개발 기초/자료구조
[Java] Hash Table
숩니따
2025. 2. 3. 14:54
해당 글에서는 아래 hash() 메소드 활용
최상위 bit(부호 bit)를 제외시키기 위해 key와 0xfffffff에 대해 AND 연산 수행하여 얻은 31bit 양수를 해시테이블 크기인 M으로 나눈 나머지를 해시값으로 사용
private int hash(Key k) {
return (k.hashCode() & 0x7fffffff) % M;
}해시테이블
핵심 아이디어
O(logN) 시간보다 빠른 연산을 위해, 키와 1차원 배열의 인덱스 관계를 이용하여 키(항목)를 저장
- 키를 배열의 인덱스로 그대로 사용하면 차지 않은 빈 공간에 메모리 낭비가 심해지므로 키를 변환하여 배열의 인덱스로 사용
- 키를 간단한 함수를 사용해 변환한 값을 배열의 인덱스로 이용하여 항목을 저장하는 것을 해싱(Hasing)이라고 함
- 해싱에 사용되는 함수를 해시함수(Hash Function)라고 하고, 해시함수가 계산한 값을 해시값(Hash Value) 또는 해시주소라고 하며, 항목이 해시값에 따라 저장되는 배열을 해시테이블(Hash Table)이라고 함
해싱
항목의 키 집합 중 k 키 값을 해시 함수에 입력하면 결과 해시값 i가 나오는데 i에 해당되는 위치에 k를 저장
충돌
2개 이상의 항목을 해시테이블의 동일한 원소에 저장하여야 하는 경우 충돌 발생
(서로 다른 키들이 동일한 해시 값을 가질 때 충돌 발생)
해시함수
- 가장 이상적인 해시함수는 키들을 균등(uniformly)하게 해시테이블의 인덱스로 변환하는 함수
- 일반적으로 키들은 부여된 의미나 특성을 가지므로 키의 가장 앞 부분 또는 뒤의 몇 자리 등을 취하여 해시값으로 사용하는 방식의 해시함수는 많은 충돌을 야기시킴
- 균등하게 변환한다는 것은 키들을 해시테이블에 랜덤하게 흩어지도록 저장하는 것을 뜻함
- 해시함수는 키들을 균등하게 해시테이블의 인덱스로 변환하기 위해 의미가 부여되어 있는 키를 간단한 계산을 통해 ‘뒤죽박죽’ 만든 후 해시테이블의 크기에 맞도록 해시 값을 계산
- 하지만 아무리 균등한 결과를 보장하는 해시 함수이더라도 함수 계산 자체에 긴 시간이 소요된다면 해싱의 장점인 연산의 신속성을 상실하므로 그 가치를 잃음
대표적인 해시함수
- 중간제곱(Mid-square) 함수 : 키를 제곱한 후, 적절한 크기의 중간부분을 해시 값으로 사용
- 접기(Folding) 함수 : 큰 자릿수를 가지는 십진수를 키로 사용하는 경우, 몇 자리씩 일정하게 끊어서 만든 숫자들의 합을 이용해 해시값을 만든다.
- (예시) 123456789012에 대해서 1234 + 5678 + 9012 = 15924 계산 후 헤시테이블의 크기가 3이라면 15924의 끝에 3자리 수만을 해시값으로 사용
- 곱셈(Multiplicative) 함수 : 1보다 작은 실수 $\delta$를 키에 곱하여 얻은 숫자의 소수부분을 테이블 크기 M과 곱한다. 이렇게 나온 값의 정수부분을 해시값으로 사용.
- h(key) = (int) (key * $\delta$) & 1) * M
- Knuth에 의하면 $\delta = \frac{\sqrt{5} - 1}{2} \approx 0.61803$이 좋은 성능을 보인다. (경험적 숫자)
해시함수의 공통점
- 키의 모든 자리의 숫자들이 함수 계산에 참여함으로써 계산 결과에서 원래 키에 부여된 의미나 특성을 찾아볼 수 없게 된다는 점
- 계산 결과에서 해시테이블의 크ㅡ기에 따라 특정부분만을 해시 값으로 활용
가장 널리 사용되는 해시함수 : 나눗셈(Division) 함수
- 나눗셈 함수는 키를 소수(Prime) M으로 나눈 뒤, 그 나머지를 해시값으로 사용
- h(key) = key % M이고, 따라서 해시테이블의 인덱스는 0에서 M-1이 됨
- 여기서 제수로 소수를 사용하는 이유는 나눗셈 연산을 했을 때, 소수가 키들을 균등하게 인덱스로 변환시키는 성질을 갖기 때문임
※ key(피제수), M(제수)
자바의 hashCode()
- 자바의 모든 클래스는 32비트 int를 리턴하는 hashCode()를 포함하고 있고, hashCode()는 객체를 int로 변환하는 메소드
- 자바의 hashCode()는 이론적으로 어떤 종류의 객체(사용자 정의한 객체 포함)라도 해싱을 할 수 있도록 지원
- hashCode()는 key1.equals(key2)가 true 이면, key1.hashCode() == key2.hasyCode()가 성립한다는 조건 하에 구현되어 있음
→ 즉 2개의 키가 동일하면 각각의 hashCode 값도 같아야 함
자바의 여러 클래스에 선언되어 있는 hashCode() 메소드
Integer
아무런 계산 없이 그대로 key를 리턴
public final class Integer {
private final int key;
public int hashCode() {return key;}
}Boolean
true이면 1231, false이면 1237을 각각 리턴
public final class Boolean {
private final boolean key;
public int hashCode() {
if (key) return 1231;
else return 1237;
}
}Double
key를 IEEE 64-bit 포맷으로 변환시킨 후, 모든 bit를 계산에 참여시키기 위해 최상위 32 bit와 최하위 bit를 XOR한 결과를 리턴
public final class Double {
private final double key;
public int hashCode() {
long bits = doubletoLongBits(key);
return (int) (bits ^ (bits >>>32));
}
}String
key의 문자 (char)를 31진수의 숫자로 간주하여 해시값을 계산
예를 들어 key = “ball”이라면 3016191 리턴
$hash = 98 * 31^3 + 97 * 31^2 + 108 * 31^1 + 108 * 31^0 = 3016191$
public final class String {
private final char [ ] s;
public int hashCode() {
int hash = 0;
for (int i = 0; i < length(); i++) {
hash = s[i] + (31 * hash);
}
return hash;
}
}자바의 hashCode()의 공통점
- 자바의 hashCode()는 제각각 다른 값을 리턴하지만 hashCode()가 리턴하는 값이 모두 signed 32 bit 정수라는 공통점을 가짐
- 자바를 이용하여 해시테이블을 구현할 때엔 일반적으로 hashCode()를 override하여 해시함수 구현
오버플로우 해결
개방주소방식(Open Addressing)
해시테이블 전체를 열린 공간으로 가정하고 충돌된 키를 일정한 방식에 따라서 찾아낸 empty 원소에 저장 ↔ 폐쇄주소방식(Closed Addressing)의 충돌 해결방법은 키에 대한 해시값에 대응되는 곳에만 키를 저장
선형조사(Linear Probing)
$$
(h(key) + i) \bmod M, j = 0, 1, 2, 3, ...
$$
- 충돌이 일어난 원소에서부터 순차적으로 검색하여 처음 발견한 empty 원소에 충돌이 일어난 키를 저장
- h(key) = i라면, 해시테이블 a[i], a[i+1], a[i+2], …, a[i+j]를 차례로 검색하여 첫번째로 찾아낸 empty 원소에 key를 저장
- 해시테이블은 1차원 배열이므로, i+j가 M이 된다면 a[0]을 검색
- 순차 탐색으로 empty 원소를 찾아 충돌된 키를 저장하므로 해시테이블의 키들이 빈틈없이 뭉쳐지는 현상이 발생
[1차 군집화(Primary Clustering)] - 이러한 군집화는 탐색, 삽입, 삭제 연산 시 군집된 키들을 순차적으로 방문해야 하는 문제점을 야기
- 군집화는 해시테이블에 empty 원소 수가 적을수록 더 심화되며 해시성능을 극단적으로 저하시킴
public class LinearProbing<K, V> {
private int M = 13; // 테이블 크기
private K[] a = (K[]) new Object[M]; // 해시테이블
private V[] d = (V[]) new Object[M]; // key 관련 데이터 저장
private int hash(K key) {
return (key.hashCode() & ox7fffffff) % M; // 나눗셈 함수
}
// 삽입 연산
private void put(K key, V data) {
int initialpos = hash(key); // 초기 위치
int i = initialpos, j = 1;
do {
// 삽입 위치 발견
if (a[i] == null) {
a[i] = key;
d[i] = data;
return;
}
// 이미 key 존재
if (a[i].equals(key)) {
d[i] = data; // 데이터만 갱신
return;
}
i = (initialpos + j++) % M; // i = 다음 위치
} while (i != initialpos); // 현재 i가 초기위치와 같게되면 루프 종료
}
// 탐색 연산
public V get(K key) {
int initialpos = hash(key);
int i = initialpos, j = 1;
// a[i]가 empty가 아니면
// 군집화 현상 때문에 null인 경우는 탐색 실패
while (a[i] != null) {
if (a[i].equals(key))
return d[i]; // 탐색 성공
i = (initialpos + j++) % M; // i = 다음 위치
}
return null; // 탐색 실패
}
}이차조사(Quadratic Probing)
$$
(h(key) + j^2) \bmod M, j = 0, 1, 2, 3, ...
$$
- 이차조사는 선형조사와 근본적으로 동일한 충돌 해결방법
- 충돌 후 배열 a에서 선형조사보다 더 멀리 떨어진 곳에서 empty 원소를 찾음
- 이차조사는 이웃하는 빈 곳이 채워져 만들어지는 1차 군집화 문제를 해결하지만,
같은 해시값을 갖는 서로 다른 키들인 동의어(Synonym)들이 똑같은 점프 시퀀스(Jump Sequence)를 따라 empty 원소를 찾아 저장하므로 결국 또 다른 형태의 군집화인 2차 군집화(Secondary Clustering)를 야기 - 점프 크기가 제곱만큼씩 커지므로 배열에 empty 원소가 있는데도 empty 원소를 건너뛰어 탐색에 실패하는 경우도 피할 수 없음
public class QuadProbing<K, V> {
private int M = 13; // 테이블 크기
private K[] a = (K[]) new Object[M]; // 해시테이블
private V[] d = (V[]) new Object[M]; // key 관련 데이터 저장
private int hash(K key) {
return (key.hashCode() & ox7fffffff) % M; // 나눗셈 함수
}
// 삽입 연산
private void put(K key, V data) {
int initialpos = hash(key); // 초기 위치
int i = initialpos, j = 1;
do {
// 삽입 위치 발견
if (a[i] == null) {
a[i] = key;
d[i] = data;
return;
}
// 이미 key 존재
if (a[i].equals(key)) {
d[i] = data; // 데이터만 갱신
return;
}
i = (initialpos + j * j++) % M; // i = 다음 위치
} while (i != initialpos); // 현재 i가 초기위치와 같게되면 루프 종료
}
// 탐색 연산
public V get(K key) {
int initialpos = hash(key);
int i = initialpos, j = 1;
// a[i]가 empty가 아니면
while (a[i] != null) {
if (a[i].equals(key))
return d[i]; // 탐색 성공
i = (initialpos + j * j++) % M; // i = 다음 위치
}
return null; // 탐색 실패
}
}랜덤조사(Random Probing)
$$
(h(key) + rand) \bmod M
$$
- 랜덤조사는 선형조사와 이차조사의 규칙적인 점프시퀀스와 달리 점프 시퀀스를 무작위화 하여 empty 원소를 찾는 충돌 해결방법
- 랜덤 조사는 의사난수(psedo random) 생성기를 사용하여 다음 위치를 찾음
- 랜덤조사 방식도 동의어들이 똑같은 점프 시퀀스에 따라 empty 원소를 찾아 키를 저장하게 되고, 이 때문 3차 군집화(Tertiary Clustering)가 발생
import java.util.Random;
public class RandProbing <K, V> {
private int M = 13; // 테이블 크기
private K[] a = (K[]) new Object[M]; // 해시테이블
private V[] d = (V[]) new Object[M]; // key 관련 데이터 저장
private int hash(K key) {
return (key.hashCode() & ox7fffffff) % M; // 나눗셈 함수
}
// 삽입 연산
private void put(K key, V data) {
int initialpos = hash(key); // 초기 위치
int i = initialpos;
Random rand = new Random();
rand.setSeed(10);
do {
// 삽입 위치 발견
if (a[i] == null) {
a[i] = key;
d[i] = data;
return;
}
// 이미 key 존재
if (a[i].equals(key)) {
d[i] = data; // 데이터만 갱신
return;
}
i = (initialpos + rand.nextInt(1000)) % M; // i = 다음 위치
} while (i != initialpos); // 현재 i가 초기위치와 같게되면 루프 종료
}
// 탐색 연산
public V get(K key) {
int initialpos = hash(key);
int i = initialpos, j = 1;
// a[i]가 empty가 아니면
while (a[i] != null) {
if (a[i].equals(key))
return d[i]; // 탐색 성공
i = (initialpos + rand.nextInt(1000)) % M; // i = 다음 위치
}
return null; // 탐색 실패
}
}이중해싱(Double Hashing)
$$
(h(key) + j \times d(key)) \bmod M, j = 0, 1, 2, 3, ...
$$
- 이중해싱은 2개의 해시함수를 사용
- 하나는 기본적인 해시함수 h(key)로 키를 해시테이블의 인덱스로 변환하고, 제2의 함수 d(key)는 충돌 발생 시 다음 위치를 위한 점프 크기를 다음의 규칙에 따라 정함
- 이중해싱은 동의어들이 저마다 제2 해시감수를 갖기 때문에 점프 시퀀스가 일정하지 않아 이중해싱은 모든 군집화 문제를 해결
- 제2의 함수 d(key)는 점프 크기를 정하는 함수이므로 0을 리턴해서는 안됨
- 제2의 함수 d(key)의 값과 해시테이블의 크기 M과 “서로소(Relatively Prime)” 관계일 때 좋은 성능을 보이므로 해시테이블 크기 M을 소수로 선택하면, 이 제약 조건을 만족
public class DobuleHashing<K, V> {
private int M = 13; // 테이블 크기
private K[] a = (K[]) new Object[M]; // 해시테이블
private V[] dt = (V[]) new Object[M]; // key 관련 데이터 저장
private int hash(K key) {
return (key.hashCode() & ox7fffffff) % M; // 나눗셈 함수
}
// 삽입 연산
private void put(K key, V data) {
int initialpos = hash(key); // 초기 위치
int i = initialpos, j = 1;
int d = (7 - (int) key % 7); // 두 번째 해시 함수, d(key) = 7 - key % 7
do {
// 삽입 위치 발견
if (a[i] == null) {
a[i] = key;
dt[i] = data;
return;
}
// 이미 key 존재
if (a[i].equals(key)) {
dt[i] = data; // 데이터만 갱신
return;
}
i = (initialpos + j * d) % M; // i = 다음 위치
} while (i != initialpos); // 현재 i가 초기위치와 같게되면 루프 종료
}
// 탐색 연산
public V get(K key) {
int initialpos = hash(key);
int i = initialpos, j = 1;
int d = (7 - (int) key % 7);
// a[i]가 empty가 아니면
while (a[i] != null) {
if (a[i].equals(key))
return d[i]; // 탐색 성공
i = (initialpos + j * d) % M; // i = 다음 위치
}
return null; // 탐색 실패
}
}
폐쇄주소방식(Closed Addressing)
- 폐쇄주소방식의 충돌 해결 방법은 키에 대한 해시값에 대응되는 곳에만 키를 저장
- 충돌이 발생한 키들은 한 위치에 모여 저장
- 이를 구현하는 가장 대표적인 방법 : 체이닝(Chaning)
public class Chaining<K, V> {
private int M = 13; // 테이블 크기
private Node[] a = new Node[M]; // 해시 테이블
public static class Node { // Node 클래스
private Object key;
private Object data;
private Node next;
// 배열의 원소에는 연결리스트 Node를 가리키는 레퍼런스 저장
// 키, 데이터, 다른 노드 참조 ref로 구성
public Node(Object newkey, Object newdata, Node ref) { // 생성자
key = newkey;
data = newdata;
next = ref;
}
public Object getKey() { return key; }
public Object getData() { return data; }
}
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % M; } // 나눗셈 연산
public V get(K key) { // 탐색 연산
int i = hash(key);
for (Node x = a[i]; x != null; x= x.next) // 연결리스트 탐색
if (key.equals.(x.key)) return (V) x.data; // 탐색 성공
return null; // 탐색 실패
}
private void put(K key, V data) { // 삽입 연산
int i = hash(key);
// 항상 앞으로 삽입
for (Node x = a[i]; x != null, x = x.next) {
if (key.equals(x.key)) { // 이미 키 존재
x.data = data; // 데이터만 갱신
return;
}
a[i] = new Node(key, data, a[i]); // 연결리스트의 첫 노드로 삽입
}
} 해싱 종류
정적 해싱 (Static Hashing)
고정 크기의 배열을 이용한 방법으로 구현이 쉽고 간단
재해시(Rehash)
- 어떤 해싱방법도 해시테이블에 비어있는 원소가 적으면, 삽입에 실패하거나 해시성능이 급격하게 저하되는 현상을 피할 수 없음
- 이러한 경우, 해시테이블을 확장시키고 새로운 해시함수를 사용하여 모든 키들을 새로운 해시테이블에 다시 저장하는 재해시(Rehash)가 필요
- 재해시는 오프라인에서 이루어지고 모든 키들을 다시 저장해야하므로 O(N) 시간이 소요
- 재해시 수행 여부는 적재율(Load Factor)에 따라 결정
- 적재율 α = (테이블에 저장된 키의 수 N) / (테이블의 크기 M)
- 일반적으로 α > 0.75가 되면 해시테이블 크기를 2배로 늘리고, α < 0.25가 되면 해시테이블을 1/2로 줄임
동적 해싱(Dynamic Hashing)
대용량의 데이터베이스를 위한 해시방법으로 재해싱을 수행하지 않고 동적으로 해시테이블의 크기를 조절
확장해싱
- 디렉터리(Directory)를 메인메모리(Main Memory)에 저장하고, 데이터는 디스크 블록(Disk Block) 크기 버킷(Bucket) 단위로 저장
- 버킷이란 키를 저장하는 곳
- 확장해싱에서는 버킷에 오버플로우가 발생하면 새 버킷을 만들어 나누어 저장하며 이때 이 버킷들을 가리키던 디렉터리는 2배로 확장
→ 디렉터리 확장
선형해싱
- 디렉터리 사용없이, 삽입할 때 버킷을 순서대로 추가하는 방식
- 추가되는 버킷은 삽입되는 키가 저장되는 버킷과 무관하게 순차적으로 추가
- 만일 삽입되는 버킷에 저장공간이 없으면 오버플로우 체인에 새 키를 삽입
- 체인은 단순연결리스트로서 오버플로우된 키들을 임시로 저장하고, 나중에 버킷이 추가되면 오버플로우 체인의 키들을 버킷으로 이동
- 오버플로우가 일어날 경우, 버킷 개수가 linear하게 (하나씩) 증가
해시방법의 성능 비교 및 응용
- 해시방법의 성능은 탐색이나 삽입 연산을 수행할 때 성공과 실패한 경우를 각가 분석하여 측정
- 선형조사는 적재율 α가 너무 작으면 해시테이블에 empty 원소가 너무 많고 α값이 1.0에 근접할수록 군집화가 심화됨
- 개방주소방식의 해싱은 α가 0.5에 가까울수록 즉, $M \approx 2N$일 때 상수시간 성능 보임
- 체이닝은 α가 너무 작으면 대부분의 연결리스트들이 emtpy가 되고, α가 너무 크면 연결리스트길이가 너무 길어져 해시성능이 매우 저하됨
- 일반적으로 M이 소수
[출처] 경기대학교 | 소프트웨어중심대학산업