[자료구조] 해시 테이블(Hash Table)

해시 테이블이란?

Hash Table (출처: wikimedia commons)

해시 테이블(hash table)은 키를 값에 매핑하여 데이터를 관리하는 연관 배열 자료구조이다. 한 마디로 키와 값이 1 대 1로 연결되고, 키를 이용하여 값을 저장, 삭제, 검색할 수 있는 것이다. 해시 테이블에서 키와 값을 맵핑하기 위해서는 해시코드가 필요하다. 해시코는 키를 정수로 변환한 값을 말한다.

예를 들어, 크기 50의 배열 A가 있고, 문자열 "abcdef"를 정수 100과 맵핑하려고 한다. 이때 문자열 "abcdef"를 특정 정수로 변환하여 25를 얻었다면, A[25]에 100을 저장하여 "abcdef"와 100을 맵핑할 수 있다.

key -> function(key) -> hash code => index -> 값 저장, 삭제, 검색

 

 

해시 함수

해시 함수(hash function)는 키를 함수 인자로 받아서 사칙연산, 모듈러 연산, 비트 연산 등의 알고리즘을 적용하여 특정 정수 값을 만들고, 이 값을 반환해주는 함수이다. 해시 함수는 인자로 받는 키가 같으면 항상 같은 값을 반환해야 한다.

 

아래 함수는 문자열을 해시코드로 변환하는 간단한 예제이다.

/*
* 문자열의 아스키코드 값을 더해 반환
*/
public int hashCode(String value) {
    int h = 0;
   	for(char c : value.toCharArray()) {
    	h += c;
    }
    return h;
}

해시코드를 배열의 인덱스로 사용할 수 있다. 하지만 배열의 크기가 해시코드보다 작은 경우 해시코드를 배열의 크기에 맞게 변환해야 한다. 아래 함수는 해시코드를 50이 넘지 않는 인덱스로 변환해주는 간단한 예제이다.

// 해시테이블 배열 크기
private static int DATA_SIZE = 50;

/*
* 해시코드를 데이터의 크기로 나머지 연산하여 인덱스 반환
*/
public int hash(String key) {
    return hashCode(key) % DATA_SIZE;
}

 

※ Java 11(OpenJDK 11.0.3) HashMap의 hash 함수

// HashMap의 hash 함수
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

 

해시 충돌 및 해결 방법

해시 충돌(collision)은 서로 다른 키 값이 같은 해시 코드를 갖는 경우 또는 서로 다른 해시 코드가 같은 배열의 인덱스를 갖는 경우를 말한다. 예제 함수 hashcode와 hash로 충돌의 경우를 살펴보면 다음과 같다. 먼저, hashCode("abc")의 반환 값과 hashCode("cba")의 반환 값은 294로 동일하다. 이경우 해시코드의 값이 같으므로 배열의 인덱스 값도 같아 출동일 발생한다. 다음으로 hashCode("abc")의 반환 값과 hashCode("kvw")의 반환 값은 각각 294와 344이다. 하지만 hash("abc")의 반환 값과 hash("kvw")의 값은 44로 동일하다. 즉, 문자열 "abc"와 "kvw"는 해시코드의 값은 다르지만 배열의 인덱스 값이 같아 충돌이 발생한다.

 

해시 충돌을 해결하기 위해 사용되는 방법은 체이닝(Chaining)과 선형탐사(Linear Probing)가 있다.

체이닝은 충돌한 데이터를 리스트 또는 트리로 연결하는 방법이다. N개의 데이터가 한곳에 충돌했을 경우, 리스트로 연결하면 탐색하는데 O(N) 만큼 시간이 걸리지만 구현이 간단하다. 트리로 연결하면 트리의 균형을 맞춰야 하기 때문에 삽입에 시간이 걸지만 균형을 맞춘 이진트리는 탐색하는데 O(log2N) 만큼 시간이 걸린다. 선형탐사는 충돌이 발생한 데이터를 사용하지 배열의 공간에 우선 저장하는 방법이다.

 

해시 테이블의 시간 복잡도

해시 테이블은 해시 함수를 이용하여 데이터에 바로 접근할 수 있는 인덱스를 생성하기 때문에 삽입, 삭제, 검색의 평균 시간 복잡도는 O(1)이다. 해시 충돌이 발생하여 일부 데이터 접근 속도에 영향을 줄 수 있지만 평균 시간 복잡도는 영향을 끼치지는 않는다.

 

 

 

 

참고

엔지니어대한민국

코딩하는거니

Wikimedia Commons