Hash table

Hash table 은 데이터를 일정한 규칙에 따라 정리하는 방법이다.

Property

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 만큼 걸린다.

table resizing

Hashing 값이 너무 많다면 불필요하게 메모리를 사용하게 되고, 너무 적다면 중복되는 값이 많아 탐색에 어려움을 겪을 것이다.
기존 hash table 의 70% ~ 80% 만큼 차게 될경우 2배 증가시킨다.