Hash Table이란 효율적인 key value lookup을 위해 key를 value에 매핑하는 자료 구조입니다. 찾는 과정을 살펴보면, 먼저 hash function을 사용해서 hash code 값을 계산합니다. key를 변환해서 더 작은 key로 만드는데 사용되는 함수가 hash function 인데요, 그렇게 해서 얻어진 값인 hash(key) 값이 hash code 입니다.

이 hash code를 array length로 나누어 얻어진 나머지를 index로 사용해서 해당 index에 매핑되는 value를 array에 저장하고 찾는 것입니다.

예를 들어, [“apple”, “banana”, “lemon”] 이라는 key 배열이 있다고 가정하면 python에서 hash function을 사용해서 hash code를 얻으면 각각 값이 4431541238040168687, 7306034771644922176, 3404778505129102945 이 됩니다. array의 length는 3이기 때문에 각각을 3으로 나눈 나머지는 0, 1, 1 입니다. 그리고 이 값들이 index가 되어서 해당 index에 있는 value가 원래 key인 “apple”, “banana”, “lemon”에 매핑되는 값입니다.

이 경우에서도 볼 수 있지만 hash code가 다르더라도 동일한 index가 나올 수 있습니다. 또한 서로 다른 key에 대해서 hash code 값이 같을 수도 있어서 이 경우에도 동일한 index가 나올 수 있습니다.

이를 보완하기 위해 Linear Probing 기법에서는 index가 겹치면 그 다음 index를 사용합니다. 예를 들어, 아까처럼 “lemon”의 hash code를 3으로 나눈 나머지가 1로 “banana”의 index와 겹치면 1대신 2를 index로 사용합니다.

이러한 충돌이 매우 높으면 worst case로는 런타임이 O(N)이 됩니다. (여기서 N은 key의 갯수입니다.) 그러나 일반적으로 충돌이 최소한으로 발생한다고 가정하여 look up 타임을 O(1)로 가정합니다.