Hash table 은 데이터를 일정한 규칙에 따라 정리하는 방법이다.
Hashing : 데이터를 일정한 규칙에 의해 바꾸는 것
Buckets : hashing 한 데이터를 저장하는 곳
const storage = {};
function Hashing(key) {
// 특정 규칙
return // 규칙을 통해 나온 값
}
function input(key, value) {
const hashData = Hashing(key);
storage[hashData] = value;
}
function findValue(key) {
const hashData = Hashing(key);
return storage[hashData];
}
원하는 데이터의 값을 빠르게 찾을수 있다. (단, 중복되는 hashing 값이 없어야 한다.)
hashData 값이 중복될경우, 최악의 경우 모든 데이터의 hashData 가 같은값 일경우,탐색에 값이 중복되거나,
탐색에 시간이 Linked list 만큼 걸린다.
Hashing 값이 너무 많다면 불필요하게 메모리를 사용하게 되고, 너무 적다면 중복되는 값이 많아 탐색에 어려움을 겪을 것이다.
기존 hash table 의 70% ~ 80% 만큼 차게 될경우 2배 증가시킨다.