해시란?
해시란 탐색, 삽입, 삭제를 모두 O(1) 기대 시간에 수행할 수 있도록 해 주는 기법입니다.
해시는 해시 테이블을 통해 구현되며 해시 테이블은 b개의 버킷 과 버킷 내에 s개의 사전쌍들로 이루어 집니다.
여기서 해시함수 h는 키 값을 특정 홈 주소로 사상 시키는 함수로써 주로 제산 함수 등이 사용됩니다.
h(k) = 0 ~ (b-1)
위 식에서 h(k)를 해시 혹은 홈 주소 라고 부릅니다.
이상적인 조건 하에서 모든 사전쌍들이 모두 홈 버킷에 저장됩니다.
이런 해시 테이블에 있는 쌍의 수를 n 개라 하고, 가능한 전체 키의 총 개수를 T라 할때
키 밀도 = n/T
위 식이 성립합니다.
이러한 해시 함수는 여러 개의 키를 하나의 버킷에 사상시키게 되기 때문에
h(k1) = h(k2) 가 되는 k1과 k2가 존재하게 되고 이 경우 k1과 k2를 h에 대한 동거자라고 부릅니다.
오버플로우 란 어떤 쌍을 삽입 시 홈 버킷이 넘치는 경우를 말합니다.
정적 해싱
오버플로우 처리방법에는 개방 주소법과 체인법 이 있으며, 개방 주소법 에는 선형 조사법, 이차 조사법, 재해싱, 임의 조사법이 있습니다.
오버플로우 처리법
개방 주소법
선형 조사법
체인법
선형 조사법을 비롯한 개방 주소법에서는 키를 탐색 할 때 서로 다른 해시 값을 가진 키들과 일일히 비교를 수행하기 때문에 효율이 매우 떨어집니다.
이와 달리 체인법 에서는 ht[i] 가 버킷 i에 연결된 체인들 중 첫번째 블록을 가리키고 있기 때문에, 연결된 체인 내에서만 탐색을 수행하면 되어 속도가 빠릅니다.
동적 해싱
재조정을 한 번 할 때마다 오직 하나의 버킷만 재조정함
Comments