[Data Structure] Hash Table

1. Hash Table

• Hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Search 하는데 데이터 고유의 index로 접근하게 되므로 average case에 대하여 시간 복잡도가 O(1)이다. (항상 O(1)일 수는 없는데 collision 때문이다.) 하지만 문제는 이 인덱스로 저장되는 key 값이 불규칙하다.
• 그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조이다.

2. Hash Function

• ‘특별한 알고리즘’이란 것을 통해 고유한 인덱스 값을 설정한다. ‘특별한 알고리즘을’ hash method 또는 해시 함수(hash function)이라고 하고 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 한다. 저장되는 값들의 key 값들을 hash functino을 통해서 작은 범위의 값들로 바꿔준다.
• 하지만 어설픈 hash function을 통해서 key 값들을 결정한다면 동일한 값이 도출될 수 있다. 이렇게 되면 동일한 key 값에 복수개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것인데 이를 충돌(collision)이라고 한다.
• 그렇다면 좋은 hash function은 어떤 조건들을 갖추고 있어야 하는가?
• 일반적으로 좋은 hash function은 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 낸다. 하지만 좋은 해쉬 함수는 키가 어떤 특성을 가지고 있느냐에 따라 달라진다.
• hash function을 무조건 1:1로 만드는 것보다 collision을 최소화하는 방향으로 설계하고 발생하는 collision에 대비해 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능 한것도 있지만 그런 hash function을 만들어봤자 그건 array와 다를 바 없고 메모리 차지만 한다.
• Collision이 많아질 수록 Search에 필요한 시간복잡도가 O(1)에서 O(n)에 가까워진다. 어설픈 hash function은 hash를 hash 답게 사용하지 못하도록 한다. 좋은 hash function을 선택하는 것은 hash table의 성능 향상에 필수적이다.
• 따라서 hashing된 인덱스에 이미 다른 값이 들어 있다면 새 데이터를 저장할 다른 위치를 찾은 뒤에야 저장할 수 있는 것이다. 따라서 충돌 해결은 필수이며 그 방법들에 대해 알아보자.

3. Resolve Conflict

• 기본적으로 두 가지 방법을 알아보자.

1. Open Address 방식 (개방주소법)

   • 해시 충돌이 발생하면 (삽입하려는 해시 버킷이 이미 사용 중인 경우) 다른 해시 버킷에 해당 자료를 삽입하는 방식이다. 버킷이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.
   • 공개 주소 방식이라고도 불리는 이 알고리즘은 충돌이 발생하면 데이터를 저장할 장소를 찾는다. Worst case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다. 이 과정에서도 여러 방법이 존재한다.
     • Linear Probing : 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행한다.
     • Quadratic probing : 2차 함수를 이용해서 탐색할 위치를 찾는다.
     • Double hashing probing : 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 새로운 주소를 할당한다. 위 두가지 방법에 비해 많은 연산량을 요구한다.

2. Separate Chaining 방식 (분리 연결법)

   • 일반적으로 Open Addression은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면 Separate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워 지는 빈도를 줄일 수 있다. Java 7에서는 Separate Chaining 방식을 사용하여 HashMap을 구현하고 있다. Separate Chaining 방식으로는 두 가지 방식이 있다.

     • 연결 리스트를 사용하는 방식(Linked List) : 각각의 버킷들을 연결리스트로 만들어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식이다. 연결 리스트의 특징을 이용하여 삭제 또는 삽입이 간단하고, 작은 데이터를 저장할 때 연결 리스트 자체의 오버헤드가 부담이 된다. 또 다른 특징으로는 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.
     • Tree를 사용하는 방식(Red-Black Tree) : 기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용한다.
     • 연결 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 key-value쌍의 개수이다. 데이터의 개수가 적다면 연결 리스트를 사용하는 것이 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터의 개수가 적을 때 Worst Case를 살펴보면 트리와 연결 리스트의 성능 상 차이가 거의 없다. 따라서 메모리 측면을 봤을 대 데이터 개수가 적을 때는 연결리스트를 사용한다.
       • 데이터가 적다는 것은 얼마나 적다는 것을 의미할까? key-value 쌍의 개수 6개 8개를 기준으로 결정한다. 자료구조를 변환하는 기준이 1이라면 Switching 비용이 너무 많이 들어가기 때문에 기준을 2로 잡았다. 6 - 7 - 8로 개수가 늘어날 경우 연결리 스트에서 트리로 변환하고, 8 - 7 - 6으로 개수가 줄어들 경우 트리에서 연결리스트로 변환한다.

   • 보조 해시 함수

     • 보조 해시 함수의 목적은 key의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다. separate chaining 방식을 사용할 때 함께 사용되며 보조 해시 함수로 Worst Case 가까워지는 경우를 줄일 수 있다.

4. 해시 버킷 동적 확장

• 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생한다. 그래서 HashMap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
• 해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷 개수의 75%가 될 때이다.