JS: Hash Map & Hash Function

Hash Map(Hash Table)이란?

Hash Map: 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하여 검색을 빠르게 하기 위한 자료 구조이다. 데이터가 저장되는 곳을 버킷 또는 슬롯이라고 한다.

해시테이블의 기본 연산: 삽입, 삭제, 탐색

JS에서 Hash Map 1. Object

let obj = {
  Yul: "555-1234",
  Mel: "491-0322"
}

JS에서 Hash Map 2. Map

const collection = new Map();

collection.set("Nathan", "555-0182");
collection.set("Jane", "555-0182");
// 아래와 같이도 사용 가능 
collection["Yul"] = "625-1234";

console.log(collection.get("Nathan")); // 555-0182
console.log(collection.size); // 2

JS로 Hash Map 구현하기

Hash Map 구현 순서

• HashTable Class 생성
• hash() 함수 생성
• set() / get() 함수를 통해 key/value pair를 삽입하고 탐색

HashTable Class 생성

class HashTable {
  constructor() {
    this.table = new Array(127);
    this.size = 0;
  }
}

hash() 함수 생성

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.table.length; // key < 127
}

set() / get() 함수를 통해 key/value pair를 삽입하고 탐색

set(key, value) {
  const index = this._hash(key);
  this.table[index] = [key, value];
  this.size++;
}

get(key) {
  const index = this._hash(key);
  return this.table[index];
}

HashMap의 해시 충돌 (Hash Collision)

• hash 함수가 두 개의 다른 값에 같은 키를 생성할 때, 해시 충돌이 발생한다.

해시 충돌이 발생했을 때, 사용할 수 있는 두 가지 방법

1. Open Addressing
2. Chaining

Open Addressing:

Chaining:

Linear Probing

If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S

Quadratic Probing

If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S

Double Hashing

If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S
hash(x) = x % 7
hash2(x) = 1 + (x % 5)

Work Cited

https://www.freecodecamp.org/news/javascript-hash-table-associative-array-hashing-in-js/
https://jarednielsen.com/data-structure-hash-table-linear-probing/
https://jarednielsen.com/data-structure-hash-table-separate-chaining/
https://stackoverflow.com/questions/2556142/chained-hash-tables-vs-open-addressed-hash-tables