Hash Tables

Introduction

해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업이다.
해시 테이블이란 해싱을 사용하여 데이터를 저장하는 자료구조이다.
적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N 이라고 했을 때 적재율은 K/N 이다. Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 된다.
만약, 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1) 에 수행되지만 충돌이 발생할 경우 탐색과 삭제 연산이 최악에 O(K) 만큼 걸리게 된다

Time Complexity

• lookup: O(1)
• search: O(1)
• insert: O(1)
• delete: O(1)

Constructure

class HashTable {
  constructor(size) {
    this.data = new Array(size);
  }
  table = {};
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.data.length;
    }
    return hash;
  }
  set(key, value) {
    let address = this._hash(key);
    if (!this.data[address]) this.data[address] = [];

    this.data[address].push([key, value]);
    return this.data
  } // O(1)

  get(key) {
    let address = this._hash(key);
    const currentBucket = this.data[address];
    if(currentBucket) {
      for(let i = 0; i < currentBucket.length; i++) {
        if(currentBucket[i][0] === key) return currentBucket[i][1]
      }
    } // O(1) or O(n) 
    return undefined;
  }
  keys () {
    const keysArray = []
    for(let i = 0; i<this.data.length; i++) {
      if(this.data[i]) {
        keysArray.push(this.data[i][0][0])
      }
    }
    return keysArray
  }
}
const myHashTable = new HashTable(50);
myHashTable.set("grapes", 10000);
myHashTable.get("grapes");

Pros and Cons

1)Pros

• Fast lookups
• Fast inserts
• Flexible keys
• Good colision resolution needed

2)Cons

• Unordered
• Slow key iteration
• Tradeoff: more memory O(n)

Example

const solution = (array) => {
  const tempObj = {}
  for(let i = 0; i<array.length; i++) {
    if(tempObj[array[i]]) return array[i]
    tempObj[array[i]] = true
  }
  return undefined
} // O(n)

참조
https://baeharam.netlify.app/posts/data%20structure/hash-table