해시 테이블(Hash Table)

개념

해시 테이블은 Key와 Value로 쌍을 이뤄 데이터를 저장하는 자료구조이다.

해시 테이블은 각각의 Key값에 해시함수(Hash Function)를 수행하여 고유한 인덱스를 생성시키며, 해당 인덱스를 활용하여 값을 저장, 검색하게 된다. 이때, 실제 값이 저장되는 장소를 버킷(bucket) 또는 슬롯(slot)이라 한다.

이런 구조로 데이터를 저장할 때, Key값을 해시함수를 수행하여 저장했다. 그렇다면 조회, 삭제할 때도 Key값에 대한 해시함수를 수행하면 된다.

해시 함수는 특정 입력 데이터에서 고정 길이 값을 생성하는 알고리즘이다. 해시 함수를 통해 나온 결과물은 원본으로 변환하지 못한다.
또한, 특정 입력값에는 특정 출력 값을 산출하지만 작은 변화만 줘도 극단적인 출력 값의 변화가 생긴다. 이를 눈사태 효과라 한다.

해시 함수는 원칙적으로는 동일 출력 값이 나오면 안 되지만 다른 입력값에 드물게 동일한 출력 값이 나오는 경우가 있는데 이런 경우를 해시 충돌이라 한다.

해시 충돌이 발생하는 경우

• 분리 연결법(Separate Chaining)
  • 동일한 버킷에 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다.
    이러한 방식은 해시 테이블의 확장이 필요 없고 간단하게 구현 가능하며 손쉽게 삭제할 수 있다는 장점이 있다.
    그러나 데이터의 수가 많아지면 동일한 버킷에 Chaning 되는 데이터가 많아지면서 캐시의 효율성이 감소한다는 단점이 있다.
• 개방 주소법(Open Addressing)
  • 해시 테이블의 공간을 활용하는 방법인데 이 방법에는 3가지 방법이 존재한다.
    1. Linear Probing
       현재 버킷 인덱스로부터 고정된 폭만큼 이동하여 차례대로 검색하여 비어있는 버킷에 데이터를 저장한다.
    2. Quadratic Probing
       해시의 충돌한 수를 제곱으로 저장하는 방식이다.
       예를 들면 처음 충돌한 경우 $1^2$만큼 이동하고 그다음 충돌하면 $2^2$칸, $3^2$칸씩 옮기는 방식이다.
    3. Double Hashing Probing
       해싱된 값을 한번 더 해싱하는 방식인데, 이는 해시함수를 두 번 수행하기 때문에 많은 연산을 하게 된다.

 

---

시간 복잡도

각각의 Key값은 해시함수를 수행하여 고유한 인덱스를 갖게 되어 바로 접근할 수 있기 때문에 평균 $O(1)$의 시간 복잡도를 갖는다.
하지만, 해시 충돌이 발생할 경우 $O(n)$까지 시간 복잡도가 증가할 수 있다.

 

---

장단점

• 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
• 교유한 인덱스를 사용하여 검색, 삽입, 삭제가 빠르다.
• 중복을 제거하는데 유용하다.
• 충돌이 발생할 경우가 곧 단점이다.
• 공간 복잡도가 커지며 해시함수 의존도가 높아진다.