Hash Table
해시 테이블은 Key, Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블에서 데이터는 각 데이터 값에 고유한 인덱스 값이 있는 배열 형식으로 저장된다. 원하는 데이터의 인덱스를 알면 데이터 접근이 빨라진다. 따라서 데이터의 크기에 관계없이 저장 및 검색 작업이 매우 빠른 데이터 구조가 된다. 해시 테이블은 배열을 저장 매체로 사용하고 해시 기술을 사용하여 데이터가 저장되고 위치할 인덱스를 생성한다.
Hashing
해싱은 키 값을 배열의 인덱스로 변환하는 기술이다. 해시 테이블은 각각의 키 값에 해시함수를 적용해 배열의 고유 index를 생성한다.
예를 들어 (Key, Value) 값이 (Lisa Smith, 521-8976)인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 hash function을 통해 index = hashFucntion("Lisa Smith") % 16 연산을 통해 Index 값을 계산한다. 그리고 array[index] = "521-8976"로 데이터를 저장하게 된다. 이러한 해싱 구조로 저자하면 Key 값으로 데이터를 찾을 때 해시 함수를 한 번만 수행하면 되기 때문에 매우 빠르게 데이터를 저장/조회/삭제 할 수 있다.
Hash Table 구조
해시테이블은 n개의 버킷으로 이루어지는 테이블로서 n-1개의 원소를 가진다. 하나의 버킷은 s개의 슬롯을 가질 수 있으며 하나의 슬롯에는 하나의 항목이 저장된다. 하나의 버킷에 여러 슬롯을 두는 이유는 서로 다른 두 개의 Key가 해시 함수에 의해 동일한 해시 Index로 변환될 수 있으므로 여러 개의 항목을 동일한 버킷에 저장하기 위함이다.
Collision
다른 Key 값을 hash function에 넣었는데 같은 index이 계산될 때 이를 해시 충돌이라고 한다. 아래 예제에서 보면 서로 다른 Key값인 'John Smith'와 'Sandra Dee'가 서로 같은 Index를 2를 가르키고 있다. 이러한 해시 충돌 해결 방법에는 Separate Chaining 방식과 Open Addressing 방식이 있다
Separate Chaining
충돌 시 해시 테이블 인덱스에 연결 리스트를 이용해서 여러 값을 연결한 형태로 저장한다. 체이닝의 경우 버킷이 꽉 차더라도 연결 리스트로 계속 늘려가기 때문에 데이터의 index는 바뀌지 않는다.
Open Addressing
해시충돌이 일어나면 다른 저장소에 데이터를 삽입하는 방식이다.
선형 탐색(Linear Probing): 해시 충돌이 발생하면 다음 버킷, 혹은 몇 개를 건너뛰어 데이터를 삽입한다. 구조가 간단하고 캐시 효율이 높지만 한 번 충돌이 나면 집중적으로 충돌이 발생하는 것을 의미하기에 평균 검색 시간이 증가한다. 최악의 경우 해시테이블 전체를 검색해야 하는 상황이 발생할 수 있다.
제곱 탐색(Quadratic Probing): 충돌이 일어난 인덱스의 제곱을 한 해시에 데이터를 저장한다. 선형 탐색보다 충돌은 적지만 처음 충돌한 위치가 같다면 다음 충돌할 위치도 반복적으로 계속 충돌이 나게된다.
이중 해시(Double Hashing): 다른 해시 함수를 한 번 더 적용한 해시에 테이터를 저장한다.
Separate Chaining 과 Open Addressing 비교
체이닝은 연결 리스트를 사용하여 복잡한 계산식을 개방 주소법에 비해 적게 사용하지만 해시테이블이 채워질수록 성능 저하가 발생한다. 개방 주소법은 포인터가 필요 없고 지정한 메모리 외 추가적 저장 공간이 필요 없다. 하지만 슬롯이 80% 이상 차게 되면 급격하게 성능 저하가 일어난다