[자료구조] Hash Table

Hash Table의 정의

hash table이란 해시함수(hash function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조입니다.

이 해시테이블은 쉽게 핸드폰으로 통화를 하기 위해, 단축번호를 설정하여 사용하는 것과 같다고 생각하면 됩니다. 김코딩 , 010-1234-5678 , 단축번호 : 1이라는 사람에게 전화를 걸기 위해 미리 사용자가 저장한 단축번호 : 1을 누르면 010-1234-5678 번호로 바로 통화를 할 수 있습니다.

이 과정처럼, 필요한 데이터의 키(key)를 해시함수를 사용해 별도의 해시(hash)로 바꿔 주고, 해당하는 데이터(value)를 함께 저장하는 자료구조입니다.

Hash Table의 구조

• 키(key) : 고유한 값으로 해시 함수의 입력값이 됩니다. 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장하게 됩니다.
• 해시함수(hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 합니다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줍니다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요합니다.
• 해시(hash) : 키(key)를 해시함수(hash function)를 사용하여 만들어진 결과물로, 저장소에서 데이터(value)와 매칭되어 저장됩니다. 변환된 값을 배열의 색인(index)과 같이 사용하게 됩니다.
• 데이터(value) : 저장소에 최종적으로 저장되는 값으로 색인(index)과 매칭되어 저장됩니다.

Hash Table의 특징

hash table에서 저장, 삭제, 검색 과정은 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어 데이터를 다루는 작업이 매우 빠르다는 장점이 있습니다.

다만, 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어놔야 하기 때문에 공간 효율성이 떨어집니다. 또한 해시함수(hash function)의 의존도가 높습니다.

이 말은 곧, 해시 함수(hash function)가 복잡하다면, 해시(hash) 값을 만들어내는 데 많은 시간이 소요됩니다.

1. 저장, 삭제, 검색 과정

hash table에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수(hash function)에 키(key) 값을 넣어 해시(hash) 값을 만들게 됩니다. 이후 만들어진 해시(hash)값과 일치하는 색인(index)을 찾아 저장하거나 삭제, 검색합니다.

기본적으로 해당 작업들의 시간복잡도는 O(1)입니다.

해시함수(hash function)를 거쳐 해시(hash) 값을 찾아내는데 걸리는 과정은 고려하지 않습니다. 그러나 해싱 충돌이 발생할 경우 저장소의 모든 색인(index)(삽입) 혹은 데이터(value)(삭제, 검색)를 찾아봐야 하기 때문에 O(n)이 됩니다.

2. 대표적인 해시 알고리즘

• Division Method : Number type의 키(key)를 저장소의 크기로 나누어 나온 나머지를 색인(index)으로 사용하는 방법입니다. 이때 저장소의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋습니다. 예를 들어 Key 값이 23일 때 테이블 크기가 7이라면 index는 2가 됩니다.
• Digit Folding : 키(key)의 문자열을 ASCII 코드로 바꾸고 그 값을 합해 저장소에서 색인(index)으로 사용하는 방법입니다. 만약 이때 색인(index)가 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있습니다.
• Multiplication Method : 숫자로 된 Key 값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 사용합니다. index = (KA mod 1)m
• Universal Hashing : 다수의 해시함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 해시(hash) 값을 만드는 기법입니다.

---

해시 충돌을 해결할 수 있는 방법

1. 개방 연결법(Open Addressing)

개방 연결법이란 해시 충돌이 발생하면 다른 색인(index)에 해당 자료를 삽입하는 방식입니다. 이 과정도 여러 가지 방법들이 존재합니다. 그중, 가장 대표적으로 사용되는 3가지를 알아봅니다.

1. Linear Probing
   • 현재 중복된 색인(index)으로부터, 고정된 숫자만큼 이동하여 비어있는 저장소(버킷)를 찾아 데이터(value)를 저장합니다.
2. Quadratic Probing
   • 현재 중복된 색인(index)으로부터 이동할 숫자를 제곱으로 사용하는 방식입니다. 처음 충돌이 발생하면 1(1^2)만큼 이동하고, 또 충돌이 발생한다면 4(2^2)만큼, 3번째는 9(3^2)만큼, 4번째는 16(4^2)만큼 이동하여 빈 공간을 탐색하는 방법입니다.
3. Double Hasing Probing
   • 하나의 해시함수(hash function)에서 충돌이 발생한다면 미리 지정해 둔 다른 해시함수(hash function)를 이용해 새로운 주소를 받아 사용하는 방법입니다. 다른 방법들보다 많은 연산이 필요하게 됩니다.

2. 분리 연결법(Separate Chaining)

분리 연결법이란 동일한 색인(index)의 데이터에 대해 연결리스트(linked list), 트리(Red-Black tree) 등의 자료구조를 활용해 데이터의 주소를 저장하는 방법입니다.

저장소의 동일한 버킷의 데이터에 연결리스트(linked list), 트리(Red-Black tree) 등의 자료구조를 사용해서 충돌이 일어난 데이터를 저장하는 방식입니다.

이 방식의 경우 구현이 간단하며, 데이터(value)를 쉽게 삭제할 수 있다는 장점이 있습니다. 하지만 중복으로 저장되는 데이터(value)가 많아지면 동일한 버킷에 연결되는 데이터(value)가 많아져서 검색의 효율성이 감소하는 단점이 있습니다.

3. 저장소 확장(Resize)

저장소에 크기가 작다면, 불필요한 메모리 사용을 줄일 수 있지만, 해시 충돌이 발생하며 개방 연결법(Open Addressing)이나 분리 연결법(Separate Chaining)을 사용해도 성능상 손실이 발생합니다. 실제 Java에서 사용되는 HashMap이라는 자료 구조는 매치된 key-value 데이터 개수가 일정 이상이 된다면(저장소의 75% 이상 사용) 저장소의 크기를 두 배로 늘리게 됩니다. 이 방식으로 해시 충돌로 인한 성능이 감소하는 문제를 어느 정도 해결이 가능합니다.

JAVA의 HashMap 과 HashTable의 차이

java에서 HashMap 이라는 자료구조가 있는데 HashTable과의 차이는 동기화 지원 여부에 있습니다.

HashTable: 병렬 처리를 하면서 자원의 동기화를 고려할 때

HashMap: 병렬 처리와 동기화가 필요하지 않을 때

사용합니다.

[자료구조] 해시테이블이란?

꼭 알아둬야 하는 자료구조 해쉬테이블