1. 해시 테이블(Hash Table)
테이블 자료구조란?
- 키(key)와 값(value)이 하나의 쌍을 이루어 저장되는 자료 구조
- 테이블에서 키는 고유값을 가지며, 키가 존재하지 않는 값은 저장 불가
- 키 값을 사용해 임의의 위치에 저장된 값에 접근 가능
: 탐색 시 시간복잡도는- 딕셔너리(dictionary) 또는 맵(map)으로도 지칭
해시 테이블 관련 주요 용어/개념 정리
해시 값(hash value) / 해시 코드(hash code)
- 키 값이 해시 함수를 통해 변환된 결과값
해시 함수(hash function)
- 넓은 범위에 분산된 키 값을 좁은 범위의 해시값으로 변경할 때 사용되는 단방향 함수
: 키 값으로 해시 값을 구하는 것은 가능하나, 그 역은 불가능- 일반적으로 나머지 연산에 기반한 연산을 사용
- 데이터 저장 공간을 낭비하지 않으면서 데이터를 저장할 위치를 설정 가능
해시 테이블(hash table)
- 해시 값을 인덱스로 사용하고 원래의 키 값을 저장하는 배열 형태의 자료구조
: 해시 값을 활용한 임의 접근 가능해싱(hashing)
- 해시 함수를 사용하여 데이터를 해시 테이블에 저장하고 검색하는 기법
버킷(bucket)
- 해시 테이블을 구성하는, 배열에서의 요소와 같은 부분
2. 충돌(Collision)
충돌이란?
- 서로 다른 키에 동일한 해시 함수를 사용하여 변환한 해시값이 서로 동일한 상황
: 해시 코드의 성능을 하락시키는 주된 원인- 해시 테이블에서는 데이터를 저장할 버킷이 서로 겹치는 현상
- 좋은 해시 함수일수록 고르게 분포된 해시 값을 갖기 때문에 충돌의 빈도가 낮음
충돌에 관한 주요 대안
체인법
체인법(chaining) / 닫힌 주소법(closed addressing) / 오픈 해시법(open hashing)
- 동일한 해시값을 갖는 데이터를 사슬 모양으로 연결 리스트에 연결하는 방법
: 해시 테이블은 배열, 데이터는 테이블의 각 버킷마다 연결 리스트 형태로 구현- Java 언어에서
HashMap클래스의 구현에 사용하는 자료구조
오픈 주소법
오픈 주소법(open addressing) / 닫힌 해시법(closed hashing)
- 해시 충돌이 발생했을 때 빈 버킷을 찾을 때까지 해시를 반복(rehashing)하는 방법
- 재해시하는 방식에 따라 선형 조사법, 이차 조사법 등으로 세분
- 각 버킷마다 충돌 여부를 식별 가능한 상태 정보가 필요
- 해시값이 같을 때, 충돌 발생 시 빈 버킷을 찾아 접근하는 위치가 항상 동일해지는 문제 발생
cf1) 선형 조사법(linear probing): 충돌이 발생한 해시값을 갖는 버킷의 칸 옆의 버킷을 검사
cf2) 이차 조사법(quadratic probing): 충돌이 발생한 해시값을 갖는 버킷의 칸 옆의 버킷을 검사
이중 해시
이중 해시(double hash)
- 충돌 발생 빈도를 낮추기 위해, 키를 해시값으로 변환할 때 2개의 해시 함수를 사용하는 방식
- 1차 해시 함수: 주어진 키로 저장 위치를 결정
- 2차 해시 함수: 키와 해시값을 활용하여 충돌 발생 시 다음에 접근할 버킷을 결정
- 아발란체 효과를 통해 오픈 주소법보다 충돌 발생 빈도를 줄일 수 있음
: 1차 해시 함수로 구한 해시값이 같아도, 키의 차이로 인해 2차 해시 함수로 재해시한 해시값이 크게 달라지기 때문
3. 해시 테이블 구현
- 전체 코드는 여기에서 확인 가능
해시 테이블의 핵심 기능 정의
TaskResult enum 클래스
package datastructure.hashtable;
// 해시테이블에서의 데이터 추가/삭제 결과를 명확히 드러내기 위해 사용
// 각각 작업 실패, 작업 성공, 해시테이블 가득 참을 의미
public enum TaskResult {
FAILED, SUCCESS, FULL
}HashTable 인터페이스
- 해시테이블에서의 데이터 추가/삭제 기능의 경우, 반환값으로 enum 클래스인
TaskResult를 사용하여 작업 수행 결과가 명확히 드러나게 했다.
package datastructure.hashtable;
public interface HashTable<K,V> {
int hashValue(K key); // 주어진 해시값에 관한 해시 테이블에서의 인덱스 번호 반환
V search(K key); // 주어진 키에 대응되는 값을 해시 테이블에서 탐색
TaskResult add(K key, V value); // 주어진 키와 값을 갖는 요소를 해시테이블에 추가
TaskResult remove(K key); // 주어진 키를 갖는 요소를 찾아 해시 테이블에서 삭제
boolean isEmpty(); // 해시 테이블이 비어 있는지 확인
void clear(); // 해시 테이블에 저장된 모든 요소 삭제
int getSize(); // 해시 테이블에 저장된 요소의 개수를 반환
void dump(); // 해시 테이블에 저장된 키-값 쌍을 모두 출력
}
체이닝을 적용한 해시 테이블 구현
ChainNode 클래스
package datastructure.hashtable;
public class ChainNode<K,V> {
private final K key; // 현재 노드의 키
private final V value; // 현재 노드의 값
private ChainNode<K,V> next; // 이 노드의 다음 노드를 참조하는 변수
// 주어진 키-값 쌍을 갖는 노드 생성
public ChainNode(K key, V value, ChainNode<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
// 이 노드에 저장된 키를 반환
public K getKey() {
return key;
}
// 이 노드에 저장된 값을 반환
public V getValue() {
return value;
}
// 이 노드의 다음 노드 변경
public ChainNode<K, V> getNext() {
return next;
}
// 이 노드의 다음 노드를 지정한 노드로 변경
public void setNext(ChainNode<K, V> next) {
this.next = next;
}
// 키의 해시 값을 반환
@Override
public int hashCode() {
return key.hashCode();
}
}ChainedHashTable 클래스
package datastructure.hashtable;
import java.util.Arrays;
import java.util.Objects;
public class ChainedHashTable<K,V> implements HashTable<K,V> {
private final int capacity; // 해시 테이블의 최대 용량
private final ChainNode<K,V>[] table; // 해시 테이블
private int size; // 해시 테이블에 저장된 노드의 개수
// 지정한 최대 용량을 갖는 해시 테이블 생성
public ChainedHashTable(int capacity) {
this.table = new ChainNode[capacity]; // 해시테이블 생성 및 최대 용량 초기화
this.capacity = capacity;
this.size = 0; // 테이블에 저장된 노드 개수 0으로 초기화
}
// 키의 해시값을 해시테이블에서의 인덱스로 변환
@Override
public int hashValue(K key) {
return key.hashCode() % capacity;
}
// 지정한 키를 갖는 노드를 해시테이블에서 찾아 그 값을 반환
@Override
public V search(K key) {
// 1. 지정한 키를 해시값에 따른 인덱스로 변환
int hash = hashValue(key);
// 2. 구한 해시값을 인덱스로 삼는 버킷을 선택 후 버킷이 가리키는 연결리스트를 탐색
ChainNode<K,V> node = table[hash];
while (node != null) {
// 3-1. 해당하는 노드 발견 시 그 값을 반환하고 종료
if (node.getKey().equals(key)) {
return node.getValue();
}
// 3-2. 해당하는 노드가 아니면 현재 인덱스의 다음 노드 탐색
node = node.getNext();
}
// 지정한 키에 해당하는 노드가 존재하지 않음
return null;
}
// 주어진 키-값 쌍을 갖는 새 노드를 해시테이블에 저장
@Override
public TaskResult add(K key, V value) {
// 1. 주어진 키를 해시값으로 변환
int hash = hashValue(key);
// 2. 구한 해시값을 인덱스로 삼는 버킷을 선택 후 해당 버킷의 연결리스트 탐색
ChainNode<K,V> node = table[hash];
while (node != null) {
// 3-1. 이미 등록된 키면 노드 추가 없이 그대로 종료
if (node.getKey().equals(key)) {
return TaskResult.FAILED;
}
// 3-2. 연결리스트의 다음 노드 탐색
node = node.getNext();
}
// 4. 연결리스트에 없는 키면 리스트의 맨 앞에 노드 삽입
ChainNode<K,V> temp = new ChainNode<>(key, value, table[hash]);
table[hash] = temp;
// 5. 해시 테이블에 저장된 노드의 개수 1 증가
size++;
return TaskResult.SUCCESS;
}
@Override
public TaskResult remove(K key) {
// 1. 주어진 키를 해시값으로 변환
int hash = hashValue(key);
// 2. 해시값을 인덱스로 삼는 버킷을 선택 후 해당 연결리스트에서 삭제할 노드 탐색
ChainNode<K,V> node = table[hash];
ChainNode<K,V> prev = null;
while (node != null) {
// 3-1. 삭제할 노드를 발견한 경우 연결 리스트에서 해당 노드를 제거
if (node.getKey().equals(key)) {
if (prev == null) {
table[hash] = node.getNext(); // 삭제할 노드가 맨 앞 노드
} else {
prev.setNext(node.getNext()); // 삭제할 노드가 맨 앞 노드가 아님
}
// 4-1. 해시 테이블에 저장된 노드의 개수를 1 감소시킨 후 종료
size--;
return TaskResult.SUCCESS;
}
// 발견하지 못한 경우 현재 노드와 그 이전 노드를 갱신
prev = node;
node = node.getNext();
}
// 삭제할 노드가 해시테이블에 없음
return TaskResult.FAILED;
}
// 빈 해시 테이블인지 확인
@Override
public boolean isEmpty() {
return size == 0 && Arrays.stream(table).allMatch(Objects::isNull);
}
// 해시테이블에 저장된 노드의 개수를 반환
@Override
public int getSize() {
return size;
}
// 해시테이블에 저장된 모든 노드 삭제
@Override
public void clear() {
System.out.println("Clearing hash table...");
for (int i = 0; i < capacity; i++) {
ChainNode<K,V> node = table[i];
while (node != null) {
remove(node.getKey());
node = node.getNext();
}
}
System.out.println("Hash table cleared.");
}
// 해시테이블에 저장된 모든 키-값 쌍 출력
@Override
public void dump() {
for (int i = 0; i < capacity; i++) {
ChainNode<K,V> node = table[i];
System.out.printf("[%02d] ", i);
while (node != null) {
System.out.printf("→ %s (%s) ", node.getKey(), node.getValue());
node = node.getNext();
}
System.out.println();
}
}
}실행용 샘플 코드 및 실제 실행 결과
package datastructure.hashtable;
public class ChainedHashTableMain {
public static void main(String[] args) {
HashTable<Integer, String> hashTable = new ChainedHashTable<>(6);
// 1. 해시 테이블에 여러 개의 키-값 쌍을 저장한 후 그 저장 결과를 출력
hashTable.add(900254, "Lee");
hashTable.add(900139, "Jack");
hashTable.add(900827, "David");
hashTable.add(900653, "Mary");
hashTable.add(900745, "John");
hashTable.add(900841, "Ann");
System.out.println("Print hash table:");
hashTable.dump();
System.out.printf("Hash table node count: %d\n", hashTable.getSize());
System.out.println();
// 2. 해시테이블에서 지정한 키에 대응되는 값 검색
System.out.printf("searching ID %d...\n", 900139);
String name = hashTable.search(900139);
if (name != null) {
System.out.printf("ID %d is %s.\n", 900139, name);
} else {
System.out.printf("ID %d is not found.\n", 900139);
}
System.out.printf("searching ID %d...\n", 901456);
name = hashTable.search(901456);
if (name != null) {
System.out.printf("ID %d is %s.\n\n", 901456, name);
} else {
System.out.printf("ID %d is not exist.\n\n", 901456);
}
// 4. 해시 테이블에 저장된 일부 데이터 삭제
System.out.println("Delete some ID...");
if (hashTable.remove(900841) == TaskResult.FAILED) {
System.out.printf("ID %d is not exist.\n", 900841);
} else {
System.out.printf("ID %d is removed.\n", 900841);
}
if (hashTable.remove(900745) == TaskResult.FAILED) {
System.out.printf("ID %d is not exist.\n", 900745);
} else {
System.out.printf("ID %d is removed.\n", 900745);
}
if (hashTable.remove(901456) == TaskResult.FAILED) { // 해시테이블에 존재하지 않는 키
System.out.printf("ID %d is not exist.\n", 901456);
} else {
System.out.printf("ID %d is removed.\n", 901456);
}
System.out.println("Print hash table after removal:");
hashTable.dump();
System.out.printf("Hash table node count: %d\n", hashTable.getSize());
System.out.println();
// 5. 해시 테이블에 저장된 모든 데이터 삭제
hashTable.clear();
System.out.println("Print hash table after clearing:");
hashTable.dump();
System.out.printf("Hash table node count: %d\n", hashTable.getSize());
}
}
오픈 주소법을 적용한 해시 테이블 구현
BucketStatus enum
package datastructure.hashtable;
// 오픈 주소법에서 버킷의 현재 상태를 나타내기 위해 사용
// 각각 데이터 저장, 빈 상태, 삭제 완료된 상태를 의미
public enum BucketStatus {
OCCUPIED, EMPTY, DELETED
}Bucket 클래스
package datastructure.hashtable;
public class Bucket<K,V> {
private K key; // 버킷에 저장될 키 값
private V value; // 키에 대응되는 데이터
private BucketStatus stat; // 버킷의 데이터 저장 상태
// 해시테이블의 버킷은 항상 빈 상태로 생성
public Bucket() {
this.stat = BucketStatus.EMPTY;
}
// 지정한 키-값 쌍을 버킷에 저장하고, 버킷의 현재 상태를 변경
public void set(K key, V value, BucketStatus stat) {
this.key = key;
this.value = value;
this.stat = stat;
}
// 버킷의 데이터 저장 상태만을 변경
public void setStat(BucketStatus stat) {
this.stat = stat;
}
// 버킷에 저장된 키를 반환
public K getKey() {
return key;
}
// 버킷에 저장된 데이터를 반환
public V getValue() {
return value;
}
// 버킷의 데이터 저장 상태를 반환
public BucketStatus getStat() {
return stat;
}
// 현재 키의 해시값을 반환
@Override
public int hashCode() {
return key.hashCode();
}
}OpenHashTable 클래스
package datastructure.hashtable;
import java.util.Arrays;
public class OpenHashTable<K,V> implements HashTable<K,V> {
private final int capacity; // 해시 테이블의 최대 용량
private int size; // 해시 테이블에 저장된 노드의 개수
private final Bucket<K,V>[] table; // 해시 테이블
// 지정한 용량을 갖는 해시 테이블 생성
public OpenHashTable(int capacity) {
this.table = new Bucket[capacity];
for (int i = 0; i < capacity; i++) {
this.table[i] = new Bucket<>();
}
this.capacity = capacity;
}
// 해시값을 인덱스로 변환
@Override
public int hashValue(K key) {
return key.hashCode() % capacity;
}
// 해시 충돌 발생 시 재해시 수행(선형 탐사법 사용)
public int rehashValue(int hash) {
return (hash + 1) % capacity; // 해시 충돌 발생 시 다음에 접근할 버킷
}
// 주어진 키를 갖는 노드 검색
private Bucket<K,V> searchNode(K key) {
// 1. 주어진 키를 변환한 해시값을 인덱스로 갖는 버킷을 선택
int hash = hashValue(key);
Bucket<K,V> node = table[hash];
// 2. 해시테이블에서 주어진 키를 갖는 버킷 탐색
for (int i = 0; node.getStat() != BucketStatus.EMPTY && i < capacity; i++) {
// 3-1. 데이터가 유효하면서 주어진 키를 갖는 버킷일 경우 해당 버킷을 반환
if (node.getStat() == BucketStatus.OCCUPIED && node.getKey().equals(key)) {
return node;
}
// 3-2. 찾는 버킷이 아닌 경우 재해싱을 통해 다음에 탐색할 버킷을 지정
hash = rehashValue(hash);
node = table[hash];
}
// 탐색 실패
return null;
}
@Override
public V search(K key) {
// 주어진 키에 해당하는 노드를 찾으면 그 노드의 값을 반환
// (탐색 실패 시 null 반환)
Bucket<K,V> node = searchNode(key);
return node != null ? node.getValue() : null;
}
@Override
public TaskResult add(K key, V value) {
// 1-1. 해시 테이블에 이미 등록된 키인 경우 그대로 종료
if (searchNode(key) != null) {
return TaskResult.FAILED;
}
// 1-2. 새로운 키인 경우, 해당 키에 관한 해시값을 인덱스로 삼는 버킷을 선택
int hash = hashValue(key);
Bucket<K,V> node = table[hash];
// 2. 새로운 키-값 쌍을 저장할 버킷 탐색
for (int i = 0; i < capacity; i++) {
// 3-1. 버킷에 데이터가 없거나 충돌로 인해 데이터가 삭제되었을 경우
// 해당 버킷에 주어진 키-값 쌍을 저장하고 그 상태를 변경
if (node.getStat() != BucketStatus.OCCUPIED) {
node.set(key, value, BucketStatus.OCCUPIED);
// 3-1. 해시테이블에 저장된 데이터 쌍의 개수를 1 증가시키고 종료
size++;
return TaskResult.SUCCESS;
}
// 3-2. 데이터를 저장 불가능한 버킷이면 재해싱으로 다음에 접근할 버킷을 지정
hash = rehashValue(hash);
node = table[hash];
}
// 더 이상 새로운 데이터 저장 불가
return TaskResult.FULL;
}
@Override
public TaskResult remove(K key) {
// 1. 주어진 키를 갖는 버킷를 해시테이블에서 검색
Bucket<K,V> node = searchNode(key);
// 2-1. 해당하는 버킷이 없으면 그대로 종료
if (node == null) {
return TaskResult.FAILED;
}
// 2-2. 해당하는 버킷의 상태를 삭제 상태로 변경
node.setStat(BucketStatus.DELETED);
// 3. 해시테이블의 키-값 쌍의 개수를 1 감소시키고 종료
size--;
return TaskResult.SUCCESS;
}
// 빈 해시테이블이 되는 조건
@Override
public boolean isEmpty() {
return size == 0
&& Arrays.stream(table).noneMatch(bucket -> bucket.getStat() == BucketStatus.OCCUPIED);
}
// 각 버킷마다 저장된 데이터를 모두 지우고 빈 상태로 변경
@Override
public void clear() {
Arrays.stream(table).forEach(bucket -> bucket.set(null, null, BucketStatus.EMPTY));
size = 0;
}
// 해시테이블에 저장된 키-값 쌍의 개수 반환
@Override
public int getSize() {
return size;
}
// 해시테이블에 저장된 모든 키-값 쌍과 각 버킷의 상태 출력
@Override
public void dump() {
for (int i = 0; i < capacity; i++) {
System.out.printf("[%02d] ", i);
switch (table[i].getStat()) {
case OCCUPIED:
System.out.printf("%s (%s)\n", table[i].getKey(), table[i].getValue());
break;
case DELETED:
System.out.println("--- 삭제 마침 ---");
break;
case EMPTY:
System.out.println("--- 미등록 ---");
break;
}
}
}
}실행용 샘플 코드 및 실제 실행 결과
package datastructure.hashtable;
public class OpenHashTableMain {
public static void main(String[] args) {
OpenHashTable<Integer, String> hashTable = new OpenHashTable<>(13);
// 1. 데이터 추가 후 결과 출력
hashTable.add(1, "Kim");
hashTable.add(14, "Bob");
hashTable.add(5, "Jack");
hashTable.add(17, "Lily");
hashTable.add(9, "Tom");
hashTable.add(12, "Jack");
hashTable.add(13, "John");
System.out.println("Print hash table:");
hashTable.dump();
System.out.printf("Hash table node count: %d\n", hashTable.getSize());
System.out.println();
// 2. 데이터 삭제 후 결과 출력
System.out.println("Delete some ID...");
if (hashTable.remove(12) == TaskResult.SUCCESS) {
System.out.printf("Successfully deleted ID %d\n", 12);
} else {
System.out.printf("Failed to delete ID %d\n", 12);
}
if (hashTable.remove(5) == TaskResult.SUCCESS) {
System.out.printf("Successfully deleted ID %d\n", 5);
} else {
System.out.printf("Failed to delete ID %d\n", 5);
}
if (hashTable.remove(6) == TaskResult.SUCCESS) {
System.out.printf("Successfully deleted ID %d\n", 6);
} else {
System.out.printf("Failed to delete ID %d\n", 6);
}
System.out.println();
System.out.println("Print hash table:");
hashTable.dump();
System.out.printf("Hash table node count: %d\n", hashTable.getSize());
}
}
Reference
- Do-it! 자료구조와 함께 배우는 알고리즘 입문(Bohyoh Shibata 지음, 강민 옮김)
- 윤성우의 열혈 자료구조(윤성우 지음)
- 자바의 정석 3판(남궁성 지음)
