[자료구조] 해시 테이블(Hash Table)

 해시 테이블(Hash Table)이란, 검색하고자 하는 키(key) 값을 입력받아서 해시 함수(hash function)를 통해 얻은 해시를 배열의 색인(index)으로 환산해서 데이터(value)에 접근하는 자료구조이다. 즉, 필요한 데이터의 키를 해시함수를 사용해 별도의 해시로 바꾸고 해당하는 데이터를 함께 저장하는 자료구조이다.

 

 해시 테이블은 주소록(Address Book), 블록체인(Blockchain), 크롬, V8 등에 사용된다.

 

 

 

 

구조

 해시 테이블은 키, 해시 함수, 해시, 데이터로 이루어져 있다.

 

• 키(key)
  : 고유한 값으로 해시 함수의 입력값이 된다.
  
  
• 해시 함수(hash function)
  : 키를 해시로 바꿔주는 역할을 한다.
  
  
• 해시(hash)
  : 해시 함수에 의해 얻어지는 값이다.
  
  
• 데이터(value)
  : 저장소에 최종적으로 저장되는 값, 인덱스와 매칭되어 저장된다.

 

 

 

 

특징

hash table에서 저장, 삭제, 검색 과정은 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있어서 데이터를 다루는 작업이 매우 빠르다. 하지만 해시 충돌이 발생할 경우, 저장소의 모든 인덱스와 데이터를 찾아봐야 하기 때문에 시간 복잡도는 O(n)이 된다.

 

 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어둬야 하기 때문에 공간 효율성이 떨어진다. 또한 해시 함수의 의존도가 높다. 즉, 해시 함수가 복잡하다면 해시 값을 만드는 데 많은 시간이 소요된다.

 

 

 

 

충돌(Collision)

 해시 테이블은 크기보다 키의 개수가 많기 때문에 서로 다른 키가 같은 해시가 되는 경우가 있다. 이를 해시 충돌(hash collistion)이라고 하며, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요하다.

 

 다음과 같은 방법으로 해시 충돌을 해결할 수 있다.

 

• 개방 연결법(Open Addressing)
  : 해시 충돌이 발생하면 다른 인덱스에 해당 자료를 삽입하는 방법이다.
  
  
• 분리 연결법(Seperate Chaining)
  : 동일한 인덱스의 데이터에 대해 linked list, Red-Black tree 등의 자료구조를 활용해서 데이터의 주소를 저장하는 방법이다.
  
  
• 저장소 확장(Resize)
  : 저장소의 크기가 작으면 불필요한 메모리를 줄일 수 있지만, 해시 충돌이 발생할 경우 이를 해결하는 과정에서 성능상 손실이 발생한다. 따라서 저장소 크기를 늘려서 해시 충돌로 인해 성능이 감소하는 문제를 어느 정도 해결이 가능하다.