Hash Table
Hash Table: Hash collision resolved by seperate chaining
해시테이블 | HashTable
- 데이터를 효율적으로 관리하기 위해, 고정된 길이의 데이터로 매핑하는 것
- 해시 함수(Hash Function)를 구현하여 데이터 값을 해시 값으로 매핑
해시 함수(Hash Function)
- hashcode: 해시 함수에 의해 반환된 데이터의 고유 숫자 값(key 값)
- hashcode를 알면 빠른 데이터 검색 가능
- 적은 자원으로 많은 데이터를 효율적으로 관리 가능
: 하드디스크, 클라우드 등 무한한 데이터를 유한한 개수의 해시값으로 매핑하여 관리 가능
충돌(collision)
- 어설픈 hash function을 통해서 key 값들을 결정한다면 동일한 값이 도출될 수 있음
- 동일한 key 값에 복수 개의 데이터가 하나의 테이블에 존재하는 상황을 충돌이 일어났다고 표현함
- Collision : 서로 다른 두 개의 키가 같은 인덱스로 hashing(hash 함수를 통해 계산됨을 의미
좋은 해시 함수의 조건
- 일반적으로 좋은 hash function는 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 낸다. 하지만 좋은 해쉬 함수는 키가 어떤 특성을 가지고 있느냐에 따라 달라지게 된다.
- hash function를 무조건 1:1 로 만드는 것보다 Collision 을 최소화하는 방향으로 설계하고 발생하는 Collision 에 대비해 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능하기도 하지만 그런 hash function를 만들어봤자 그건 array 와 다를바 없고 메모리를 너무 차지하게 된다.
- Collision 이 많아질 수록 Search 에 필요한 Time Complexity 가 O(1)에서 O(n)에 가까워진다. 어설픈 hash function는 hash 를 hash 답게 사용하지 못하도록 한다. 좋은 hash function를 선택하는 것은 hash table 의 성능 향상에 필수적인 것이다.
충돌 문제 해결
Open Address 방식 (개방주소법)
- 해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식
Separate Chaining 방식 (분리 연결법) | Chaining(체이닝)
- 체이닝 : 연결리스트로 노드를 계속 추가해나가는 방식 (제한 없이 계속 연결 가능, but 메모리 문제)
연결 리스트를 사용하는 방식(Linked List)
- 각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 Collision 이 발생하면 해당 bucket 의 list 에 추가하는 방식
- 연결 리스트의 특징을 그대로 이어받아 삭제 또는 삽입이 간단하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담이 됨. 데이터 수가 적으면 링크드리스트로 구현하는 것이 유리
Tree 를 사용하는 방식 (Red-Black Tree)
- Tree 를 사용하는 방식 (Red-Black Tree) 기본적인 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다.
해시 버킷 동적 확장(Resize)
- 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능 상 손실이 발생
- key-value 쌍 데이터 개수가 일정 개수 이상(75%)이 되면 해시 버킷의 개수를 두 배로 증가시킴
연결 리스트를 통한 구현
import LinkedList from '../linked-list/LinkedList';
const defaultHashTableSize = 32;
export default class HashTable {
constructor(hashTableSize = defaultHashTableSize) {
// 해시 테이블을 만들고 각 버킷을 빈 연결 리스트로 채움
this.buckets = Array(hashTableSize).fill(null).map(() => new LinkedList());
this.keys = {};
}
// 해시 함수: key 문자열을 해시 번호로 변환
hash(key) {
// 단순화 하기 위해 키의 모든 문자의 문자 코드 합계를 사용하여 해시를 계산합니다.
// 그러나 충돌 횟수를 줄이기 위해 다항식 문자열 해시와 같은 보다 정교한 방식을 사용할 수도 있습니다.
// hash = charCodeAt(0) * PRIME^(n-1) + charCodeAt(1) * PRIME^(n-2) + ... +
// charCodeAt(n-1) 여기서 charCodeAt(i)는 키의 i번째 문자 코드이고
// n은 키의 길이이며 PRIME은 31과 같은 임의의 소수입니다.
const hash = Array.from(key).reduce((hashAccumulator, keySymbol) => {
hashAccumulator + keySymbol.charCodeAt(0)
}, 0);
// 해시 테이블 크기에 맞도록 해시 수를 줄입니다.
return hash % this.buckets.length;
}
set(key, value) {
const keyHash = this.hash(key); // 해시 코드
this.keys[key] = keyHash; // 해시코드를 keys 객체에 저장
// 버킷에서 해시코드에 해당하는 연결 리스트를 가져옴
const bucketLinkedList = this.buckets[keyHash];
// 버킷연결리스트에서 동일한 키를 가진 노드가 있는지 탐색
const node =
bucketLinkedList.find(
{ callback: (nodeValue) => nodeValue.key === key }
);
if (!node) {
// 동일한 키를 가진 노드가 없다면 새 노드를 삽입
bucketLinkedList.append({ key, value });
} else {
// 동일한 키를 가진 노드가 있다면 값 업데이트
node.value.value = value;
}
}
delete(key) {
const keyHash = this.hash(key); // 해시 코드
delete this.keys[key]; //
const bucketLinkedList = this.buckets[keyHash];
const node = bucketLinkedList.find(
{ callback: (nodeValue) => nodeValue.key === key }
);
if (node) {
return bucketLinkedList.delete(node.value);
}
return null;
}
get(key) {
const bucketLinkedList = this.buckets[this.hash(key)];
const node = bucketLinkedList.find(
{ callback: (nodeValue) => nodeValue.key === key }
);
return node ? node.value.value : undefined;
}
has(key) {
return Object.hasOwnProperty.call(this.keys, key);
}
getKeys() {
return Object.keys(this.keys);
}
getValues() {
return this.buckets.reduce((values, bucket) => {
const bucketValues = bucket.toArray()
.map((linkedListNode) => linkedListNode.value.value);
return values.concat(bucketValues);
}, []);
}
}📚 참고
Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
Photo by Alain Pham on Unsplash
protect me from what i want