1. 개념
각 위치(슬롯)마다 주소가 부여되어 있는 저장공간
- 탐색 키값을 활용하여 해시 테이블의 주소를 계산
→ 원하는 데이터를 해시 테이블에서 직접적이고 빠르게 탐색할 수 있음 - 브루트 포스(완전 탐색)로는 시간초과에 빠지는 경우에 적용
1-1. 해싱(hashing)
- 해시 테이블을 이용하는 방법
- 특정 키값을 갖는 데이터를 데이터를 찾는 문제에 가장 적합한 형태의 탐색 방법
- 다음 형태의 문제에는 적합하지 않음
- 어떤 범위에 속하는 키값을 가진 모든 데이터를 탐색하는 문제
- 최대 또는 최소의 키값을 가진 데이터를 찾는 문제
- 키값의 순서대로 데이터를 방문하는 형태의 문제
2. 구현
2-1. 충돌(collision)
저장할 버킷이 중복되는 현상
- 키 값과 해시 값의 대응 관계가 반드시 1:1이라는 보증이 없다(보통 n:1).
- 해시 함수가 가능하면 해시 값이 치우치지 않도록 고르게 분포된 값을 만들어야 한다.
2-2. 대처 방법
2-2-1. 체인법(chaining) = 오픈 해시법(open hashing)
같은 값을 갖는 데이터를 쇠사슬(chain) 모양으로 연결 리스트에서 연결하는 방법
- 배열의 각 버킷(해시 테이블)에 저장하는 값은 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째 노드에 대한 참조
- 데이터가 존재하지 않는 버킷의 값은 null을 가리킴
public class ChainHash<K,V> {
/**
* 해시 구성 노드
*/
class Node<K,V> {
private K key; // 키 값
private V value; // 데이터
private Node<K,V> nextNode; // 참조하는 다음 노드
/**
* 생성자
*/
Node(K key, V value, Node<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
}
/**
* 키 값 반환 메서드
*/
K getKey() {
return key;
}
/**
* 데이터 반환 메서드
*/
V getValue() {
return value;
}
/**
* 키의 해시 값 반환 메서드
*/
public int hashCode() {
return key.hashCode();
}
}
private int size; // 해시 테이블 크기
private Node<K,V>[] table; // 해시 테이블
/**
* 생성자
* - 호출 직후 배열 table의 모든 요소는 null을 참조
* - 즉, 모든 버킷이 비어있는 상태가 됨
*/
public ChainHash(int capacity) {
try {
table = new Node[capacity];
this.size = capacity;
} catch(OutOfMemoryError e) {
this.size = 0;
}
}
/**
* 해시 값을 구하는 메서드
*/
public int hashValue(Object key) {
return key.hashCode() % size;
}
/**
* 키 값 key를 갖는 요소 검색 메서드(데이터 반환)
* -
*/
public V search(K key) {
int hash = hashValue(key); // 검색할 데이터의 해시 값
Node<K,V> currentNode = table[hash]; // 선택한 노드
while(currentNode != null) {
if(currentNode.getKey().equals(key)) {
return currentNode.getValue(); // 검색 성공
}
currentNode = currentNode.next; // 다음 노드 가리키기
}
return null; // 검색 실패
}
/**
* 키 값 key, 데이터 value를 갖는 요소 추가 메서드
*/
public int add(K key, V value) {
int hash = hashValue(key); // 추가할 데이터의 해시 값
Node<K,V> currentNode = table[hash]; // 선택한 노드
while(currentNode != null) {
// 이미 등록된 키 값인 경우
if(currentNode.getKey().equals(key)) {
return 1;
}
currentNode = currentNode.next; // 다음 노드 가리키기
}
Node<K,V> temporary = new Node<K,V>(key, value, table[hash];
table[hash] = temporary; // 노드 삽입
return 0;
}
/**
* 키 값 key를 갖는 요소를 삭제하는 메서드
*/
public int remove(K key) {
int hash = hashValue(key); // 삭제할 데이터의 해시 값
Node<K,V> currentNode = table[hash]; // 선택한 노드
Node<K,V> preNode = null; // 바로 앞의 선택 노드
while(currentNode != null) {
// 찾은 경우
if(currentNode.getKey().equals(key)) {
if(preNode == null) {
table[hash] = currentNode.next;
} else {
preNode.next = currentNode.next;
}
return 0;
}
preNode = currentNode;
currentNode = currentNode.next; // 다음 노드 가리키기
}
return 1; // 해당 키 값이 없음
}
}2-2-1-1. 생성자 ChainHash
비어 있는 해시 테이블 생성
- 요솟수가
capacity인 배열table의 본체를 생성하고capacity값을 필드size에 복사 - 해시 테이블의 각 버킷은 맨 앞부터 접근 가능
ex) table[0] table[1], ..., table[size - 1] - 생성자가 호출된 직후 배열
table의 모든 요소는 null을 참조(모든 버킷이 비어있는 상태)- 버킷이
Node<K,V>에 대한 참조형이므로, 참조형 배열인table의 초기 설정값이 널 참조가 됨
- 버킷이
2-2-1-2. search 메서드
키 값이
key인 요소를 검색하는 메서드
✅ 검색 과정
1. 해시 함수가 키 값을 해시 값으로 변환한다.
2. 해시 값을 인덱스로 하는 버킷을 선택한다.
3. 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색한다.
3-1. 키 값과 같은 값을 찾은 경우 → 검색 성공
예시) 검색하려는 값 : 33, 해시 값 : 7
table[7]이 가리키는 연결 리스트를 하나씩 끌어당기며 검색하다가 해당 값을 찾음3-2. 끝까지 스캔하여 찾지 못한 경우 → 검색 실패
예시) 검색하려는 값 : 26, 해시 값 : 0
table[0]이 null이므로 검색 실패2-2-1-3. add 메서드
키 값이
key이고 데이터가value인 요소를 삽입하는 메서드
✅ 과정
1. 해시 함수가 키 값을 해시 값으로 변환한다.
2. 해시 값을 인덱스로 하는 버킷을 선택한다.
3. 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색한다.
3-1. 키 값과 같은 값을 찾은 경우 → 키 값이 이미 등록된 상태(실패)
3-2. 끝까지 스캔하여 찾지 못한 경우 → 리스트의 맨 앞 위치에 노드 삽입
2-2-1-4. remove 메서드
키 값이
key인 요소를 삭제하는 메서드
✅ 과정
1. 해시 함수가 키 값을 해시 값으로 변환한다.
2. 해시 값을 인덱스로 하는 버킷을 선택한다.
3. 선택한 버킷의 연결 리스트를 처음부터 순서대로 검색한다.
3-1. 키 값과 같은 값을 찾은 경우 → 해당 노드를 리스트에서 삭제
3-2. 끝까지 스캔하여 찾지 못한 경우 → 삭제 실패
2-2-2. 오픈 주소법(open addressing) = 닫힌 해시법(closed hashing)
충돌이 발생했을 때 재해시(refrashing)를 수행하여 비어 있는 버킷을 찾아내는 방법
public class OpenHash<L,V> {
/**
* 버킷 상태
* - {데이터 저장, 비어있음, 삭제 마침}
*/
enum Status {OCCUPIED, EMPTY, DELETED};
/**
* 버킷 클래스
*/
static class Bucket<K,V> {
private K key; // 키 값
private V value; // 데이터
private Status status; // 상태
/**
* 생성자
*/
Bucket() {
status = Status.EMPTY; // 버킷은 비어있는 상태
}
/**
* 모든 필드에 값을 설정하는 메서드
*/
void set(K key, V value, Status status) {
this.key = key; // 키 값
this.value = value; // 데이터
this.status = status; // 상태
}
/**
* 상태를 설정하는 메서드
*/
void setStatus(Status status) {
this.status = status;
}
/**
* 키 값을 반환하는 메서드
*/
K getKey() {
return key;
}
/**
* 데이터를 반환하는 메서드
*/
v getValue() {
return value;
}
/**
* 키의 해시 값을 반환하는 메서드
*/
public int hashCode() {
return key.hashCode();
}
}
private int size; // 해시 테이블 크기
private Bucket<K,V>[] table; // 해시 테이블
/**
* 생성자
*/
public OpenHash(int size) {
try {
table = new Bucket[size];
for(int index = 0; index < size; index++) {
table[index] = new Bucket<K,V>();
}
this.size = size;
} catch(OutOfMemoryError e) { // 테이블 생성 불가
this.size = 0;
}
}
/**
* 해시 값을 구하는 메서드
*/
public int hashValue(Object key) {
return key.hashCode() % size;
}
/**
* 재해시 값을 구하는 메서드
*/
public int rehashValue(int hash) {
return (hash + 1) % size;
}
/**
* 키 값 key를 갖는 버킷을 검색하는 메서드
*/
private Bucket<K,V> searchNode(K key) {
int hash = hashValue(key); // 검색할 데이터의 해시 값
Bucket<K,V> currentNode = table[hash]; // 선택한 버킷
for(int index = 0;
currentNode.status != Status.EMPTY && index < size;
index++
) {
if(currentNode.status == Status.OCCUPIED && currentNODE.getKey().equals(key)) {
return currentNode;
}
hash = rehashValue(hash); // 재해시
currentNode = table[hash];
}
return null;
}
/**
* 키 값 key를 갖는 요소를 검색하는 메서드(데이터 반환)
*/
public V search(K key) {
Bucket<K,V> currentNode = searchNode(key);
if(currentNode != null) {
return currentNode.getValue();
} else {
return null;
}
}
/**
* 키 값 key, 데이터 value를 갖는 요소를 추가하는 메서드
*/
public int add(K key, V value) {
if (search(key) != null) {
return 1; // 키 값이 이미 등록되어 있음
}
int hash = hashValue(key); // 추가할 데이터의 해시 값
Bucket<K,V> p = table[hash]; // 선택한 버킷
for(int index = 0; index < size; index++) {
if(currentNode == Status.EMPTY || currentNode == Status.DELETED) {
currentNode.set(key, value, Status.OCCUPIED);
return 0;
}
hash = rehashValue(hash); // 재해시
currentNode = table[hash];
}
return 2; // 해시 테이블이 가득 참
}
/**
* 키 값 key를 갖는 요소를 삭제하는 메서드
*/
public int remove(K key) {
Bucket<K,V> currentNode = searchNode(key); // 선택한 버킷
if(currentNode == null) {
return 1; // 등록되지 않은 키 값임
}
currentNode.setStatus(Status.DELETED);
return 0;
}
}2-2-2-1. 요소 삽입
- 새로운 값을 삽입하고자 할 때 충돌이 발생한 경우, 재해시 사용
- 재해시 수행 시 해시 메서드는 자유롭게 결정할 수 있음
- 빈 버킷을 만날 때까지 재해시를 여러 번 반복함 → 선형 탐사법(linear probing)
2-2-2-2. 요소 삭제
-
인덱스에 해당하는 버킷의 데이터
a를 삭제하는 경우, 같은 해시 값을 갖는 다른 데이터b를 검색할 때 데이터b가 존재하지 않는다고 생각하게 됨(검색 실패)
→ 버킷에 대한 속성 부여 필요속성 설명 비고 OCCUPIED 데이터 저장 EMPTY 비어 있음 같은 해시 값의 데이터가 존재하지 않음 DELETED 삭제 마침 같은 해시 값의 데이터가 다른 버킷에 저장되어 있음
2-2-2-3. 요소 검색
- 해시 값의 속성값이 비어 있음인 경우 → 검색 실패
- 해시 값의 속성값이 삭제 마침인 경우 → 재해시 수행하여 원하는 값이 나올 때까지 재검색
- 해시 값의 속성값이 데이터 저장인 경우 → 검색 성공
3. 성능 분석
3-1. 평균 시간 복잡도
- 충돌이 전혀 발생하지 않는다는 전제가 필요
- 해시 함수로 인덱스를 찾는 것만으로 검색, 추가, 삭제가 거의 완료
| 항목 | 복잡도 |
|---|---|
| 삽입 | O(1) |
| 삭제 | O(1) |
| 검색 | O(1) |
3-2. 최악 시간 복잡도
해시 함수가 모든 키를 동일한 해시 값으로 매핑하여 모든 항목이 하나의 버킷에 저장되는 경우
| 항목 | 복잡도 |
|---|---|
| 삽입 | O(n) |
| 삭제 | O(n) |
| 검색 | O(n) |
4. 주의사항
- 충돌을 최소화하고 키를 균등하게 분포시켜야 한다.
- 해시 테이블의 크기는 소수로 정하는 것이 좋다.
- 너무 작으면 충돌이 많아진다.
- 너무 크면 공간 낭비가 발생한다.
5. 용어정리
| 항목 | 설명 |
|---|---|
| 해시 테이블 (hash table) | 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열 |
| 해시 함수 (hash function) | 키 값을 가지고 해시 값을 만드는 과정 |
| 버킷(bucket) | 해시 테이블의 각 요소 |
📖 참고
- 이관용·김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원
- Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱
기쁘게 코딩하고 싶은 백엔드 개발자