Hash Tale!

해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다.

해시 함수 - 위키백과, 우리 모두의 백과사전

해시 테이블은 자주 사용되는 자료구조입니다. 혹시 파이썬을 사용하셨다면 딕셔너리를 떠올리시면 됩니다!

해시 테이블은 key를 기준으로 value에 접근할 수 있습니다. 그렇다면 key의 값만 알면 바로 직접 접근이 가능하다는 것입니다. 그렇기 때문에 시간복잡도는 O(1)을 가집니다. 그러나 최악의 경우에는 O(n)을 가지게 됩니다.

key를 알고 있으면 value로 바로 접근할텐데 왜 O(n)을 가지게 되는지 의문일 수 있습니다.

그 이유는 Hash Collision 때문입니다. 

해시충돌이라고도 불리는데 서로 다른 key의 값이 hash function에 의해 동일한 index를 리턴하게 되서 그렇습니다.

해시 테이블의 key는 오직 한 곳의 value만을 가리켜야 합니다. 즉 모든 key와 value는 1:1로 맵핑이 되어 있어야 옳습니다.

즉 key와 value의 1:1 맵핑을 위해 key의 값을 hash function이라는 매서드에 인자값으로 주어서 특정 규칙에 의해 value를 리턴하게 됩니다. 이 때, 동일한 key의 값이라면 항상 동일한 value를 리턴하게 되고 서로 다른 key의 값이라면 서로 다른 value 값을 리턴해야 합니다. 이와 같은 기능을 하는 것이 hash function이고 hash function에 의해서 hash table의 성능이 결정됩니다. 

hash table의 성능이 hash function에 의해 결정된다는 말은 hash function이 서로 다른 key값이라도 동일한 value 값을 리턴하게 된다면 ? 이 hash table의 성능은 떨어지는 것이라고 말할 수 있습니다. 왜냐하면, 서로 다른 key의 값이 같은 value값을 가리키게 됩니다. 즉 1:1 맵핑이 아니라 n:1 맵핑이 되면서 서로 충돌하게 되는데, 이러한 현상을 해시충돌이라고 합니다. 해시충돌이 자주 일어날 수록 hash table의 성능은 떨어질 수 밖에 없습니다.

그 이유를 알아보기 위해, 다시 의문으로 돌아가서 O(n)을 가지는 이유를 알아보자면 해시 충돌에 대비하기 위해서 hash table에서는 해시충돌이 일어나게 되는 경우에 대처방안을 생각해야합니다.

그렇기 때문에 value의 값을 배열로 만들어서 연결할 수도 있고, 해시 충돌이 일어날 경우 다른 value의 값에 맵핑할 수도 있습니다. 그렇기 때문에 한번에 key값을 찾아내지 못한다면 n번의 배열을 다 돌아서 찾아야 할 수 있기때문에 O(n)의 시간복잡도를 가집니다.

즉 O(1)의 시간복잡도를 갖는 것이 옳은데 해시 충돌에 의해 최악의 경우 O(n)을 가지게 되는 것입니다. 즉 hash function을 잘 구현하는 것이 hash table 성능의 핵심이라고 말할 수 있겠습니다.