데이터를 순차적으로 뒤지며 찾는 O(N)의 고통에서 벗어나게 해주는 마법의 상자입니다. Key-Value(키-값) 쌍으로 데이터를 저장하며, 입력된 'Key'를 신비한 해시 함수(Hash Function)에 통과시키면 데이터를 저장할 '고유한 위치(배열 인덱스)'가 즉시 튀어나옵니다. 이 덕분에 데이터가 수백만 개라도 단 한 번의 접근(O(1))만에 원하는 데이터를 찰나에 찾아낼 수 있습니다.
1. 구조 및 해시 충돌(Collision) 해결법
2. 성능 및 특징 요약
연산 (Operation)
평균 시간 복잡도
최악의 경우 (Worst Case)
비고
탐색 (Search)
O(1) 🚀
O(N)
충돌이 발생하지 않으면 단번에 찾습니다. 모든 데이터가 하나의 슬롯에 충돌(Collision)하면 연결 리스트를 순회해야 하므로 O(N)이 됩니다.
삽입 (Insert)
O(1) 🚀
O(N)
마찬가지로 배열의 인덱스에 접근하여 즉시 할당합니다.
삭제 (Delete)
O(1) 🚀
O(N)
Key를 해시 변환하여 인덱스를 찾고 바로 삭제합니다.
💡 실무 지식: 해시 충돌(Collision)과 Redis
서로 다른 Key가 우연히 같은 배열 인덱스를 가리키는 현상을 해시 충돌(Collision)이라 합니다. 이를 해결하기 위해 같은 칸에 값이 겹치면 연결 리스트로 줄줄이 달아버리는 체이닝(Chaining) 방식과, 빈 칸을 찾아 옆으로 이동하는 개방 주소법(Open Addressing) 방식이 쓰입니다.
실무에서 해시 테이블은 정말 지겹게 사용됩니다. 데이터베이스에서 빠른 조회를 위한 해시 인덱스, JSON 데이터를 다루는 딕셔너리 객체, 그리고 무엇보다 Redis, Memcached 같은 인메모리 캐시 시스템의 핵심 엔진이 바로 이 해시 테이블 메커니즘입니다!
// 📂 HashTable.js (JavaScript)
// 자바스크립트의 객체(Object)와 Map은 내부적으로 해시 테이블을 사용합니다.
// 여기서는 원리를 이해하기 위해 배열을 이용해 직접 해시 테이블을 구현해 봅니다.
class HashTable {
constructor(size = 50) {
this.buckets = new Array(size);
this.size = size;
}
// 간단한 문자열 해시 함수
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % this.size;
}
// 체이닝(Chaining) 기법을 사용한 데이터 삽입
set(key, value) {
const index = this._hash(key);
if (!this.buckets[index]) {
this.buckets[index] = [];
}
this.buckets[index].push([key, value]);
}
// Key를 통해 O(1)에 가까운 속도로 Value 탐색
get(key) {
const index = this._hash(key);
const bucket = this.buckets[index];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket[i][1];
}
}
}
return undefined;
}
}
// 실행 예시
const myHash = new HashTable();
myHash.set("name", "Minstudio");
myHash.set("age", 25);
console.log("Name:", myHash.get("name")); // Minstudio 출력
// 💡 실무에서는 자바스크립트 내장 Map을 쓰는 것이 가장 성능이 좋습니다.
const map = new Map();
map.set("name", "Minstudio");
console.log("Map Output:", map.get("name"));
