[자료구조/JAVA] 해시 테이블 (Hash Table)
해시 테이블 (Hash Table)
해시 테이블(Hash Table)은 데이터를 효율적으로 저장하고 검색하기 위한 자료구조이다.
데이터를 키-값 쌍으로 매핑한 후, 이를 배열에 저장하는데, 각 키에 대해서 해시 함수를 적용하여 해시 값을 계산하여 이를 배열의 인덱스로 사용한다. 따라서 특정 키에 대한 검색이 빠르게 이루어질 수 있다.
버킷(Bucket): 해시 테이블의 각 슬롯을 가리키는 용어이다.
데이터 삽입 과정
해시 함수 적용: 데이터의 키를 해시 함수에 넣어 해시 값을 계산한다.
해시 값의 인덱스 결정: 해시 값을 기반으로 배열에서 저장될 위치인 인덱스를 결정한다.
데이터 저장: 결정된 인덱스에 데이터를 저장한다. 만약 해당 인덱스에 이미 데이터가 저장되어 있다면 충돌이 발생한 것이다.
충돌 해결: 충돌이 발생했을 경우에는 충돌을 해결하기 위한 방법을 사용하여 다음 빈 슬롯을 찾는다.
해시함수
이상적인 해시 함수
1. 키들을 균등(Uniform)하게 해시테이블의 인덱스로 변환 → 해시테이블에 랜덤하게 흩어지도록 저장하는 것
2. 해시 함수가 복잡하면 안됨(연산 속도가 오래 걸리면 안됨)
해시 함수의 종류 : 중간제곱(Mid-square)함수, 접기(Folding)함수, 곱셈(Multiplicative) 함수
가장 널리 사용되는 해시함수 : 나눗셈(Division) 함수 → h(key) = key % M(제수, Divisior)
- M을 소수로 사용하는 이유 : 나눗셈 연산 시 소수가 키들을 균등하게 인덱스로 변환시키는 성질을 가지기 때문이다.
해시 충돌
해시 충돌(Collision) : 서로 다른 아이템들의 키들이 동일한 해시값을 가지는 경우, 배열의 같은 인덱스에 아이템 여러개를 일반적으로는 동시에 저장할 수는 없다. 해당 현상을 해시 충돌이라고 하며, 충돌 해결을 위한 기법을 사용해야 한다.
충돌 해결 기법
개방주소방식(Open Addressing): 충돌이 발생했을 때, 새로운 키를 위해 해시 테이블의 다른 위치를 찾아 사용하는 방식
- 선형 조사(Linear Probing)
- 이차 조사(Quadratic Probing)
- 랜덤 조사(Random Probing)
- 이중 해싱(Double Hashing)
폐쇄주소방식(Closed Addressing): 충돌이 발생했을 때, 같은 버킷 내에 연결 리스트 등의 데이터 구조를 사용하여 항목을 저장
- 체이닝(Chaining)
해시 테이블 구현
class Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
@Override
public String toString() {
return "[" + this.key + " : " + this.value + "]";
}
}public class MyHashTable<K, V> {
private Entry<K, V>[] table;
private int capacity;
private int size;
public MyHashTable(int capacity) {
this.capacity = capacity;
this.table = new Entry[capacity];
this.size = 0;
}
private int hash(K key) {
// 절대값[Key의 해시코드(Integer)] % 배열의 크기 = 해시함수로 사용
return Math.abs(key.hashCode()) % capacity;
}
public void insert(K key, V value) {
if (size == capacity) {
System.out.println("해시 테이블이 가득 찼습니다.");
return;
}
int index = hash(key);
// 충돌 해결 기법을 적용시켜야 함
table[index] = new Entry<>(key, value);
size++;
}
public V search(K key) {
int index = hash(key);
// 충돌 해결 기법을 적용시켜야 함
return table[index].getValue();
}
public void remove(K key) {
int index = hash(key);
// 충돌 해결 기법을 적용시켜야 함
if (table[index].getKey().equals(key)) {
table[index] = null;
size--;
return;
}
}
public void print(){
for(Entry e : table){
System.out.print(e + " ");
}
}
}
search()
- 주어진 키를 해시 함수를 통해 해시값으로 변환한 후, 해당 인덱스에 위치한 엔트리를 찾는다.
- 충돌이 발생할 수 있기 때문에 현재 코드에는 충돌 처리 부분이 구현되어 있지 않으므로 충돌 해결 방법을 적용해야 한다.
insert()
- 주어진 키를 해시 함수를 통해 해시값으로 변환한 후, 해당 인덱스에 엔트리를 추가시킨다..
- 마찬가지로 충돌이 발생할 수 있기 때문에 현재 코드에는 충돌 처리 부분이 구현되어 있지 않으므로 충돌 해결 방법을 적용해야 한다.
remove()
- 주어진 키를 해시 함수를 통해 해시값으로 변환한 후, 해당 인덱스에 위치한 엔트리를 확인하여 엔트리를 제거한다.
- 마찬가지로 충돌이 발생할 수 있기 때문에 현재 코드에는 충돌 처리 부분이 구현되어 있지 않으므로 충돌 해결 방법을 적용해야 한다.
충돌 해결 : 개방주소법 - 선형 조사(Linear Probing)
동일한 해시값으로 인해 충돌이 발생하면, 순차 탐색으로 인덱스를 1씩 증가시켜가면서 비어있는 다음 버킷을 탐색하여 그 곳에 데이터를 삽입하는 방식이다.
탐색 및 삭제시에도 해당 해시값에 해당하는 키값이 일치하지 않으면 인덱스를 1씩 증가시켜가면서 일치하는 키를 탐색한다.
1차 군집화 : 순차탐색을 사용하므로 해시테이블의 키들이 빈틈없이 뭉쳐지는 현상이 발생하게 된다. 이러한 군집화는 해시테이블의 Empty 원소 수가 적을수록 더 심화되며, 해시 성능을 극단적으로 저하시킨다.
public class LinearProbingHashTable<K, V> {
private Entry<K, V>[] table;
private int capacity;
private int size;
public LinearProbingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Entry[capacity];
this.size = 0;
}
private int hash(K key) {
// 절대값[Key의 해시코드(Integer)] % 배열의 크기 = 해시함수로 사용
return Math.abs(key.hashCode()) % capacity;
}
public void insert(K key, V value) {
if (size == capacity) {
System.out.println("해시 테이블이 가득 찼습니다.");
return;
}
int index = hash(key);
while (table[index] != null) {
index = (index + 1) % capacity; // 충돌 발생 시 인덱스를 1씩 증가시켜 삽입 위치를 찾음
}
table[index] = new Entry<>(key, value);
size++;
}
public V search(K key) {
int index = hash(key);
while (table[index] != null) {
// 키가 일치할 경우 해당 Value 반환
if (table[index].getKey().equals(key)) {
return table[index].getValue();
}
// 만약 키가 일치하지 않는다면 다음 인덱스를 조사
index = (index + 1) % capacity;
}
return null; // 찾지 못한 경우
}
public void remove(K key) {
int index = hash(key);
while (table[index] != null) {
// 키가 일치할 경우 해당 항목 제거
if (table[index].getKey().equals(key)) {
table[index] = null;
size--;
return;
}
// 만약 키가 일치하지 않는다면 다음 인덱스를 조사
index = (index + 1) % capacity;
}
}
public void print(){
for(Entry e : table){
System.out.print(e + " ");
}
}
}
충돌 해결 : 개방주소법 - 이차 조사(Quadratic Probing)
선형 조사와 유사하지만 동일한 해시값으로 인해 충돌이 발생하면, 인덱스를 제곱 합수를 사용하여 증가시켜가면서 비어있는 다음 버킷을 탐색하여 그 곳에 데이터를 삽입하는 방식이다.
위의 예시에서 보면 Key 50을 삽입하려 할 때 충돌이 발생하여 1^2 만큼 증가시킨 버킷에 삽입하려고 하였다. 또다시 해당 버킷에서도 충돌이 발생하자 2^2만큼 증가시킨 인덱스의 버킷에 삽입하였다.
이차 조사는 이웃하는 빈 곳이 채워져 만들어지는 1차 군집화 문제를 해결한다.
그렇지만 결국 동의어(같은 해시값을 가지는 서로 다른 키들)들이 똑같은 시퀀스를 따라 Empty를 탐색 및 저장하므로 또 다른 형태의 2차 군집화 문제를 야기하게 된다.
public class QuadraticProbingHashTable<K, V> {
private Entry<K, V>[] table;
private int capacity;
private int size;
public QuadraticProbingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Entry[capacity];
this.size = 0;
}
private int hash(K key) {
// 절대값[Key의 해시코드(Integer)] % 배열의 크기 = 해시함수로 사용
return Math.abs(key.hashCode()) % capacity;
}
public void insert(K key, V value) {
if (size == capacity) {
System.out.println("해시 테이블이 가득 찼습니다.");
return;
}
int index = hash(key);
int step = 1;
while (table[index] != null) {
index = (index + step * step) % capacity; // 충돌 발생 시 인덱스를 step이 제곱씩 증가시켜 삽입 위치를 찾음
System.out.println("index" + index);
step++;
}
table[index] = new Entry<>(key, value);
size++;
}
public V search(K key) {
int index = hash(key);
int step = 1; // 두 번째 해시 함수의 결과
while (table[index] != null) {
// 키가 일치할 경우 해당 Value 반환
if (table[index].getKey().equals(key)) {
return table[index].getValue();
}
// 만약 키가 일치하지 않는다면 인덱스를 step만큼 증가시킨 후 조사
index = (index + step * step) % capacity;
step++;
}
return null; // 찾지 못한 경우
}
public void remove(K key) {
int index = hash(key);
int step = 1;
while (table[index] != null) {
// 키가 일치할 경우 해당 항목 제거
if (table[index].getKey().equals(key)) {
table[index] = null;
size--;
return;
}
// 만약 키가 일치하지 않는다면 인덱스를 step만큼 증가시킨 후 조사
index = (index + step * step) % capacity;
step++;
}
}
public void print(){
for(Entry e : table){
System.out.print(e + " ");
}
}
}
충돌 해결 : 개방주소법 - 랜덤 조사(Random Probing)
선형조사와 이차조사의 규칙적인 점프 시퀀스와는 달리, 점프 시퀀스를 무작위로 하여 Empty 원소를 찾는 충돌 해결 방법이다.
랜덤 조사 방식 역시 동의어들이 일정한 패턴에 따라 Empty를 탐색하게 되는 3차 군집화 문제가 발생한다.
public class RandomProbingHashTable<K, V> {
private Entry<K, V>[] table;
private int capacity;
private int size;
private Random random;
public RandomProbingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Entry[capacity];
this.size = 0;
this.random = new Random();
}
private int hash(K key) {
// 절대값[Key의 해시코드(Integer)] % 배열의 크기 = 해시함수로 사용
return Math.abs(key.hashCode()) % capacity;
}
// 무작위로 0부터 capacity-1 사이의 값을 반환
private int randomStep() {
return random.nextInt(capacity);
}
public void insert(K key, V value) {
if (size == capacity) {
System.out.println("해시 테이블이 가득 찼습니다.");
return;
}
int index = hash(key);
int step = randomStep(); // 임의의 수
while (table[index] != null) {
index = (index + step) % capacity; // 충돌 발생 시 인덱스를 step씩 증가시켜 삽입 위치를 찾음
}
table[index] = new Entry<>(key, value);
size++;
}
public V search(K key) {
int index = hash(key);
int step = randomStep(); // 임의의 수
while (table[index] != null) {
// 키가 일치할 경우 해당 Value 반환
if (table[index].getKey().equals(key)) {
return table[index].getValue();
}
// 만약 키가 일치하지 않는다면 인덱스를 step만큼 증가시킨 후 조사
index = (index + step) % capacity;
}
return null; // 찾지 못한 경우
}
public void remove(K key) {
int index = hash(key);
int step = randomStep(); // 임의의 수
while (table[index] != null) {
// 키가 일치할 경우 해당 항목 제거
if (table[index].getKey().equals(key)) {
table[index] = null;
size--;
return;
}
// 만약 키가 일치하지 않는다면 인덱스를 step만큼 증가시킨 후 조사
index = (index + step) % capacity;
}
}
public void print(){
for(Entry e : table){
System.out.print(e + " ");
}
}
}
충돌 해결 : 개방주소법 - 이중 해싱(Double Hashing)
이중 해싱 방법은 두 개의 해시함수를 사용하여 충돌을 회피하는 방법이다.
한 개의 해시함수(h(key))는 기존의 해시테이블의 인덱스로 변환하는 역할을 하고, 다른 해시함수(d(key))는 충돌 발생 시 다음 위치를 위한 점프 크기를 결정하는 해시함수로 사용된다. 점프 크기를 정하므로 해당 해시함수는 0을 반환해서는 안 된다.
따라서 동의어들이 저마다 제 2의 해시함수를 가지기 때문에 점프 시퀀스가 일정하지 않는다. 이를 통해 모든 군집화 문제를 해결할 수 있다.
d(key)의 값과 해시테이블의 크기 M과 서로소 관계일 때 좋은 성능을 보인다 -> 해시테이블 크기 M을 소수로 선택하면 된다.
public class DoubleHashingHashTable<K, V> {
private Entry<K, V>[] table;
private int capacity;
private int size;
public DoubleHashingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Entry[capacity];
this.size = 0;
}
private int hash(K key) {
// 절대값[Key의 해시코드(Integer)] % 배열의 크기 = 해시함수로 사용
return Math.abs(key.hashCode()) % capacity;
}
private int stepHash(K key) {
// 두 번째 해시 함수를 정의. 해시 결과가 0이 되면 안 되므로 0보다 큰 수 중에서 선택
int hash = Math.abs(key.hashCode()) % (capacity - 1);
return hash != 0 ? hash : 1;
}
public void insert(K key, V value) {
if (size == capacity) {
System.out.println("해시 테이블이 가득 찼습니다.");
return;
}
int index = hash(key);
int step = stepHash(key); // 두 번째 해시 함수의 결과
while (table[index] != null) {
index = (index + step) % capacity; // 충돌 발생 시 인덱스를 step씩 증가시켜 삽입 위치를 찾음
}
table[index] = new Entry<>(key, value);
size++;
}
public V search(K key) {
int index = hash(key);
int step = stepHash(key); // 두 번째 해시 함수의 결과
while (table[index] != null) {
// 키가 일치할 경우 해당 Value 반환
if (table[index].getKey().equals(key)) {
return table[index].getValue();
}
// 만약 키가 일치하지 않는다면 인덱스를 step만큼 증가시킨 후 조사
index = (index + step) % capacity;
}
return null; // 찾지 못한 경우
}
public void remove(K key) {
int index = hash(key);
int step = stepHash(key);
while (table[index] != null) {
// 키가 일치할 경우 해당 항목 제거
if (table[index].getKey().equals(key)) {
table[index] = null;
size--;
return;
}
// 만약 키가 일치하지 않는다면 인덱스를 step만큼 증가시킨 후 조사
index = (index + step) % capacity;
}
}
public void print(){
for(Entry e : table){
System.out.print(e + " ");
}
}
}
결과
public static void main(String[] args) {
DoubleHashingHashTable<String, Integer> hashTable = new DoubleHashingHashTable<>(11);
hashTable.insert("One", 1);
hashTable.insert("Two", 2);
hashTable.insert("Three", 3);
hashTable.insert("Four", 4);
hashTable.insert("Five", 5);
hashTable.insert("Six", 6);
hashTable.insert("Seven", 7);
hashTable.insert("Eight", 8);
hashTable.insert("Nine", 9);
System.out.println("검색 결과:");
System.out.println("키 Two 값: " + hashTable.search("Two")); // 2
System.out.println("키 Ten 값: " + hashTable.search("Ten")); // null
hashTable.remove("Three");
System.out.println("Three 키 삭제 후 검색 결과:");
System.out.println("키 Three 값: " + hashTable.search("Three")); // null
System.out.println("전체 해시 테이블 값");
hashTable.print();
}검색 결과:
키 Two 값: 2
키 Ten 값: null
Three 키 삭제 후 검색 결과:
키 Three 값: null
전체 해시 테이블 값
[Two : 2] [Seven : 7] null null [Five : 5] [Nine : 9] [Four : 4] [Eight : 8] [Six : 6] null [One : 1]
Process finished with exit code 0
충돌 해결 : 폐쇄주소법 - 체이닝(Chaining)
폐쇄주소방식 : 키에 대한 해시값에 대응되는 곳에 모아서 키를 저장하는 방법이다. 대표적인 방법으로 체이닝(Chaning)이 있으며 이를 구현하기 위해서 배열의 인덱스의 원소들을 Linked List를 사용하여 구현하게 된다.
public class ChainingHashTable<K, V> {
// 체이닝을 위해서 Linked List의 배열을 선언
private LinkedList<Entry<K, V>>[] table;
private int capacity;
private int size;
public ChainingHashTable(int capacity) {
this.capacity = capacity;
this.table = new LinkedList[capacity];
this.size = 0;
for (int i = 0; i < capacity; i++) {
table[i] = new LinkedList<>();
}
}
private int hash(K key) {
return Math.abs(key.hashCode()) % capacity;
}
public void insert(K key, V value) {
int index = hash(key);
LinkedList<Entry<K, V>> list = table[index];
// 해당 해시값에 대응하는 배열의 인덱스에 위치한 LinkedList를 탐색한다.
for (Entry<K, V> entry : list) {
// 키가 존재한다면 Value만 바꾼다.
if (entry.getKey().equals(key)) {
entry.setValue(value);
return;
}
}
// Linked List에 <Key, Value>를 추가한다.
list.add(new Entry<>(key, value));
size++;
}
public V search(K key) {
int index = hash(key);
LinkedList<Entry<K, V>> list = table[index];
// 해당 해시값에 대응하는 배열의 인덱스에 위치한 LinkedList를 탐색한다.
for (Entry<K, V> entry : list) {
// 키가 존재한다면 LinkedList에서 해당 아이템을 반환한다.
if (entry.getKey().equals(key)) {
return entry.getValue();
}
}
return null;
}
public void remove(K key) {
int index = hash(key);
LinkedList<Entry<K, V>> list = table[index];
// 해당 해시값에 대응하는 배열의 인덱스에 위치한 LinkedList를 탐색한다.
for (Entry<K, V> entry : list) {
// 키가 존재한다면 LinkedList에서 해당 아이템을 지운다.
if (entry.getKey().equals(key)) {
list.remove(entry);
size--;
return;
}
}
}
public void print(){
for (int i = 0; i < capacity; i++) {
System.out.print("Index " + i + ": ");
LinkedList<Entry<K, V>> list = table[i];
for (Entry<K, V> entry : list) {
System.out.print(entry + " ");
}
System.out.println();
}
}
}public static void main(String[] args) {
ChainingHashTable<String, Integer> hashTable = new ChainingHashTable<>(11);
hashTable.insert("One", 1);
hashTable.insert("Two", 2);
hashTable.insert("Three", 3);
hashTable.insert("Four", 4);
hashTable.insert("Five", 5);
hashTable.insert("Six", 6);
hashTable.insert("Seven", 7);
hashTable.insert("Eight", 8);
hashTable.insert("Nine", 9);
System.out.println("검색 결과:");
System.out.println("키 Two 값: " + hashTable.search("Two")); // 2
System.out.println("키 Ten 값: " + hashTable.search("Ten")); // null
hashTable.remove("Three");
System.out.println("Three 키 삭제 후 검색 결과:");
System.out.println("키 Three 값: " + hashTable.search("Three")); // null
System.out.println("전체 해시 테이블 값");
hashTable.print();
}검색 결과:
키 Two 값: 2
키 Ten 값: null
Three 키 삭제 후 검색 결과:
키 Three 값: null
전체 해시 테이블 값
Index 0: [Two : 2] [Five : 5] [Six : 6]
Index 1: [Eight : 8]
Index 2:
Index 3:
Index 4:
Index 5:
Index 6: [Four : 4]
Index 7: [Nine : 9]
Index 8:
Index 9: [Seven : 7]
Index 10: [One : 1]
해시 테이블의 성능
해시는 해시 테이블에 비어있는 원소가 부족하면 삽입에 실패하거나 해시 성능이 급격히 저하될 수 있다. 즉, 해시 테이블의 성능은 적재율에 매우 큰 영향을 받는다는 소리이다. 따라서 해시 테이블의 적재율에 따라서 해시 테이블의 크기를 조절하는 방법이 필요하다.
- 적재율 : 해시 테이블에 저장된 키의 수(N)를 테이블의 크기(M)로 나눈 비율. 적재율이 일정 수준 이상으로 증가하면 해시 테이블의 성능이 저하될 가능성이 높아진다.
재해싱(Rehashing) : 해당 문제를 해결하기 위해 해시 테이블을 확장하고 모든 키를 새로운 해시 테이블에 다시 저장하는 과정. 모든 키를 다시 저장해야 하기 때문에 O(N)의 시간이 소요된다.
동적 해싱 : 재해싱을 수행하지 않고 해시 테이블의 크기를 동적으로 조절하는 방법. 확장 해싱과 선형 해싱은 동적 해싱의 한 형태이다.
- 확장 해싱 : 디렉터리를 메인 메모리에 저장하고 데이터를 디스크 블록 크기의 버킷 단위로 저장하는 방식. 버킷이 가득 찰 경우에는 디렉터리를 확장하여 새로운 버킷을 추가한다.
- 선형 해싱 : 디렉터리 사용 없이, 삽입할 때 버킷을 순서대로 추가하는 방식, 추가되는 버킷은 삽입되는 키가 저장되는 버킷과 무관하게 순차적으로 추가한다. 만약 삽입되는 버킷에 저장공간이 없으면 Overflow 체인에 임시로 새 키를 삽입하고 나중에 버킷이 추가되면 해당 버킷에 Overflow 체인의 키들을 이동시키는 방법. 해당 방식은 삽입이 빈번한 경우에도 효율적으로 해시 테이블을 유지할 수 있는 장점이 있다.
해시 테이블 vs 트리
해시 테이블과 트리는 모두 데이터를 효율적으로 구조화하여 검색 성능을 향상시키고 빠르게 접근하기 위한 자료 구조이다. 해당 두 자료구조가 어떤 경우에 특화되어 있는지 살펴보자.
해시가 트리보다 좋은 경우
단일 검색: 해시는 키를 기반으로 직접 값을 찾기 때문에 트리보다 검색 속도가 훨씬 빠르다. 데이터가 많을 경우 좋은 성능을 보인다.
간단한 구현: 해시는 트리보다 구현이 비교적 간단하다.
해시가 트리보다 나쁜 경우
순서 제한: 해시는 데이터의 순서를 보장하지 않는다. 즉 정렬되지 않는다.
범위 검색: 위의 특성으로 인해서 트리가 특정 범위 검색에 좋은 성능을 발휘하는 것과 대비하여 좋은 성능을 내지 못한다.
데이터의 분포 : 데이터가 고르게 분포되지 않을 경우 특정 버킷에 데이터가 집중되어 범위 검색 성능이 저하될 수 있다.
시간 복잡도
해시 함수 : 해시 테이블의 시간 복잡도는 얼마나 좋은 해시 함수를 사용하느냐에 따라 좌우된다.
삽입, 삭제, 검색
충돌이 발생하지 않을 때 : 일반적으로 O(1)
충돌이 발생하는 경우 : 최악의 경우 O(N)
이상적인 해시 테이블 : 충돌이 적게 발생하고, 해시 함수가 균등하게 키를 분배할 때 평균적으로 O(1)의 시간 복잡도를 가진다.
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘/JAVA] 백트래킹(Backtracking) : 개념 (N-Queen / 스도쿠) (0) | 2024.04.16 |
|---|---|
| [알고리즘/JAVA] 정렬 알고리즘 : 선택, 삽입, 버블, 병합, 퀵 정렬 (0) | 2024.04.05 |
| [자료구조/JAVA] 허프만 코딩 (Huffman Coding) (0) | 2024.03.31 |
| [자료구조/JAVA] 우선순위 큐 : 힙(Heap) (0) | 2024.03.28 |
| [자료구조/JAVA] 트리 (3) : AVL 균형 트리 (AVL Tree) (0) | 2024.03.25 |
