목차
- Intro
- Array vs Hash Table
- 어떻게 O(1)을 만들었을까? - Hash function과 Collision
- Collision을 최소화해 보자
- JavaScript의 Hash Table
- 마치면서
Intro
코드를 더 빠르게 만들어주는 Hash Table에 대해 배워보자! Hash Table이란 단어를 처음 들어봤어도 개발하다가 이미 써봤을 확률이 매우 높다. Hash Table은 key-value 쌍으로 데이터를 저장하는 자료구조이다. 이 자료구조는 생각보다 똑똑한 방법으로 효율성을 높이는데, 어떤 식으로 구현되어 있는지 뜯어보자.
Array vs Hash Table
배열은 index를 통해 데이터를 순차적으로 저장한다. 특정 index의 값을 읽거나 추가할 때는 O(1)이지만, 어느 index에 있는지 모르는 값을 찾으려고 할 때는 첫 번째 index에서부터 순차적으로 원하는 값을 찾을 때까지 확인해야 한다. 이 방식은 요소가 많을수록 시간이 오래 걸리는 O(n)의 시간복잡도를 가진다.
반면, hash table은
let person = {
name: "그냥하는거지뭐~",
age: 23,
city: "Seoul"
};
이렇게 저장해서, 특정 값을 찾을 때 key로 바로 찾을 수 있다. (ex. person[name]) 따라서 O(1)의 시간복잡도를 가진다. 데이터를 추가, 삭제할 때도 마찬가지로 O(1)이다.
이를 이용해서 value만 있는 데이터도 다음과 같이 hash table로 관리하면 O(1)의 시간 복잡도로 특정 값을 찾을 수 있을 것이다.
const data = {
a: true,
c: true,
d: true,
e: true,
};
console.log(data["a"]) // true
console.log(data["b"]) // undefined
어떻게 O(1)을 만들었을까? - Hash function과 Collision
Hash Table의 내부에도 사실 array 같은 구조가 있다. 이전 섹션에서 array는 찾고 싶은 index의 값을 알면 바로 그 값에 접근할 수 있지만(O(1)), index를 모르면 순차적으로 돌아야 한다고 했다(O(n)). Hash Table은 바로 이것을 이용하기 위해 hash function을 도입한다. key를 hash function에 input으로 넣으면 hashing을 거쳐 output으로 hash value가 나오고, 이를 index삼아 value에 접근하는 것이다. 그리고, 값이 저장되는 공간을 bucket이라 한다.
해시함수는 임의의 크기의 데이터를 고정된 크기의 데이터로 매핑시키는 함수이다. 동일한 입력에 대해 항상 같은 출력(해시값)을 반환해야 하며, 함수의 로직에 따라 좋은 해시함수일 수도, 아닐 수도 있다. 다음 예시를 보자.
글자수를 hash value로 반환하는 해시함수가 있다고 해보자. 'kiwi'을 넣으면 4가 나오고, bucket의 index 4에 value가 저장될 것이다. 'mango'를 넣으면 index 5에 저장된다. 이때 'melon'을 넣으면 어떻게 될까? index 5에는 이미 mango의 value가 들어가 있다. 이를 collision이라 한다. 즉, 해시함수에 각각 다른 입력을 넣었을 때 출력이 중복되는 일, 즉 다른 key가 같은 hash value를 가지는 일이 많아지면 좋은 해시함수라고 볼 수 없다.
해시함수의 조건
- 동일한 입력에 대해 항상 같은 해시값을 반환
- 일방향성
- 균일한 분포
- 빠른 계산 속도
- 충돌 최소화
- 입력 값의 작은 변화에도 해시 값이 크게 달라져야 함 (avalanche effect)
Collision을 최소화해 보자
#chaining #open_addressing #linear_probing #quadratic_probing #double_hashing
Collision을 최소화하는 방법에는 대표적으로 chaining 기법과 open addressing 기법을 들 수 있다. Open addressing에는 linear probing, quadratic probing, double hashing 기법이 있다.
n: number of data
m: size of hash table
Load factor: λ=n/m
① Chaining
1.1. 개념
Chaining은 각 bucket이 linked list로 구현되어 동일한 bucket에 해당되는 key-value 쌍 데이터를 배열에 순차적으로 저장한다. 데이터의 개수(n)가 배열 index의 범위(m)를 초과하는 경우에 유용하게 사용할 수 있다.
탐색(search)할 때는 hash function이 반환한 index 위치에서 해당 key를 가진 데이터가 있는지 보고, 있으면 return 한다. 한 index에 여러 개의 데이터가 있으면 linear searching을 통해 찾는다.
1.2. Worst Case와 장단점
한 index에 모든 데이터가 linked list로 저장될 경우가 worst case일 텐데, 이때는 O(m)의 시간복잡도를 가질 것이다. Insert, delete도 같은 논리로 worst case일 때 O(m)이다.
Chaining 기법은 해시 테이블이 가득 차지 않아도 linked list를 통해 연속적인 삽입이 가능하고, 해시 함수의 성능이 떨어져도 비교적 안정적인 성능을 가진다는 특징이 있다. 하지만 linked list의 길이가 길어지면, 즉 많은 충돌이 발생하면 우리가 원하는 O(1)이 아니게 된다. 또한 데이터의 수가 해시테이블의 크기보다 훨씬 적다면, 안 쓰는 공간에 대한 낭비가 심할 것이다. 또, 빈 공간이 많음에도 collision이 발생할 경우 linked list를 위한 추가 공간을 마련해야 하기 때문에 메모리 사용량이 많아질 수 있다는 단점이 있다.
정리하면,
장점
- 해시 테이블의 load factor가 높아지더라도 성능 유지가 비교적 용이
- 해시 함수의 성능이 다소 떨어져도 비교적 성능이 안정적
단점
- 연결 리스트의 길이가 길어지면, 즉 많은 충돌이 발생하면 검색 시간이 길어질 수 있 음 => O(1)이 아님
- n << m일 경우 공간 낭비가 심함
- 다른 공간이 많음에도 collision 발생 시 linked list를 위한 추가 공간을 마련해야 함
- 각 요소마다 추가적인 공간이 필요하기 때문에 메모리 사용량이 많아질 수 있음
② Open Addressing(1) - Linear Probing(선형 조사), Quadratic Probing(이차원 조사)
2.1. 개념
Open addressing은 collision 발생 시 linked list와 같은 추가적인 공간을 부여하지 않고 주어진 공간(m)에서 해결하는 방법이다.
Linear probing과 quadratic probing은 충돌이 발생했을 때 다음에 시도할 버킷의 위치를 계산하는 방식에서 차이가 나타나는데, linear probing은 일정한 간격(보통 1)을 더해가며 찾고, quadratic probing은 제곱수를 이용해 찾는다.
linear probing의 작동 원리는 다음과 같다.
ⓐ key를 hash function에 입력하여 초기 index 계산
ⓑ 계산된 index에 버킷이 비어있는지 확인
ⓒ collision 발생 시, 초기 index부터 시작해서 다음 버킷을 순차적으로 검사. (빈 버킷 찾을 때까지)
ⓓ 빈 버킷 찾으면 그 위치에 key-value 저장
찾을 때도 비슷한 순서를 따른다.
2.2. 충돌 예시와 해결 과정
m=5이고, hash function은 h(key) = key % 5라고 했을 때, 7, 12, 17을 삽입해보자.
ⓐ 모든 key는 같은 초기 hash value 2를 가진다. (7 % 5 = 12 % 5 = 17 % 5 = 2).
ⓑ key 7이 index 2에 저장된다.
ⓒ key 12는 index2가 차있으므로 index3에 저장된다.
ⓓ key 17은 index 2, 3이 차있으므로 index4에 저장된다.
key17을 찾고 싶다면,
ⓐ index2 확인 => 실패
ⓑ index3 확인 => 실패
ⓒ index4 확인 => 성공, 종료
2.2. Worst case와 장단점
Linear probing의 경우 충돌이 발생하면 순차적으로 이동하면서 빈 공간을 채우므로 특정 부분에 데이터가 몰리는 1차 clustering 문제가 발생할 수 있다. Quadratic probing의 경우 1차 clustering 문제가 어느 정도 해결될 수 있지만, 여러 데이터가 같은 초기 hash value를 가지게 되면 모두 같은 순서로 조사하게 되는 2차 clustering 문제가 발생할 수 있다.
해시 테이블이 거의 찼을 경우(n/m이 1에 가까울 경우)이거나, hash function의 성능이 좋지 않다면 모든 버킷을 검사할 수도 있다. 최악의 경우는 모든 key가 동일한 hash value를 가질 때 linear probing이 필요한 최대 거리를 탐사해야 하는 경우이다. => O(m)
장점
- 별도의 자료구조를 사용하지 않기 때문에 추가 메모리가 필요없다.
- 구현이 간단하고 소규모 데이터셋에 쓰기 좋다
단점
- clustering problem: 연속된 빈 버킷이 줄어들수록 clustering 현상으로 탐색 시간이 길어질 수 있다. (데이터가 쌓일수록 심해짐)
2.3. Clustering Problem을 해결하는 방법: Rehashing
Load factor가 정해진 임계값을 넘으면 rehashing 과정을 거친다. 우선 hash table 확장하는데, 기존보다 큰 새 hash table을 생성한다. 일반적으로 크기는 2배 이상으로 설정하고, 소수로 설정해 충돌 가능성을 최소화한다. 그리고 재해싱 과정을 거친다. 기존 테이블에 있던 모든 데이터를 새 hash function을 이용해 다시 계산해서 새 hash table을 채운다. 이 과정이 마무리되면, 기존의 hash table은 폐기된다.
rehashing은 clustering problem을 해결하고 데이터의 분포를 균일하게 만들어 충돌 가능성을 줄인다. 하지만 모든 데이터를 새로운 테이블에 다시 적용하는 과정은 비용과 시간이 많이 들 수 있다.
③ Open Addressing(3) - Double Hashing
3.1. 개념
Double hashing은 hash function을 두 개 사용하는 방식이다. 함수 두 개를 h(key), d(key)라고 하고, 일반적으로 다음과 같은 수식으로 계산된다.
Idx(i) = (h(key) + i × d(key)) % m
h(key): 초기 해시 위치
d(key): 두 번째 해시 함수에 의한 offset
i: 충돌 횟수 (0, 1, 2, ...)
초기에는 i=0이므로, h(key) % m이 초기 index가 된다. 충돌이 발생하면 d(key)가 유의미해지는데, 이를 사용해 새로운 위치를 계산한다.
3.2. 충돌 예시와 해결 과정
다음과 같은 조건에서 두 개의 키 14, 21이 있다고 가정하자.
h(key) = key % 7
d(key) = 5 - (key % 5)
m = 7
ⓐ key 14 삽입: h(14) = 14 % 7 = 0 => 0번 index에 저장
ⓑ key 21 삽입: h(21) = 21 % 7 = 0 => collision 발생!
충돌을 해결해보자
ⓐ d(21) = 5 - (21 % 5) = 5 - 1 = 4
ⓑ 새로운 index = (0 + 1×4) % 7 = 4 % 7 = 4
ⓒ index4 확인 => 비어있으면 저장
3.3. 균일한 분포를 위한 몇 가지 조건
- d(key)는 0을 반환하면 안된다
d(key)는 다음 위치를 위한 점프 크기를 정하는 함수이다. 이때 d(key)가 0을 반환하면, 충돌이 계속 발생해도 계속 같은 위치만 조사하게 되므로 함수 두 개를 사용하는 의미가 없어진다. (충돌 해결 실패)
- d(key)의 반환 값과 m이 서로소 => m을 소수로 설정하자
d(key)의 반환 값과 m이 서로소가 되어야 해시 테이블을 균일하게 사용할 수 있다. 서로소는 두 수의 GCD(최대공약수)가 1이 되는 관계를 말하는데, 서로소가 아닐 때와 서로소일 때를 비교해보자.
CASE 1: 서로소가 아닐 경우 (m=10, d(key)=5, h(key)=0)
Idx(0) = (0 + 0×5) % 10 = 0
Idx(1) = (0 + 1×5) % 10 = 5
Idx(2) = (0 + 2×5) % 10 = 0
Idx(3) = (0 + 3×5) % 10 = 5
...
CASE 2: 서로소일 경우 (m=10, d(key)=3, h(key)=2)
Idx(0) = (2 + 0×3) % 10 = 2
Idx(1) = (2 + 1×3) % 10 = 5
Idx(2) = (2 + 2×3) % 10 = 8
Idx(3) = (2 + 3×3) % 10 = 1
...
이처럼 서로소가 아닐 경우 0, 5, 0, 5,... 처럼 계속해서 특정 index만 방문하게 되는데, 서로소일 경우 해시 테이블의 모든 공간을 방문하게 된다. m을 소수로 설정하면 자연스럽게 해결되는 문제이다.
3.4. double hashing의 장단점
Double hashing은 다른 open addressing 기법에 비해 clustering problem 문제를 크게 감소시킨다. 해시테이블의 모든 버킷이 사용될 확률이 높아져 데이터가 균일하게 분포되며, 메모리 사용을 효율적으로 최소화할 수 있다. Load factor가 높을 경우에도 두 번째 함수 d(eky)가 탐사 경로를 다양화하여 충돌 해결 효율을 높이므로 성능 저하가 적다.
하지만 단점도 분명히 존재한다. Double hashing은 두 개의 함수를 계산해야 하므로 시간과 비용이 더 들고, 이 두 함수의 품질에 크게 의존한다. d(key)가 0을 반환하면 안되고 m과 d(key)가 서로소가 되어야 하는 등의 조건을 만족시키는 추가 로직을 생각해야 하는데, d(key)를 잘못 선택할 경우에 성능이 저하될 수 있다. 또한 h(key)와 d(key)가 조화롭지 않을 경우 구현이 복잡해지고 오류가 발생하기 쉽다. 정리하면,
장점
- 클러스터링 감소
- 효율적인 메모리 사용
- 높은 load factor에서의 성능 유지
단점
- 계산 복잡도
- 구현 복잡성
- 성능 저하의 가능성
JavaScript의 Hash Table
① 직접 구현
JavaScript를 사용하여 간단한 hash table을 직접 구현해보자. hash function의 로직은 key의 문자들의 ASCII 코드 값을 더한 후, 해시테이블의 크기(size)로 나눈 나머지를 반환하여 index로 사용하겠다. 이 index는 해시테이블 내에서 key-value를 저장할 위치를 결정한다. 충돌은 chaining 기법으로 관리하겠다.
삽입(set)
- key를 해시 함수에 통과시켜 index를 얻는다.
- 해당 index에 아무것도 없으면 새 배열을 할당하고, 그곳에 key-value 쌍을 객체 형태로 저장한다.
- 이는 chaining 기법으로, 같은 index에 여러 개의 데이터가 존재할 수 있게 한다.
검색(get)
- key를 해시 함수에 통과시켜 index를 얻는다.
- 해당 index에 있는 배열을 순회하면서 일치하는 key의 값을 반환한다.
삭제(remove)
- key를 해시 함수에 통과시켜 index를 얻는다.
- 해당 index의 배열에서 키에 해당하는 객체를 찾아 삭제한다.
class HashTable {
constructor(size = 100) {
this.table = new Array(size);
this.size = size;
}
hash(key) {
let hashValue = 0;
for (let char of key) {
hashValue = (hashValue + char.charCodeAt(0)) % this.size;
}
return hashValue;
}
// 키-값 쌍 삽입
set(key, value) {
const index = this.hash(key);
if (!this.table[index]) {
this.table[index] = [];
}
// 체이닝을 사용하여 충돌 관리
this.table[index].push({ key, value });
}
// 값 검색
get(key) {
const index = this.hash(key);
const items = this.table[index];
if (items) {
for (let item of items) {
if (item.key === key) {
return item.value;
}
}
}
return undefined;
}
// 키-값 쌍 삭제
remove(key) {
const index = this.hash(key);
const items = this.table[index];
if (items) {
for (let i = 0; i < items.length; i++) {
if (items[i].key === key) {
items.splice(i, 1);
return true;
}
}
}
return false;
}
}
const hashTable = new HashTable();
hashTable.set('name', '그냥하는거지뭐~');
hashTable.set('age', 23);
console.log(hashTable.get('name')); // 그냥하는거지뭐~
console.log(hashTable.get('age')); // 23
hashTable.remove('name');
console.log(hashTable.get('name')); // undefined
② JavaScript 엔진과 최적화
JavaScript에서 Object, Map, Set과 같은 내장 자료구조는 해시 테이블 기반의 구현으로 데이터를 관리한다. 이러한 자료구조는 내부적으로 충돌 해결 매커니즘이 구현되어 있어 개발자가 직접 충돌을 관리하지 않아도 된다. Collision 처리 방식은 브라우저 엔진의 구현에 따라 다른데, 이들의 구현 세부사항은 대부분 공개되진 않는다. 하지만 가장 흔히 사용되는 기법은 chaining이다.
const map = new Map();
// 여러 키가 같은 해시 값을 가질 수 있음
map.set('key1', 'value1');
map.set('key2', 'value2');
// 두 키는 내부적으로 충돌할 수 있지만, Map은 체이닝을 통해 이를 관리
console.log(map.get('key1')); // "value1"
console.log(map.get('key2')); // "value2"
대부분의 현대 JavaScript 엔진(ex. V8, SpiderMonkey, JavaScriptCore)은 데이터 구조를 최적화하여 충돌을 효과적으로 관리한다. 이 엔진들은 각기 다른 최적화 전략을 적용할 수 있는데, 주요 전략에 대부분 고성능 해시 함수를 사용하는 것과 동적 리사이징이 포함된다.
고성능 해시 함수
해시 함수의 계산 속도는 런타임 성능에 직접적으로 영향을 미치기 때문에 빠른 계산 속도가 중요하다. 또한 해시테이블 전체에 균일하게 분포시킴으로써 충돌을 최소화해야 한다.
동적 리사이징
데이터의 양이 증가하면, load factor가 높아져 성능 저하가 발생할 수 있다. Load factor가 설정된 임계값 (ex.0.7)을 초과하면 테이블의 크기를 두 배로 늘리고 모든 데이터를 rehashing한다. 반대로 load factor가 너무 낮은 경우(ex. 0.2), 자원을 효율적으로 사용하기 위해 테이블 크기를 줄이기도 한다.
마치면서
hash table이 무엇인지부터, 어떻게 시간복잡도를 줄이는지, 충돌은 어떻게 관리하는지, JavaScript에서는 어떻게 사용하는지에 대해 알아보았다.
이제 문제풀러 가자!
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
▶ 추가로 생각해볼 것
① 다른 자료구조와 비교하여 hash table은 멀티스레드 환경에서 심각한 수준의 race condition 문제에 빠질 위험이 있다. 성능 감소를 최소화한 채로 이 문제를 해결할 수 있는 방법이 뭐가 있을까?
② JavaScript에서 Object와 Map 비교
Reference
- 10분 테코톡 https://www.youtube.com/watch?v=Rpbj6jMYKag
- 니꼬쌤 https://www.youtube.com/watch?v=HraOg7W3VAM
- 쥐피티 포
- https://github.com/VSFe/Tech-Interview/blob/main/01-DATA_STRUCTURE_ALGORITHM.md
- https://en.wikipedia.org/wiki/Hash_table#
'CS > Data Structure, Algorithm' 카테고리의 다른 글
| 정렬 알고리즘의 성능 비교와 상황별 선택 기준 (1) | 2024.08.07 |
|---|---|
| Stack 2개로 Queue, Queue 2개로 Stack 만들기 (0) | 2024.05.07 |
