hash의 충돌 해결법(collsion resolution in hash tables)

hash의 충돌 해결법(collsion resolution in hash tables)에 대해 정리해본다.

이 글은 open addresiing 방법을 검색하면서 공부한 내용이다.

(몇몇 블로그를 보면서 공부한 내용인데, 이게 정확한 내용인지는 한번 더 확인해보고 싶다.)

충돌(collision)은 서로 다른 입력(key)에 대해 동일한 해시 주소를 반환하는 것을 말한다.

이러한 충돌을 해결하기 위해 크게 2가지의 카테고리로 구분할 수 있다.

• Separate chaining : 버킷에는 데이터를 저장할 수 있는 리스트가 있으며, 충돌시에 리스트의 엔트리를 추가하는 방식
• Separate chaining 은 closed addressing 이라고 할 수 있는데, 데이터의 address가 해쉬 값으로 정해지기 때문이다.
  하지만, 일반적으로는 Separate chaining 이라고 한다.
• Open addressing : 버킷에 데이터가 저장되며, 충돌시에 다른 버킷에 삽입하는 방식
• open addressing 이라는 이름은 데이터의 address가 해쉬 값으로 정해지지 않기 때문이다.

실제로 충돌을 어떤 방식으로 해결하는지 정리해본다.

• Separate chaining
• with linked lists : linked lists 에 정렬된 순서로 저장
• with list head cells : 첫 레코드를 버킷(head)에 저장하고, 다른 레코드들은 head의 next로 저장
• with other structures : self-balancing tree, dynamic array를 사용하는 방법
• self-balancing tree, dynamic array : 이 자료구조들은 좀 더 공부할 필요가 있습니다...
• Open addressing
• Linear probing : 충돌시 한 칸 혹은 몇 칸씩 이동하여 데이터를 삽입
• Quadratic probling : 충돌시 제곱식을 이용하여 데이터를 삽입
• Double hashing : 충돌시에 다른 해쉬함수를 이용하여 데이터를 삽입

정리를 하다보니, 학부 때 배웠던 내용도 생각나고, 업무에 사용하는 hash에 대해서도 생각하게 되고 좋은 시간이다.

각 충돌 해결 방법의 장단점, 그리고 어떤 환경에서 어떤 해쉬를 사용해야 하는가도 정리하고 싶은 부분이다.

이 부분은 다음 시간에 다시 정리하는 것으로 하고, 이번 글을 마무리한다.

참고 링크

1. http://en.wikipedia.org/wiki/Hash_table

2. http://luyin.tistory.com/191

3. http://ir.bagesoft.com/76

4. http://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables
   (stackoverflow, Chained Hash Tables vs. Open-Addressed Hash Tables)