Hash Table

hash는 내부적으로 배열을 사용하기 때문에 데이터를 검색할 때에 빠른 속도를 갖는다. 특정한 값을 검색할 때에는 데이터 고유의 인덱스로 접근하게 되기 때문에 average case에 대해 시간 복잡도는 O(1)이다. hash에서의 문제는 key값이 불규칙하다는 것이다.

이를 해결하기 위해 특별한 알고지름을 통해 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 후 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입 연산 시 다른 데이터의 사이에 끼어들거나 삭제 시 다른 데이터로 채울 필요가 없어지기 때문에 연산에서 추가적인 비용이 발생하지 않는다.

Hash Function

앞서 말한 특별한 알고리즘이 바로 Hash Function이다. 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hash code라고 한다. 저장되는 값들의 key값을 hash function을 통하여 작은 범위의 값들로 바꿔준다.

그러나 어설픈 hash function을 사용할 경우 동일한 key값이 도출될 가능성이 있다. 이렇게 되면 동일한 key값에 복수 개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것이다. 이것을 Collision이라고 한다.
** Collision: 서로 다른 두 개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없게되는데 이 현상을 말함.

Collision이 발생하지 않기 위해서는 좋은 hash function이 필요하다. 좋은 hash function의 조건은 다음과 같다.

• 키의 일부분을 참조하여 해쉬값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만든다. 하지만 좋은 hash function은 키가 어떤 특성을 가지고 있느냐에 따라 달라지게 된다.
• hash function을 무조건 1:1로 만드는 것 보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비하여 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것은 거의 불가능하고, 그런 hash function을 만들게 될 경우 그것은 array와 별 다른 점이 없어지게 되며 메모리를 많이 차지한다.

Collision이 많아질 수록 검색에 필요한 시간 복잡도가 O(1)에서 O(n)으로 가까워진다. 어설픈 hash function은 hash를 hash답게 사용하지 못하게 만든다. hash table의 성능 향상에는 좋은 hash function을 선택하는 것이 필수적이라고 할 수 있다.

hashing된 인덱스에 이미 다른 값이 들어있을 경우에는 새로운 데이터를 넣기 위한 새로운 인덱스를 찾아야만 저장할 수 있는 구조이다. 그렇기 때문에 충돌의 해결은 필수이다.

Resolve Conflict

충돌 해결 방법에는 2가지가 있다.

Open Address 방식 (개방 주소법)

개방 주소법은 해시 충돌이 발생했을 때에 다른 해시 버킷에 해당 자료를 저장하는 방식이다. 여기서 버킷은 바구니와 같은 개념으로 데이터를 저장하기 위한 공간을 의미하고 있다. 최악의 경우에는 다른 해시 버킷을 찾지 못해 제자리로 돌아올 수도 있다. 개방 주소법에서 다른 해시 버킷을 찾는 방법에는 3가지가 존재한다.

• Linear Probing:
  비어있는 버킷을 찾을 때 까지 순차적으로 탐색하는 방법
• Quadratic Probing:
  2차 함수를 이용해 탐색할 위치를 찾는 방법
• Double Hashing Probing:
  하나의 hash function에서 충돌이 발생할 경우 2차 hash function을 이용해 새로운 주소를 할당받는 방법.
  (다른 두가지 방법에 비해 많은 연산량을 요구함)

Separate Chaining 방식 (분리 연결법)

일반적으로 Open Address 방식은 사용중인 버킷의 비율이 높아질 수록 Worst case의 발생 빈도가 증가한다. 점점 비어있는 버킷이 줄어들기 때문이다. 반면에 Separate Chaining 방식은 해시 충돌이 잘 발생하지 않도록 hash function을 조정할 수 있다면 Worst case에 가까운 경우의 빈도를 줄일 수 있다. Java 7에서는 HashMap을 Separate Chaining 방식으로 구현하고 있다. Separate Chaining 방식에는 2가지 종류가 있다.

• Linked List(연결 리스트) 방식
  각각의 버킷들을 연결 리스트로 만들어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식이다. 연결 리스트를 사용했기 때문에 삽입과 삭제가 간단하지만 작은 데이터들을 저장할 경우 연결 리스트 자체의 오버헤드가 부담된다. 그리고 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.
• Red-Black Tree 방식
  연결 리스트 대신에 트리를 사용하는 방식이다. 연결 리스트와 트리 방식 중에서 선택하는 기준은 해시 버킷에 할당된 key-value 쌍의 개수이다. 데이터의 수가 적을 경우에는 연결 리스트 방식을 사용하는 것이 유리하다. 트리는 기본적으로 메모리 사용량이 많기 때문에 적은 데이터를 저장할 때에는 좋지 않다. 트리의 성능이 더 좋기는 하지만 데이터가 적을 경우에는 성능의 차이가 거의 없기 때문에 데이터가 적다면 연결 리스트를, 데이터가 많다면 트리를 사용하는 것이 좋다.

데이터의 많고 적고의 기준은 6개와 8개이다. 7을 건너뛰고 6과 8로 정한 이유는 데이터의 양이 변화했을 때 자료구조를 변경하는 비용을 줄이기 위해서이다. 만약 초기의 데이터가 6개라면 연결 리스트로 구현할 것이다. 그러다가 데이터가 추가되어 7개가 된다면 트리로 변경시켜줘야 한다. 그러던 중에 다시 데이터가 삭제되어 6개가 된다면 연결 리스트로 자료구조를 다시 변경해야한다. 이러한 상황을 방지하기 위해 7을 건너뛰고 6과 8로 기준이 정해졌다.

Open Address vs Separate Chaining

두 방식 보두 최악의 경우에는 O(M)의 시간 복잡도를 가진다. 그러나 Open Address 방식은 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 높다. 따라서 데이터의 개수가 충분히 적다면 Open Address 방식을 사용하는 것이 좋다.

다른 차이점은 Open Address방식은 버킷을 계속해서 사용하는 반면 Separate Chaining은 그러지 않기 때문에 테이블의 확장을 보다 늦출 수 있다.

보조 해시 함수

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

해시 버킷 동적 확장 (Resize)

해시 버킷의 개수가 적다면 메모리를 아낄 수 있지만 해시 충돌로 인해 성능의 문제가 발생하게 된다. 그래서 Hash Map은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 저하 문제를 어느정도 해결할 수 있다. 이때 일정 개수는 현재 데이터 개수의 75%를 의미한다. 여기서 0.75는 load factor라고 불린다.