[Data Structure] Hash Table

Hash Table

해쉬는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 소도를 갖는다. 특정한 값을 검색하는데 데이터 고유의 index에 접근하므로 O(1)이 걸린다. 단 인덱스로 저장되는 key값이 불규칙적이다.

 

그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이므로 다른 데이터의 인덱스와 중복되지 않는다. 따라서 삽입, 삭제 시에서도 추가적인 비용이 들지 않는다.

 

Hash Function

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

 

부적절한 hash function을 사용하여 중복되는 key값을 생성하여 여러 개의 데이터가 하나의 테이블에 존재하는 것을 Collision라고 한다.

 

좋은 Hash Function의 조건

1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 Collision에 어떻게 대응할 것인가가 중요하다. 1:1 대응이 되도록 만드는 것은 거의 불가능하며 만든다고 하더라도 array와 다를바 없다.

 

Collision이 많아질 수록 검색에 대한 시간복잡도가 O(n)에 가까워진다. 즉 Collision이 발생하면 저장할 새로운 공간을 찾아야한다. 

 

Resolve Conflict

해시 충돌을 해결하는 방법을 알아보자.

Open Address 방식 (개방주소법)

해시 충돌이 발생하면 다른 해시 버킷에 삽입하는 방식이다. 버킷이란 데이터를 저장하는 공간이다. 해시 충돌이 발생하면 데이터를 저장할 다른 장소를 찾는다. Worst Case의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 돌아 올 수 있다. 이 과정에서 여러 방법이 있다.

• Linear Probing : 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.
• Quadratic Probing : 2차 함수를 이용해 탐색할 위치를 찾는다.
• Double hashing probing : 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬 함수를 이용해 주소를 할당한다. 연산량이 많다.

Separate Chaining 방식 (분리연결법)

일반적으로 Open Address 방식은 Separate Chaing 방식보다 느리다. Open Address 방식은 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 높기 때문이다. 반면 Separate Chaing 방식은 해시 충돌이 발생하지 않도록 보조 해시 함수를 통해 조정하여 Worst Case 빈도를 줄일 수 있다. Java7에서 Separate Chaing 방식을 사용하여 HashMap을 구현한다. Separate Chaing 방식은 두 가지 구현방식이 존재한다.

• 연결리스트를 사용하는 방식 : 각각의 버킷들을 연결리스트로 만들어 충돌이 발생하면 해당 버킷의 리스트에 추가하는 방식이다. 연결리스트이므로 삭제, 십입이 간단하다. 단 작은 데이터들을 저장할 때 오버헤드가 발생한다. 
• Tree를 사용하는 방식(Red-Black Tree) : 하나의 해시 버킷의 할당된 key-value 쌍의 개수에 따라 연결리스트를 사용할지 트리를 사용할지 결정한다. 데이터의 개수가 적다면 연결 리스트를 사용한다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 

 

Open Address vs Separate Chaining

• 두 방법 모두 Worst Case에서는 O(n)이다. 
• Open Address 방삭은 연속된 공간에 데이러를 저장하기 때문에 캐시 효율이 높다. 따라서 데이터의 개수가 적으면 Open Address가 더 성능이 좋다.
• Separate Chaining 방식은 테이블이 확장을 Open Address보다 늦출 수 있다.

 

보조 해시 함수

보조 해시 함수의 목적은 key의 값을 변형하여 해시 충돌 가능성을 줄이는 것이다. Separate Chaining 방식을 사용할 때 함께 사용된다.

 

해시 버킷 동적 확장(Resize)

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌록 인해 성능 상 손실이 발생한다. 그래서 HashMap을 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 버킷의 개수를 두 배로 늘린다. 현재 데이터 개수가 해시 버킷 개수의 75%를 차지하면 두 배로 늘린다. 이 때 0.75라는 숫자를 load factor라고 부른다.