해시테이블은 저장되어있는 자료와 비교하여 자리를 찾지 않고, 단 한번의 계산으로 해시값을 구해 자신의 자리를 찾는다.

해시함수

• 입력한 원소가 해시테이블 전체에 고루 저장되어야 한다.
• 게산이 간단해야 한다.

1. 나누기 방법

나눈 나머지를 이용해 해시테이블 개수 안으로 축소시키는 것

2. 곱하기 방법

우선 0~1사이의 소수로 만든다음, 해시테이블 개수를 곱해 다시 팽창시키는 것

충돌(Collsion) 해결

1. 체이닝

• 충돌을 받아들이고 해당 주소로 들어온 원소가 링크드리스트를 형성한다.
• 적재율이 1을 넘어도 사용할 수 있다는 장점이 있다.

2. 개방주소 방법

• 원래 들어갈 자리에 못들어가게 되었으니 다른 곳을 찾아 들어간다.
• 적재율이 1을 넘을 수 없으며, 적재율이 높아질수록 효율이 급격히 떨어지므로 적당한 임계점을 넘으면 테이블의 크기를 키워 모든 원소를 다시 해싱하는 게 바람직하다.
• 그리고 주의해야할 점은, 삭제했을 때 삭제한 곳에 DELETED와 같은 상수로 표시를 해줘야한다는 것이다. 그렇지 않으면, 해당 위치를 건너뛰고 저장되었던 원소와의 연이 끊기게 된다. 해당 위치에 누군가 있었음을 표시해줘야 한다는 것이다.

개방주소 방법에서 다음번 주소를 정하는 것에는 대표적으로 3가지 방법이 있다.

1) 선형 조사

들어가려던 자리의 다음번 자리가 비어있는지를 보고 들어가는 것이다. 특정 영역에 원소가 몰리는 이른바 군집이 되는 경우 성능이 치명적으로 떨어진다는 단점이 있다. 이러한 군집은 특히 1차 군집이라 한다.

2) 이차원 조사

선형 조사가 일정한 보폭으로 다음번 자리를 보는데 반해, 이차원 조사는 다음 단계로 갈수록 제곱만큼의 보폭으로 다음번 자리를 본다. 따라서 1차 군집이 있어도 금방 벗어날 수 있다. 하지만 동일한 초기 해시 함수를 갖게 될 경우 같은 짓을 반복하므로, 성능이 마찬가지로 떨어진다. 이를 2차 군집이라 한다.

3) 더블 해싱

두 개의 해시 함수를 통해 해싱을 두번하는 것이다.