해시 테이블(Hash Table)은 데이터를 효율적으로 저장하고 검색하기 위해 사용하는 자료구조임. 해시 테이블은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하며, 키를 해시 함수(Hash Function)를 통해 해시값으로 변환하고, 이 해시값을 기반으로 데이터를 저장할 위치를 결정.
구성 요소
해시 함수 (Hash Function)
키를 입력으로 받아 해시값을 생성하는 함수.
해시 함수는 입력된 키를 일정한 크기의 정수(인덱스)로 변환하여 해시 테이블의 특정 위치를 가리킴.
버킷 (Bucket)
해시 테이블에서 데이터를 저장하는 공간.
각 버킷은 여러 개의 값을 저장할 수 있으며, 해시 함수에 의해 인덱싱된 위치에 데이터를 저장함.
충돌 (Collision)
서로 다른 키들이 동일한 해시값을 가질 때 발생하는 현상.
충돌을 처리하기 위해 다양한 방법이 사용됨.
충돌 해결 방법
체이닝 (Chaining)
각 버킷에 연결 리스트(Linked List) 등을 사용해 여러 개의 값을 저장하여 충돌을 해결하는 방법.
같은 인덱스에 여러 값이 저장될 수 있으며, 충돌이 발생하면 새로운 값을 리스트에 추가
오픈 어드레싱 (Open Addressing)
충돌이 발생하면 다른 빈 버킷을 찾아 값을 저장하는 방법.
선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등의 방식이 있음.
장점과 단점
장점
평균적으로 빠른 검색, 삽입, 삭제 성능 (O(1))
효율적인 메모리 사용.
단점
해시 함수의 품질에 따라 성능이 크게 좌우될 수 있음.
충돌 발생 시 성능이 저하될 수 있음.
데이터의 순서를 유지하지 않음.
사용 예시
해시 테이블은 주로 데이터베이스, 캐싱 시스템, 키-값 저장소, 그리고 중복 검출과 같은 다양한 분야에서 널리 사용됨.
해시 테이블은 매우 효율적이지만 해시 함수의 선택과 충돌 처리 방법에 따라 성능이 크게 달라질 수 있으므로 상황에 맞게 설계하는 것이 중요함.
코드
class HashTable {
constructor(size = 53) {
this.table = new Array(size); // 해시 테이블의 크기를 설정
this.size = size;
}
// 간단한 해시 함수: 문자열 키를 정수 인덱스로 변환
_hash(key) {
let total = 0;
const WEIRD_PRIME = 31; // 소수를 사용하여 해시 충돌을 줄임
for (let i = 0; i < Math.min(key.length, 100); i++) {
const char = key[i];
const value = char.charCodeAt(0) - 96; // 알파벳을 숫자로 변환
total = (total * WEIRD_PRIME + value) % this.size;
}
return total;
}
// 데이터를 해시 테이블에 삽입
set(key, value) {
const index = this._hash(key); // 키를 해시값으로 변환하여 인덱스 찾기
if (!this.table[index]) {
this.table[index] = [];
}
// 기존 키-값 쌍이 있는지 확인하고 업데이트
for (let i = 0; i < this.table[index].length; i++) {
if (this.table[index][i][0] === key) {
this.table[index][i][1] = value; // 값 업데이트
return;
}
}
this.table[index].push([key, value]); // 새로운 키-값 쌍 추가
}
// 데이터를 해시 테이블에서 검색
get(key) {
const index = this._hash(key);
if (this.table[index]) {
for (let pair of this.table[index]) {
if (pair[0] === key) {
return pair[1]; // 키와 일치하는 값을 반환
}
}
}
return undefined; // 키가 없으면 undefined 반환
}
// 해시 테이블에서 데이터 삭제
remove(key) {
const index = this._hash(key);
if (this.table[index]) {
this.table[index] = this.table[index].filter((pair) => pair[0] !== key); // 키에 해당하는 쌍을 제거
}
}
}
// 사용 예시
const ht = new HashTable();
ht.set("apple", 10);
ht.set("banana", 20);
console.log(ht.get("apple")); // 10
console.log(ht.get("banana")); // 20
ht.remove("apple");
console.log(ht.get("apple")); // undefined
// Set사용
class HashTable {
constructor() {
this.table = new Set(); // Set을 사용하여 데이터 저장
}
// 데이터를 삽입하는 메서드
set(key, value) {
// 동일한 키가 있으면 기존 쌍을 삭제하고 새로운 값으로 업데이트
this.table.forEach((pair) => {
if (pair[0] === key) {
this.table.delete(pair);
}
});
this.table.add([key, value]); // 새로운 키-값 쌍을 추가
}
// 데이터를 검색하는 메서드
get(key) {
for (let [k, v] of this.table) {
if (k === key) {
return v; // 키에 해당하는 값을 반환
}
}
return undefined; // 키가 없으면 undefined 반환
}
// 데이터를 삭제하는 메서드
remove(key) {
for (let pair of this.table) {
if (pair[0] === key) {
this.table.delete(pair); // 키에 해당하는 쌍을 삭제
return;
}
}
}
}
// 사용 예시
const ht = new HashTable();
ht.set("apple", 10);
ht.set("banana", 20);
console.log(ht.get("apple")); // 10
console.log(ht.get("banana")); // 20
ht.remove("apple");
console.log(ht.get("apple")); // undefined
// Set의 고유한 특성을 활용한 간단한 해시 테이블 구현 방법이지만, Set은 본래 키-값 쌍의 해시 테이블보다는 Map에 가까운 데이터 구조임. Set을 활용하는 방식은 간단한 저장, 검색, 삭제 기능을 구현할 수 있지만, 실제 해시 테이블의 충돌 처리와 같은 고급 기능은 제공하지 않음.
