[자료구조] 해시(Hash)
해시(Hash)란?
해시는 데이터를 빠르게 찾기 위한 방법이다. 어떤 데이터를 넣으면, 그 데이터가 어디에 저장될지 수학적 계산, 즉 해시함수를 통해 결정해주는 방식이다.
예를 들어, 도서관에서 책을 찾는다고 해보자.
그냥 책 제목 순서대로 줄 세워두면, 어떤 책을 찾으려면 처음부터 하나하나 봐야 한다. => 느림 (O(n))
그런데 책 제목을 가지고 어떤 방 번호를 정하고, 그 방에 책을 넣어둔다고 생각해보자.
예를 들어 '해리포터'라는 책 => 계산식으로 3번 방으로 간다.
'반지의제왕' => 7번방으로 간다.
이제 책을 찾으려면 계산만 해서 바로 그 방으로 가면 된다. => 빠름 (O(1))
키(이름) → 해시함수 → 방번호(Index) → 값(데이터)
"Harry" → 3 → [3] → "Harry Potter 책"
"Lord" → 7 → [7] → "반지의 제왕 책"
"Avengers" → 2 → [2] → "마블 코믹스"
키(Key)-값(Value) 저장소
해시는 보통 키(Key)와 값(Value)의 형태로 데이터를 저장한다.
- 키 = 데이터의 이름
- 값 = 실제 데이터
즉, 해시는 '빠른 검색이 가능한 사전(Dictionary)' 같은 거라고 보면 된다.
해시테이블이란?
해시테이블은 해시 자료구조를 구현한 구체적인 방식을 뜻한다. 즉, 해시는 개념, 해시테이블은 구현체라고 말할 수 있다.
내부적으로는 배열(Array)를 사용한다.
키를 해시 함수에 넣어 배열의 인덱스를 계산하고, 그 위치에 값을 저장한다.
충돌이 생기면 체이닝이나 오픈 어드레싱 기법으로 처리한다.
※ 해시 테이블 직접 구현 예시
class HashTable {
constructor(size) {
this.table = new Array(size);
}
hash(key) {
let hash = 0;
for (let char of key) {
hash += char.charCodeAt(0);
}
return hash % this.table.length;
}
set(key, value) {
let index = this.hash(key);
if (!this.table[index]) {
this.table[index] = [];
}
this.table[index].push([key, value]);
}
get(key) {
let index = this.hash(key);
if (!this.table[index]) return undefined;
for (let [k, v] of this.table[index]) {
if (k === key) return v;
}
return undefined;
}
}
let ht = new HashTable(10);
ht.set("apple", "사과");
ht.set("banana", "바나나");
console.log(ht.get("apple")); // "사과"
console.log(ht.get("banana")); // "바나나"해시함수란?
해시 함수는 키를 입력받아 배열 인덱스로 변환하는 함수
좋은 해시 함수는 결과가 고르게 분포되어 충돌을 최소화한다.
해시함수의 대표적인 알고리즘으로 SHA가 있다. SHA
해시충돌이란?
서로 다른 키가 같은 인덱스로 해시되는 현상을 말한다.
해결방법은 크게 두가지가 있다.
1. 체이닝(Chaining) : 같은 인덱스에 여러 값을 연결 리스트로 저장
2. 오픈 어드레싱(Open Addressing) : 빈 인덱스를 찾아 다른 자리에 저장
해시의 장단점
- 장점
- 빠른 검색/삽입/삭제 가 가능하다. O(1)
- 키-값 구조로 직관적인 데이터 접근이 가능하다.
- 데이터가 많아져도 찾는 속도가 크게 느려지지 않는다.
- 단점
- 해시 함수가 좋지 않으면 충돌(두 개 키가 같은 방 번호를 배정됨)이 생길 수 있다.
- 메모리를 많이 쓸 수 있다.
- 키의 순서를 보장하지 않는다.
자바스크립트에서 해시 자료구조 사용
자바스크립트에는 해시테이블 자료구조가 내장되어 있다.
- Object : 문자열/심볼 키 사용
- Map : 다양한 타입(숫자, 객체, 함수 등)을 키로 사용 가능
- Set : 값의 중복 여부 검사에 유용
해시가 실제로 쓰이는 곳
- 데이터베이스 인덱싱
- 캐시(Cache) 구현 (ex. Redis)
- 중복 검사 (ex. 문자열에 중복된 문자가 있는지 확인)
- 비밀번호 저장 (암호학적 해시 함수 사용)