HashTable이란?
해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조입니다. 해시 테이블은 내부적으로 배열(버킷)을 사용해서 데이터를 저장하는 방식입니다. 해시 테이블은 각각의 Key값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 됩니다. 여기서 실제 값이 저장되는 장소를 버킷, 슬롯이라고 합니다.
하지만 해시 테이블의 키 값은 해시 테이블의 크기가 정해진 이상 같은 값이 나올 수 있는 가능성이 있습니다. 키 값이 같은 경우를 해시 충돌 (Hash Collision)이 발생했다고 합니다. 충돌을 해소할 수 있는 방식에는 크게 2가지가 있는데 첫 번째로각 버킷마다 연결 리스트를 생성해서 해시 충돌이 발생하더라도 연결 리스트에 저장하는 분리 연결 방식과, 두 번째로 충돌이 발생하면 정해진 규칙에 따라 빈 자리를 찾아서 저장하는 개방 주소 방식이 있습니다.
HashTable의 시간복잡도
각 Key값은 해시 함수에 의해 고유한 Index를 가지게 되어 바로 접근할 수 있기 때문에 평균 O(1)의 시간 복잡도로 데이터를 조회할 수 있습니다. 하지만 데이터 충돌이 발생하는 경우에는 충돌을 해소하기 위한 탐색을 하기 때문에 O(N)까지 시간 복잡도가 증가할 수 있습니다.
Separate Chaining (분리 연결 방식)
1. 분리 연결 방식이란?
동일한 버킷에 대해 연결 리스트와 같은 자료 구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 방식입니다.
아래 그림과 같이 동일한 버킷으로 접근하게 되면 해당 버킷의 리스트에 값을 저장해 데이터를 관리합니다.
이러한 체이닝 방식은 테이블의 확장이 필요없고, 간단하게 구현이 가능합니다. 또한 손쉽게 삭제할 수 있다는 장점이 있습니다. 하지만 데이터의 수가 많아지면 동일한 버킷에 저장되는 데이터가 많아지고 그만큼 캐시 효율성이 감소하는 단점이 있습니다.
2. 구현 코드
public class ChainingHashTable<K, V> {
private LinkedList<Entry<K, V>>[] table;
private int numberOfItems;
public ChainingHashTable(int capacity) {
table = new LinkedList[capacity];
numberOfItems = 0;
for (int i = 0; i < capacity; i++) {
table[i] = new LinkedList<>();
}
}
private int getHash(String key) {
int hashCode = 0;
for (char c : key.toCharArray()) {
hashCode += c;
}
return hashCode % table.length;
}
public void put(K key, V value) {
int indexOfBucket = this.getHash((String) key);
LinkedList<Entry<K, V>> buckets = table[indexOfBucket];
buckets.add(0, new Entry<>(key, value));
numberOfItems++;
}
public Entry<K, V> remove(K key) {
if (numberOfItems == 0) {
throw new RuntimeException("Hash Table is Empty!");
}
int indexOfBucket = this.getHash((String) key);
LinkedList<Entry<K, V>> bucket = table[indexOfBucket];
for (Entry<K, V> entry : bucket) {
if (entry.key.equals(key)) {
bucket.remove(entry);
numberOfItems--;
return entry;
}
}
return null;
}
public V get(K key) {
int indexOfBucket = this.getHash((String) key);
LinkedList<Entry<K, V>> bucket = table[indexOfBucket];
for (Entry<K, V> entry : bucket) {
if (entry.key.equals(key)) {
return entry.value;
}
}
return null;
}
}
3. 테스트
데이터 저장
public class Test {
public static void main(String[] args) {
ChainingHashTable<String, Integer> chainingHashTable = new ChainingHashTable<>(10);
chainingHashTable.put("김", 1);
chainingHashTable.put("나", 2);
chainingHashTable.put("박", 3);
chainingHashTable.put("이", 4);
chainingHashTable.display();
}
}
데이터 조회
public class Test {
public static void main(String[] args) {
ChainingHashTable<String, Integer> chainingHashTable = new ChainingHashTable<>(10);
chainingHashTable.put("김", 1);
chainingHashTable.put("나", 2);
chainingHashTable.put("박", 3);
chainingHashTable.put("이", 4);
System.out.println(" get(김) : " + chainingHashTable.get("김"));
System.out.println(" get(나) : " + chainingHashTable.get("나"));
System.out.println(" get(박) : " + chainingHashTable.get("박"));
System.out.println(" get(이) : " + chainingHashTable.get("이"));
}
}
데이터 삭제
public class Test {
public static void main(String[] args) {
ChainingHashTable<String, Integer> chainingHashTable = new ChainingHashTable<>(10);
chainingHashTable.put("김", 1);
chainingHashTable.put("나", 2);
chainingHashTable.put("박", 3);
chainingHashTable.put("이", 4);
chainingHashTable.display();
chainingHashTable.remove("김");
chainingHashTable.display();
System.out.println(" rm(김) : "+ chainingHashTable.get("김"));
}
}
Open Addressing (개방 주소 방식)
1. 개방 주소 방식이란?
개방 주소 방식은 추가적인 메모리 없이 테이블 내의 비어있는 공간을 활용하는 방법입니다. 개방 주소 방식의 구현 방법에는 3가지가 있는데, 현재 버킷으로부터 고정폭 만큼씩 이동하여 차례대로 검색하여 비어 있는 버킷에 데이터를 저장하는 Linear Probing 방식, 해시의 저장 순서 폭을 제곱으로 저장하는 Quadratic Probing 방식, 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 Double Hashing Probing 방식이 있습니다.
2. 구현 코드 (Linear Probing 방식)
public class AddressingHashTable<K, V> {
private Entry<K, V>[] table;
private int numberOfItems;
private int capacity;
public AddressingHashTable(int capacity) {
this.capacity = capacity;
table = new Entry[capacity];
numberOfItems = 0;
}
private int getHash(String key) {
int hashCode = 0;
for (char c : key.toCharArray()) {
hashCode += c;
}
return hashCode % table.length;
}
public void put(K key, V value) {
if (numberOfItems == table.length) {
this.refresh();
}
int indexOfBucket = this.getHash((String) key);
while (table[indexOfBucket] != null) {
indexOfBucket = (indexOfBucket + 1) % capacity;
}
table[indexOfBucket] = new Entry(key, value);
numberOfItems++;
}
public Entry<K, V> remove(K key) {
if (numberOfItems == 0) {
throw new RuntimeException("Hash Table is Empty!");
}
int indexOfBucket = this.getHash((String) key);
for (int i = 0; i < capacity; i++) {
if (table[indexOfBucket].key.equals(key)) {
Entry<K, V> removeItem = table[indexOfBucket];
table[indexOfBucket] = null;
numberOfItems--;
this.refresh();
return removeItem;
}
indexOfBucket = (indexOfBucket + 1) % capacity;
}
return null;
}
public V get(K key) {
int indexOfBucket = this.getHash((String) key);
for (int i = 0; i < capacity; i++) {
Entry<K, V> now = table[indexOfBucket];
if (now != null && now.key.equals(key)) {
return now.value;
}
indexOfBucket = (indexOfBucket + 1) % capacity;
}
return null;
}
private void refresh() {
if (numberOfItems == table.length) {
capacity = capacity * 2;
}
int newNumberOfItems = 0;
Entry<K, V>[] newTable = new Entry[capacity];
for (Entry<K, V> entry : table) {
if (entry == null) {
continue;
}
K key = entry.key;
V value = entry.value;
int indexOfBucket = this.getHash((String) key);
while (newTable[indexOfBucket] != null) {
indexOfBucket = (indexOfBucket + 1) % capacity;
}
newTable[indexOfBucket] = new Entry<K, V>(key, value);
newNumberOfItems++;
}
this.numberOfItems = newNumberOfItems;
this.table = newTable;
}
}
3. 테스트
데이터 저장
public class Test {
public static void main(String[] args) {
AddressingHashTable<String, Integer> addressingHashTable = new AddressingHashTable<>(10);
addressingHashTable.put("김", 1);
addressingHashTable.put("나", 2);
addressingHashTable.put("박", 3);
addressingHashTable.put("이", 4);
addressingHashTable.display();
}
}
데이터 저장 (꽉 찼을 때 Refresh)
public class Test {
public static void main(String[] args) {
AddressingHashTable<String, Integer> addressingHashTable = new AddressingHashTable<>(4);
addressingHashTable.put("김", 1);
addressingHashTable.put("나", 2);
addressingHashTable.put("박", 3);
addressingHashTable.put("이", 4);
}
}
4의 공간을 가지는 테이블이 꽉 찼을 때는 refresh() 를 통해서 기존의 테이블을 확장하는 로직을 구현했습니다.
위의 과정을 통해 4의 크기를 갖는 테이블을 꽉 채웁니다.
addressingHashTable.put("최", 5);꽉찬 테이블에 또 다른 Entry를 저장하게 되는 경우 기존 테이블을 확장함과 동시에 기존 값들을 재정렬합니다.
데이터 조회
public class Test {
public static void main(String[] args) {
AddressingHashTable<String, Integer> addressingHashTable = new AddressingHashTable<>(10);
addressingHashTable.put("김", 1);
addressingHashTable.put("나", 2);
addressingHashTable.put("박", 3);
addressingHashTable.put("이", 4);
System.out.println(addressingHashTable.get("김"));
System.out.println(addressingHashTable.get("나"));
System.out.println(addressingHashTable.get("박"));
System.out.println(addressingHashTable.get("이"));
addressingHashTable.display();
}
}
데이터 삭제
public class Test {
public static void main(String[] args) {
AddressingHashTable<String, Integer> addressingHashTable = new AddressingHashTable<>(10);
addressingHashTable.put("김", 1);
addressingHashTable.put("나", 2);
addressingHashTable.put("박", 3);
addressingHashTable.put("이", 4);
addressingHashTable.remove("김");
addressingHashTable.remove("나");
addressingHashTable.display();
}
}
값을 삭제하고 refresh()를 통해 해시 테이블의 값들의 위치를 재정렬합니다. 데이터를 삭제한 이후에 조회를 할 때 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업을 진행합니다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] LeetCode - Merge Sorted Array (0) | 2023.08.23 |
|---|