Hash

Hashing : key 값을 비교하지 않고 검색할 수 있는 방법

Hashing Collision : 서로 다른 키가 같은 hash 주소로 생성되는 경우

Hashing의 주소는 랜덤하게 생성된다 예로서 h(k) = k mod 10으로 만약 key가 52이면 h(52)=2, key가 42이면 h(42)=2이다. 이때 같은 주소 2를 가리키게 되므로 collision이 발생한다.

• 주소값 계산 방법

key는 알파벳 순으로 나열되지만 주소에서는 순서가 없다. 즉, 입력 순서대로나 특정 규칙으로 들어오는 것이 아니다.

h(OLIVIER) = 004. 인자 값을 첫번째 두글자인 OL을 아스키코드로 바꾸어 계산한다. O=79, L=76. 두 값을 곱하면 79*76=6004이므로 6004 mod 10 = 4이므로 주소는 004가 된다.

 Collision을 피하기 위해서 bucket을 사용한다. bucket은 해당 주소에 1개 이상의 record를 담는다.

Probe sequence란?

 h(key1) = h(key2) 일때를 말한다. hash 주소가 같게 되어 +3이나 일정한 규칙으로 다음 주소 공간에 key를 저장하게 된다. 이러한 주소 공간들은 probe sequence가 같다고 한다. 하지만 비슷한 주소끼리 겹치면 clustering problem이 발생한다. 이것은 double hashing을 통해 해결할 수 있다.

Dynamic hashing : Tree + Hashing

 각 bucket마다 tree를 지닐 수 있다. (b)의 4에서 40xxx, 41xxx로 값이 나누어져서 tree로 되는 것을 볼 수 있다. (c) 에서는 2가 20xxx, 21xxx로 나누어지고 41이 410xx, 411xx로 나누어져 tree가 되는 것을 볼 수 있다.