[CS] 자료구조 - Hash Table 충돌

Hash Table

효율적인 탐색을 위한 자료구조로써 키-값 쌍의 데이터를 입력받고 키에 대한 해시 값을 사용해 값을 저장하고 조회하는 자료구조이다.
내부적으로 배열(버킷)을 사용해 데이터를 저장하기 때문에 빠른 검색 속도를 제공한다. 각각의 키 값에 해시 함수를 적용해 배열의 고유한 인덱스를 생성하고 이 인덱스를 활용해 값을 저장하거나 검색한다. 이때 저장한 데이터의 실제 값이 저장되는 곳을 버킷/슬록이라고 한다.
저장 / 삭제 / 검색의 시간복잡도가 모두 O(1) 이지만, 충돌 발생으로 인한 최악의 경우 O(n)이 될 수 있다.
 

해시 테이블 데이터 저장

 
("John Smith", "521-1234")의 key-value 쌍 데이터를 크기가 16인 해시 테이블에 저장하려고 한다. 먼저 index = hash.function("John Smith") % 16 연산을 통해 인덱스 값을 계산한다. 그리고 array[index] = "521-1234"로 전화번호를 저장한다.이런 해싱 구조로 데이터를 저장하면 key 값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 된다.
즉, 매우 빠른 데이터의 저장 / 삭제 / 조회가 가능하다.
 
 

---

 

Hash Table 충돌 발생

위의 해시 테이블 데이터 저장 이미지를 예시로 만약 "John Smith"를 해시 함수로 돌려 나오는 값과 "Sandra Dee"를 돌려 나오는 값이 동일한 경우 충돌이 발생했다고 한다. 이때 해결할 수 있는 방법은 Open Addressing(개방주소법)과 Separate Chaining(분리 연결법)으로 나뉜다.
 

• Open Addressing 방식
  추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. 충돌이 발생하면 미리 정한 규칙에 따라 비어있는 해시 테이블에 데이터를 저장한다. 데이터의 삭제 시에는 삭제된 공간이 Dummy Space로 활용되기 때문에 Hash Table을 재정리 해주는 작업이 필요하다. 빈 slot을 찾는 방법에 따라 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉜다.
  
  1. Linear Probing : 현재 버킷 index로부터 고정폭 만큼씩 이동해 차례대로 검색해 비어있는 버킷에 데이터 저장
  2. Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식
  3. Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식으로 다른 방법보다 연산이 많음

• Separate Chining 방식
  동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용해 다음 데이터의 주소를 저장하는 방법으로 linked list를 이용해 충돌이 발생하면 노드를 추가해 데이터를 저장한다. 이런 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며 손쉽게 삭제가 가능하다. 하지만 데이터의 수가 많아지면 동일한 버킷에 Chaining되는 데이터가 많아져 캐시의 효율성이 감소한다.
  
  

 
 
 

충돌이 잦은 경우

해시 테이블이 아닌 다른 자료 구조를 찾아 사용해보거나, 해시 테이블을 사용해야만 하는 상황이면 해시 함수가 적절한지를 확인한다. 또한 해시 테이블이 75% 이상 채워져 있다면 테이블을 확장해본다. 해시 충돌이 잦은 경우 효율적으로 해시 테이블을 사용하려면 separe chaining에서 linked list가 아닌 Tree를 사용함으로써 최악의 경우에도 O(log N)의 시간을 보장하도록 한다.
 
- 테이블 확장 (Resize)
해시 테이블이 많이 채워져 빈 슬롯이 적어지면 충돌이 잦아져 성능 손실이 발생한다. 때문에 일정 임계점 이상 데이터가 채워지면 2배로 해시 테이블을 늘려준다.
 
 

---

 

HashMap vs. HashTable

동기화 지원 여부의 차이가 있다. 해시테이블을 병령 프로그래밍을 할 때 동기화를 지원해주고 해당 함수를 처리하는데 시간이 조금 지연된다. 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 해시테이블을, 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면 해시맵을 사용하면 된다.
 

---

* https://mangkyu.tistory.com/102
* https://pinopino.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%A9%B4%EC%A0%91-%EB%8C%80%EB%B9%84-%EC%A7%88%EB%AC%B8-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%97%85