해시 테이블은 여러 프로그래밍 언어에서 해시(Hash), 맵(Map), 해시맵(HashMap), 딕셔너리(Dictionary) 등 다양한 이름으로 불린다. 이름에서 알 수 있듯이 해시(Hash)와 테이블(Table)이라는 두 가지 핵심 개념이 결합된 자료구조이다. 해시 테이블은 데이터 검색, 삽입, 삭제에 있어서 좋은 성능을 자랑하며, 많은 프로그래밍 언어의 내부 자료구조로 활용된다.
테이블(Table)의 개념
일상생활에서 흔히 보는 표는 어떤 내용을 일정한 형식, 순서에 따라 나타낸 것이다. 예를 들어, 직원들의 사번과 이름을 정리한 표가 있다
| 사번 | 이름 |
| 1 | 홍길동 |
| 2 | 임꺽정 |
| 3 | 김철수 |
이러한 표(테이블)는 프로그래밍에서 데이터를 저장하는 방식의 기본 아이디어가 된다. 특정 ‘키(Key)’를 통해 ‘값(Value)’을 찾아내는 구조이다
배열을 이용한 테이블의 한계
2002 월드컵 대한민국 국가대표 선수 명단을 예시로 들어보자. 선수들의 등번호(Key)와 이름(Value)이 담긴 테이블이다
| 등번호 | 이름 |
| 1 | 이운재 |
| 4 | 최진철 |
| 20 | 홍명보 |
| 6 | 유상철 |
| 22 | 송종국 |
| 21 | 박지성 |
| 5 | 김남일 |
| 10 | 이영표 |
| 8 | 최태욱 |
| 9 | 설기현 |
| 14 | 이천수 |
이 데이터를 배열에 저장하는 가장 직관적인 방법은 배열의 인덱스를 등번호로 가정하고, 해당 인덱스에 선수의 이름을 저장하는 것이다
인덱스 ↔ 데이터 배열[1] = "이운재" 배열[4] = "최진철" 배열[20] = "홍명보"
이 방식은 등번호만 알면 O(1)의 시간 복잡도로 선수의 이름을 바로 찾아낼 수 있다는 장점이 있다. 하지만 치명적인 단점 또한 존재한다.
등번호 22번까지 있는데, 만약 등번호 99번 선수가 있다면?
배열의 크기는 최소 100번(0번부터 99번까지)이 되어야 한다. 1번, 4번, 5번, 6번…22번 등 일부 인덱스에만 데이터가 저장되고, 2번, 3번, 7번, 23~98번 등 중간중간에 많은 빈 공간이 발생하여 메모리가 낭비된다. 이는 효율적인 자료구조라고 할 수 없다.
해시 함수(Hash Function)의 등장
컴퓨터 과학자들은 이러한 메모리 낭비 문제를 해결하기 위해 고민했다. “어떻게 하면 데이터를 정해진 작은 범위의 인덱스에 효율적으로 저장할 수 있을까?” 그 결과, 키를 입력받아 배열의 유효한 인덱스(주소)를 계산해주는 특별한 함수를 고안했는데, 이것이 해시 함수(Hash Function)이다.
해시 함수는 임의의 크기를 가진 데이터를 고정된 크기의 값(해시 값 또는 해시 코드)으로 매핑한다. 이 해시 값을 배열의 인덱스로 사용하여 데이터를 저장하는 방식이 해시 테이블이다.
해시 함수: key % 10 (키를 10으로 나눈 나머지)
이 해시 함수를 사용하여 선수들의 등번호를 0부터 9까지의 인덱스에 매핑하여 저장하는 과정을 살펴본다
- 1번 이윤재: 1 % 10 = 1. 인덱스 1에 저장
- 4번 최진철: 4 % 10 = 4. 인덱스 4에 저장
- 10번 이영표: 10 % 10 = 0. 인덱스 0에 저장
- 6번 유상철: 6 % 10 = 6. 인덱스 6에 저장
이러한 방식으로 해시 함수를 통해 테이블의 인덱스를 새로 만들어 데이터를 저장하기 때문에 ‘해시 테이블’이라는 이름이 붙었다. 해시 테이블은 등번호(키)만 알면 O(1)의 성능으로 선수의 이름(값)을 읽을 수 있을 뿐만 아니라, 삽입, 수정, 삭제까지 평균적으로 O(1)의 강력한 성능을 가진다
해시 충돌(Hash Collision)
하지만 지금까지 확인해본 해시 테이블의 원리에는 한 가지 중요한 문제가 있다. 바로 해시 충돌이다. 축구선수의 등번호를 key % 10 해시 함수를 이용하여 배열의 인덱스를 구했다. 여기에 21번 박지성 선수를 넣어보자
- 21번 박지성: 21 % 10 = 1. 인덱스 1에 저장
그런데 인덱스 1에는 이미 이운재 선수가 저장되어 있다. 이처럼 서로 다른 키가 동일한 해시 값을 생성하여 같은 인덱스에 매핑될 때 ‘충돌이 발생했다’고 말한다. 충돌이 발생했을 때 단순히 둘 중 하나를 버릴 수는 없다. 이를 해결하기 위한 여러 방법이 있는데, 가장 보편적인 방법 중 하나가 바로 체이닝(Chaining)이다
체이닝 방식의 충돌 해결
충돌이 발생한 해당 인덱스를 연결 리스트(Linked List)로 구성하여 데이터를 연결한다. 이렇게 하면 기존에 있던 선수와 새로 들어온 선수를 모두 같은 인덱스에 저장할 수 있게 된다
- 10 이영표 (해시 값: 0) -> 배열[0]에 저장
- 1 이운재 (해시 값: 1) -> 배열[1]에 저장
- 21 박지성 (해시 값: 1) -> 배열[1]에 충돌 발생. 배열[1]의 연결 리스트에 박지성 추가
데이터 조회 과정
만약 키 21번으로 읽기 요청을 하면
- 해시 함수를 거쳐 21 % 10 = 1. 배열의 1번 인덱스에 접근한다
- 1번 인덱스에는 연결 리스트로 이운재와 박지성 데이터가 저장되어 있다
- 연결 리스트를 차례대로 순회하면서 요청된 키(21)와 일치하는 데이터를 찾는다. (이운재의 키는 1, 박지성의 키는 21)
- 박지성의 데이터를 찾아 반환한다
체이닝 방식의 한계
이때, 충돌이 많이 발생하여 연결 리스트의 길이가 길어지면 데이터 조회 시 O(N)의 성능을 가지게 된다. 예를 들어, 등번호가 1번, 11번, 21번, 41번인 선수들이 모두 인덱스 1에 저장되어 있다고 가정해보자. 이 상태에서 41번 선수를 참조하고 싶다면, 해시 함수를 거쳐 인덱스 1의 연결 리스트를 참조한 뒤, 연결 리스트를 처음부터 끝까지 순회해아 한다. 이는 일반 연결 리스트에서 데이터를 찾는 것과 다름없어 O(N)의 성능을 보이게 된다.
좋은 해시 함수의 중요성
따라서 해시 테이블의 성능은 해시 함수의 선정이 굉장히 중요하다. 좋은 해시 함수는 데이터를 균등하게 분배시켜 충돌 발생 횟수를 최소화해야 한다. 예시로 0부터 9까지 인덱스에 데이터가 고르게 분산되도록 하는 함수가 좋은 해시 함수라고 할 수 있다
해시 테이블의 장점과 단점
장점
- 빠른 데이터 읽기, 삽입, 삭제: 평균적으로 O(1)의 시간 복잡도를 가진다. 이는 데이터 양이 많아져도 성능 저하가 거의 없음을 의미한다
단점
- 공간 효율성: 해시 테이블은 미리 일정한 크기의 버킷을 확보하므로, 모든 버킷이 채워지지 않으면 공간 낭비가 발생할 수 있다
- 해시 함수의 중요성: 해시 함수의 성능이 해시 테이블 전체의 성능에 지대한 영향을 미친다. 좋은 해시 함수를 구현하는 것이 필수적이며, 이는 때로는 복잡할 수 있다
- 순서 보장 안 됨: 해시 테이블은 데이터의 삽입 순서를 보장하지 않는다
해시 테이블의 추상 자료형 (ADT)
- set(key, value): 해시 테이블에 특정 key와 value 쌍의 데이터를 삽입한다. 이미 key가 존재하면 value를 업데이트한다
- get(key): 해당 key에 해당하는 value를 찾아 반환한다. key가 없으면 null을 반환한다
- remove(key): 해당 kye와 value 쌍의 데이터를 제거한다
이중 연결 리스트(DoublyLinkedList)를 활용한 해시 테이블 구현
HashData 클래스
/**
* 해시 테이블에 저장될 키-값 쌍을 나타내는 클래스
* 각 노드에 저장될 실제 데이터이다
*
* @param<K> 키의 타입
* @param<T> 값의 타입
*/
public class HashData<K, V> {
private K key;
private V value;
/**
* HashData 생성자
* @param key 키
* @param value 값
*/
public HashData(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setKey(K key) {
this.key = key;
}
public void setValue(V value) {
this.value = value;
}
@Override
public String toString() {
return "HashData{key=" + key + ", value='" + value + "'}";
}
}
HashTable 클래스
/**
* 체이닝 방식으로 충돌을 해결하는 해시 테이블 구현
*
* 구조
* - 10개의 버킷(배열)으로 구성
* - 각 버킷은 이중 연결 리스트를 사용하여 충돌 처리
* - 해시 함수: key % 10
*
* 시간 복잡도
* - 평균: O(1) for set, get, remove
* - 최악: O(n) (모든 데이터가 하나의 버킷에 몰릴 경우)
*
* @param <K> 키의 타입
* @param <V> 값의 타입
*/
public class HashTable<K, V> {
private DoublyLinkedList<HashData<K, V>>[] arr; // 10개의 버킷, 각각 연결 리스트
private static final int TABLE_SIZE = 10; // 해시 테이블 크기
/**
* 해시 테이블 생성자
* 10개의 버킷을 생성하고 각 버킷을 빈 이중 연결리스트로 초기화한다
*/
@SuppressWarnings("unchecked")
public HashTable() {
// 제네릭 배열 생성 (제네릭 배열을 직접 생성할 수 없으므로 형변환 필요)
this.arr = (DoublyLinkedList<HashData<K, V>>[]) new DoublyLinkedList[TABLE_SIZE];
// 각 버킷을 빈 이중 연결 리스트로 초기화
for (int i = 0; i < TABLE_SIZE; i++) {
this.arr[i] = new DoublyLinkedList<>();
}
}
/**
* 해시 함수
* 키를 해시 테이블의 인덱스(0~9)로 변환한다
*
* 동작 원리
* 1. key.hashCode()로 정수 해시 값 생성
* 2. Math.abs()로 음수를 양수로 변환
* 3. TABLE_SIZE로 나눈 나머지를 인덱스로 사용
*
* @param key 해시할 키
* @return 0부터 TABLE_SIZE-1까지의 인덱스
*/
private int hashFunction(K key) {
// hashCode()는 음수가 될 수 있으므로 절대값 사용
return Math.abs(key.hashCode()) % TABLE_SIZE;
}
/**
* 해시 테이블에 데이터를 삽입한다
*
* 동작 과정
* 1. 해시 함수로 배열의 인덱스를 계산
* 2. 해당 인덱스의 연결 리스트 첫 번째 위치에 데이터 삽입
*
* 시간 복잡도: O(1)
*
* @param key 키
* @param value 값
*/
public void set(K key, V value) {
int index = hashFunction(key);
HashData<K, V> newData = new HashData<>(key, value);
// 해당 버킷(연결 리스트)의 첫 번째 위치에 삽입
arr[index].insertAt(0, newData);
}
/**
* 해시 테이블에서 키에 해당하는 값을 조회한다
*
* 동작 과정
* 1. 해시 함수로 배열의 인덱스를 계산
* 2. 해당 인덱스의 연결 리스트를 순회하며 키 검색
* 3. 키가 일치하는 데이터의 값을 반환
*
* 주의: 키 비교 시 equals() 메서드 사용
*
* 시간 복잡도: 평균 O(1), 최악 O(n)
*
* @param key 검색할 키
* @return 키에 해당하는 값, 없으면 null
*/
public V get(K key) {
int index = hashFunction(key);
Node<HashData<K, V>> currentNode = arr[index].getHead();
// 연길 리스트를 순회하며 키 검색
while (currentNode != null) {
if (currentNode.getData().getKey() == key) {
return currentNode.getData().getValue();
}
currentNode = currentNode.getNext();
}
// 키를 찾지 못한 경우
return null;
}
/**
* 해시 테이블에서 키에 해당하는 데이터를 제거한다
*
* 동작 과정
* 1. 해시 함수로 배열의 인덱스를 계산
* 2. 해당 인덱스의 연결 리스트를 순회하며 키 검색
* 3. 키가 일치하는 데이터를 삭제
*
* 시간 복잡도: 평균 O(1), 최악 O(n)
*
* @param key 삭제할 키
* @return 삭제된 노드, 없으면 null
*/
public Node<HashData<K, V>> remove(K key) {
int index = hashFunction(key);
DoublyLinkedList<HashData<K, V>> list = arr[index];
Node<HashData<K, V>> currentNode = arr[index].getHead();
int deletedIndex = 0;
// 연결 리스트를 순회하며 키 검색
while (currentNode != null) {
if (currentNode.getData().getKey() == key) {
return list.deleteAt(deletedIndex);
}
currentNode = currentNode.getNext();
deletedIndex++;
}
// 키를 찾이 못할 경우
return null;
}
/**
* 해시 테이블의 크기(버킷 개수)를 반환한다
* @return 테이블 크기
*/
public int getTableSize() {
return TABLE_SIZE;
}
/**
* 특정 버킷(연결 리스트)을 반환한다
* HashSet 구현을 위해 필요
*
* @param index 버킷 인덱스
* @return 해당 인덱스의 연결 리스트
*/
public DoublyLinkedList<HashData<K, V>> getBucket(int index) {
if (index < 0 || index >= TABLE_SIZE) {
throw new IndexOutOfBoundsException("버킷 인덱스가 범위를 벗어났습니다: " + index);
}
return arr[index];
}
/**
* 해시 테이블에 저장된 총 데이터 개수를 반환한다
* @return 저장된 데이터 개수
*/
public int size() {
int count = 0;
for (int i = 0; i < TABLE_SIZE; i++) {
count += arr[i].getSize();
}
return count;
}
/**
* 해시 테이블이 비어있는지 확인한다
* @return 비어있으면 true, 데이터가 있으면 false
*/
public boolean isEmpty() {
return size() == 0;
}
}
HashTableMain
/**
* 제네릭 HashTable 테스트 클래스
* Integer 키와 String 값을 사용하는 예제
*/
public class HashTableMain {
public static void main(String[] args) {
// Integer 키, String 값을 가진 해시 테이블 생성
HashTable<Integer, String> ht = new HashTable<>();
System.out.println("===== 선수 등록 (데이터 삽입) =====");
ht.set(1, "이운재"); // 1 % 10 = 1 → 버킷[1]
ht.set(4, "최진철"); // 4 % 10 = 4 → 버킷[4]
ht.set(20, "홍명보"); // 20 % 10 = 0 → 버킷[0]
ht.set(6, "유상철"); // 6 % 10 = 6 → 버킷[6]
ht.set(22, "송종국"); // 22 % 10 = 2 → 버킷[2]
ht.set(21, "박지성"); // 21 % 10 = 1 → 버킷[1] (충돌!)
ht.set(5, "김남일"); // 5 % 10 = 5 → 버킷[5]
ht.set(10, "이영표"); // 10 % 10 = 0 → 버킷[0] (충돌!)
ht.set(8, "최태욱"); // 8 % 10 = 8 → 버킷[8]
ht.set(9, "설기현"); // 9 % 10 = 9 → 버킷[9]
ht.set(14, "이천수"); // 14 % 10 = 4 → 버킷[4] (충돌!)
System.out.println("\n===== 선수 조회 (데이터 검색) =====");
System.out.println("등번호 1번 선수: " + ht.get(1)); // 이운재
System.out.println("등번호 20번 선수: " + ht.get(20)); // 홍명보
System.out.println("등번호 21번 선수: " + ht.get(21)); // 박지성
System.out.println("등번호 9번 선수: " + ht.get(9)); // 설기현
System.out.println("등번호 10번 선수: " + ht.get(10)); // 이영표
System.out.println("등번호 14번 선수: " + ht.get(14)); // 이천수
System.out.println("등번호 7번 선수: " + ht.get(7)); // null
System.out.println("등번호 99번 선수: " + ht.get(99)); // null
System.out.println("\n===== 충돌 확인 =====");
System.out.println("버킷[0]: 20번(홍명보), 10번(이영표) - 충돌 발생!");
System.out.println("버킷[1]: 1번(이운재), 21번(박지성) - 충돌 발생!");
System.out.println("버킷[4]: 4번(최진철), 14번(이천수) - 충돌 발생!");
System.out.println("\n===== 선수 삭제 테스트 =====");
System.out.println("\n--- 21번 박지성 선수 삭제 ---");
Node<HashData<Integer, String>> removed1 = ht.remove(21);
if (removed1 != null) {
System.out.println("✓ 삭제된 데이터: " + removed1.getData());
}
System.out.println("\n--- 20번 홍명보 선수 삭제 ---");
Node<HashData<Integer, String>> removed2 = ht.remove(20);
if (removed2 != null) {
System.out.println("✓ 삭제된 데이터: " + removed2.getData());
}
System.out.println("\n--- 7번 선수 삭제 시도 (등록되지 않음) ---");
ht.remove(7);
System.out.println("\n===== 삭제 후 재조회 =====");
System.out.println("등번호 21번 선수: " + ht.get(21)); // null
System.out.println("등번호 20번 선수: " + ht.get(20)); // null
System.out.println("등번호 1번 선수: " + ht.get(1)); // 이운재
System.out.println("등번호 10번 선수: " + ht.get(10)); // 이영표
System.out.println("\n===== 추가 선수 등록 =====");
ht.set(7, "김태영");
ht.set(13, "최은성");
ht.set(17, "황선홍");
System.out.println("\n===== 전체 선수 조회 테스트 =====");
int[] jerseyNumbers = {1, 4, 5, 6, 7, 8, 9, 10, 13, 14, 17, 22};
for (int num : jerseyNumbers) {
String player = ht.get(num);
if (player != null) {
System.out.printf("등번호 %2d번: %s%n", num, player);
}
}
}
}
/*
실행 결과
===== 선수 등록 (데이터 삽입) =====
===== 선수 조회 (데이터 검색) =====
등번호 1번 선수: 이운재
등번호 20번 선수: 홍명보
등번호 21번 선수: 박지성
등번호 9번 선수: 설기현
등번호 10번 선수: 이영표
등번호 14번 선수: 이천수
등번호 7번 선수: null
등번호 99번 선수: null
===== 충돌 확인 =====
버킷[0]: 20번(홍명보), 10번(이영표) - 충돌 발생!
버킷[1]: 1번(이운재), 21번(박지성) - 충돌 발생!
버킷[4]: 4번(최진철), 14번(이천수) - 충돌 발생!
===== 선수 삭제 테스트 =====
--- 21번 박지성 선수 삭제 ---
✓ 삭제된 데이터: HashData{key=21, value='박지성'}
--- 20번 홍명보 선수 삭제 ---
✓ 삭제된 데이터: HashData{key=20, value='홍명보'}
--- 7번 선수 삭제 시도 (등록되지 않음) ---
===== 삭제 후 재조회 =====
등번호 21번 선수: null
등번호 20번 선수: null
등번호 1번 선수: 이운재
등번호 10번 선수: 이영표
===== 추가 선수 등록 =====
===== 전체 선수 조회 테스트 =====
등번호 1번: 이운재
등번호 4번: 최진철
등번호 5번: 김남일
등번호 6번: 유상철
등번호 7번: 김태영
등번호 8번: 최태욱
등번호 9번: 설기현
등번호 10번: 이영표
등번호 13번: 최은성
등번호 14번: 이천수
등번호 17번: 황선홍
등번호 22번: 송종국
*/