전화번호부에서 이름으로 전화번호를 찾는다고 생각해보자.
전화번호부가 정렬되지 않았다면 처음부터 끝까지 찾아야 하지만, 이름을 특정 규칙으로 변환해서 바로 위치를 찾을 수 있다면 훨씬 빠를 것이다.
이것이 바로 해시 테이블(Hash Table)의 핵심 개념이다.
해시 테이블
해시 테이블은 해시 함수와 테이블(배열)이 합쳐진 자료구조이다.
키(Key)를 해시 함수로 변환하여 인덱스를 얻고, 그 위치에 값(Value)을 저장한다. 이를 통해 데이터의 저장과 검색을 매우 빠르게 수행할 수 있다.
해시 테이블의 핵심 개념
| 설명 | |
| 키 (Key) | 데이터를 식별하는 고유한 값 (예: 1, 21) |
| 값 (Value) | 실제로 저장할 데이터 (예: "이운재", "박지성") |
| 해시 함수 | 키를 인덱스로 변환하는 함수 (예: key % 10) |
| 버킷 (Bucket) | 해시 테이블의 각 저장 공간 |
해시 테이블의 장단점
장점
- 빠른 속도: 데이터 읽기, 삽입, 삭제가 평균 O(1)으로 매우 빠르다.
- 효율적인 검색: 키만 알면 바로 데이터에 접근할 수 있다.
단점
- 메모리 사용: 배열 크기만큼 메모리를 미리 할당해야 한다.
- 해시 충돌: 서로 다른 키가 같은 인덱스로 변환될 수 있다.
따라서, 좋은 해시 함수의 구현이 필수적이다.
해시 충돌 (Hash Collision)
서로 다른 키가 같은 해시 값을 가지는 경우를 해시 충돌이라고 한다.
예를 들어, 해시 함수가 key % 10일 때:
- 키 1 -> 인덱스 1
- 키 11 -> 인덱스 1 (충돌 발생)
- 키 21 -> 인덱스 1 (충돌 발생)
이 구현에서는 체이닝(Chaining) 방식으로 충돌을 해결한다. 각 버킷에 연결 리스트를 두어, 같은 인덱스에 여러 데이터를 저장한다.
해시 테이블 구현하기
HashData 클래스
키-값 쌍을 저장하는 클래스이다.
class HashData {
constructor(key, value) {
this.key = key; // 키
this.value = value; // 값
}
}
HashTable 클래스
import { DoublyLinkedList } from "../linked_list/DoublyLinkedList.mjs";
class HashTable {
constructor() {
this.arr = [];
// 크기 10인 배열을 생성하고, 각 버킷에 연결 리스트를 둔다
for (let i = 0; i < 10; i++) {
this.arr[i] = new DoublyLinkedList();
}
}
}배열의 각 인덱스마다 양방향 연결 리스트를 생성한다. 이렇게 하면 해시 충돌이 발생해도 같은 버킷에 여러 데이터를 저장할 수 있다.
주요 메서드
1. hashFunction() - 해시 함수
hashFunction(number) {
return number % 10;
}키를 10으로 나눈 나머지를 인덱스로 사용한다. 즉, 0~9 범위의 인덱스가 생성된다.
- hashFunction(1) → 1
- hashFunction(21) → 1
- hashFunction(14) → 4
2.set() - 데이터 저장
set(key, value) {
this.arr[this.hashFunction(key)].insertAt(0, new HashData(key, value));
}- 키를 해시 함수로 변환하여 인덱스를 구한다.
- 해당 인덱스의 연결 리스트 맨 앞에 데이터를 삽입한다.
- 같은 인덱스에 이미 데이터가 있어도 연결 리스트에 추가되므로 충돌이 해결된다.
3. get() - 데이터 조회
get(key) {
let currentNode = this.arr[this.hashFunction(key)].head;
while (currentNode != null) {
if (currentNode.data.key == key) {
return currentNode.data.value;
}
currentNode = currentNode.next;
}
return null;
}- 키를 해시 함수로 변환하여 인덱스를 구한다.
- 해당 인덱스의 연결 리스트를 순회하며 키가 일치하는 노드를 찾는다.
- 찾으면 값을 반환하고, 없으면 null을 반환한다.
4. remove() - 데이터 삭제
remove(key) {
let list = this.arr[this.hashFunction(key)];
let currentNode = list.head;
let deletedIndex = 0;
while (currentNode != null) {
if (currentNode.data.key == key) {
return list.deleteAt(deletedIndex);
}
currentNode = currentNode.next;
deletedIndex++;
}
return null;
}- 키를 해시 함수로 변환하여 인덱스를 구한다.
- 해당 인덱스의 연결 리스트를 순회하며 키가 일치하는 노드를 찾는다.
- 찾으면 해당 위치의 노드를 삭제하고, 없으면 null을 반환한다.
해시 테이블 사용 예제
let hashTable = new HashTable();
// 데이터 저장 (번호: 이름)
hashTable.set(1, "이운재");
hashTable.set(4, "최진철");
hashTable.set(20, "홍명보");
hashTable.set(21, "박지성");
// 데이터 조회
console.log(`1: ${hashTable.get(1)}`); // 1: 이운재
console.log(`21: ${hashTable.get(21)}`); // 21: 박지성
// 데이터 삭제
hashTable.remove(1);
console.log(`1: ${hashTable.get(1)}`); // 1: null
해시 테이블의 시간복잡도
| 평균 | 최악 | |
| 삽입 (set) | O(1) | O(n) |
| 조회 (get) | O(1) | O(n) |
| 삭제 (remove) | O(1) | O(n) |
- 평균: 해시 함수가 데이터를 골고루 분산시키면 O(1)
- 최악: 모든 데이터가 같은 버킷에 몰리면 O(n) (연결 리스트 순회 필요)
좋은 해시 함수는 데이터를 균등하게 분산시켜 충돌을 최소화한다.
해시 테이블의 실제 활용 사례
1. 데이터베이스 인덱싱
데이터베이스에서 특정 레코드를 빠르게 찾기 위해 해시 테이블을 사용한다.
// 사용자 ID로 사용자 정보 빠르게 조회
const userTable = new HashTable();
userTable.set(12345, { name: "홍길동", email: "hong@example.com" });
userTable.set(67890, { name: "김철수", email: "kim@example.com" });
const user = userTable.get(12345);
console.log(user.name); // "홍길동"
2. 캐싱 (Caching)
자주 사용되는 데이터를 메모리에 젖아하여 빠르게 접근할 수 있다.
const cache = new HashTable();
function getDataWithCache(id) {
// 캐시에 있으면 바로 반환
let cached = cache.get(id);
if (cached) {
return cached;
}
// 없으면 DB에서 조회하고 캐시에 저장
let data = fetchFromDatabase(id);
cache.set(id, data);
return data;
}
3. 중복 제거
배열에서 중복된 요소를 찾거나 제거할 때 사용한다.
function removeDuplicates(arr) {
const seen = new HashTable();
const result = [];
for (let item of arr) {
if (!seen.get(item)) {
seen.set(item, true);
result.push(item);
}
}
return result;
}
console.log(removeDuplicates([1, 2, 2, 3, 4, 4, 5])); // [1, 2, 3, 4, 5]
4. 빈도수 계산
문자열이나 배열에서 각 요소의 등장 횟수를 셀 때 사용한다.
function countFrequency(str) {
const freq = new HashTable();
for (let char of str) {
const count = freq.get(char) || 0;
freq.set(char, count + 1);
}
return freq;
}
// "hello"의 각 문자 빈도수
// h: 1, e: 1, l: 2, o: 1
5. 객체/맵 구현
JavaScript의 객체({})나 Map은 내부적으로 해시 테이블로 구현되어 있다.
// JavaScript 객체는 해시 테이블이다
const person = {
name: "홍길동", // key: "name", value: "홍길동"
age: 30 // key: "age", value: 30
};
console.log(person.name); // O(1)로 접근
해시 테이블은 빠른 검색이 필요한 곳에서 빛을 발하는 자료구조이다. 키만 알면 O(1)로 데이터에 접근할 수 있어, 데이터베이스 인덱싱부터 캐싱, 중복 제거까지 광범위하게 활용된다.
좋은 해시 함수를 사용하면 대부분의 연산을 상수 시간에 수행할 수 있다.