해시(Hash)

교실에 학생이 20명 있을 때 A 학생이 있는 지 찾는다고 하자.
이때 학생들마다 자리가 정해져있다면 A학생의 자리만 확인하면 되기 때문에 탐색이 빠르다.
이때, 각각의 학생의 자리를 정해주는 방법이 Hash라 할 수 있다.

충돌(Collision)

그런데 해시 함수의 출력값은 한정된 범위에서 나온다.
따라서 비둘기 집의 원리에 의해 서로 다른 자료가 같은 해시값을 가질 수 밖에 없다.
교실에 의자 수 보다 학생 수가 많은 것이다.
이를 해결하기 위한 대표적인 방법으로 체이닝(Chaining), 오픈 어드레싱(Open Addressing)이 있다.

체이닝(Chaining)

충돌이 발생하면 그 자리에 줄줄이 소세지로 저장해두는 것이다. 구체적으로 그 구조는 배열이나 연결리스트, 트리 등이 될 수 있다.
또 다시 교실로 생각하면 두 학생이 같은 자리로 배정이 되면 그냥 그 자리에 두명이 앉는 것이다.
최악의 경우 20명 학생이 모두 한 자리에 앉게 되면 결국 A 학생이 있는 지 확인할 때 20번의 확인이 필요하므로 자리를 정해준 의미가 없다.

오픈 어드레싱(Open Addressing)

충돌이 발생하면 충돌이 없는 빈 자리를 찾아가는 것이다. 빈 자리를 찾아가는 방법은 다양하다. 바로 다음 자리로 가는 선형 탐색, 제곱 수를 더해 찾아가는 이차 탐색 등이 있다. 최대한 뭉치지 않게 잘 흩어지도록 빈 자리 찾는 방법을 정해주는 것이 중요하다. 빈 자리가 줄어들면 빈 자리를 탐색하는데 시간이 오래 걸린다.
끝내 빈 자리가 없어 질 수 있다. 이렇게 되면

• 더 이상 못 받는다고 하거나
• 테이블 크기를 확장하고 기존 데이터를 새로 해시해서 넣거나
• 체이닝 방식으로 구조를 바꿀 수 있다.

궁금한 점

• 요즘 많이 사용되는 해시 함수
• 충돌 시 처리방법 중 어떤 방법이 많이 쓰이는 가