이중 해시

이중 해시법은 해시 충돌을 해결하기 위한 방법이다. 서로 다른 두 값들이 같은 해시 키를 갖게 되면 해시 충돌이 일어나게 된다. 충돌이 일어난 항목들을 따로 관리하지 않고 해시 테이블의 다른 주소 공간에 배열한다면 어디에 이것을 배열해야 하는지에 대한 문제가 생긴다. 이중 해시법은 다른 해시 함수로 값을 해시하여 그 값만큼을 현재 주소에 더하여 새 주소를 얻는다. 이렇게 되면 충돌시 건너뛰는 너비가 값에 따라 달라지기 때문에 한 해시 값에 뭉치는 경우가 줄어든다. 그리고 운이 나쁜 경우 계속 충돌이 일어나서 탐색 시간이 매우 오래 걸리게 되는 문제가 해결된다.