해싱 Hashing

• 데이터를 빠르게 저장하고 가져오는 기법 중 하나
• 키에 특정 연산을 적용하여 테이블의 주소를 계산

hash function

• O(1)의 시간복잡도
• 좋은 함수가 되려면, 키 값을 고르게 분포시키고, 해시 충돌이 최소화 되어야 함

해시 테이블

• key, value 쌍을 저장
• 순서가 없다

class HashTable<K, V> {
  private buckets: Map<number, Array<[K, V]>>;
  private size: number;

  constructor(size: number = 1024) {
    this.buckets = new Map<number, Array<[K, V]>>();
    this.size = size;
    // buckets 사이즈 만큼 초기화
    for (let i = 0; i < size; i++) {
      this.buckets.set(i, []);
    }
  }
  
  // hash function	
  private hash(key: K): number {
    const hashString = key.toString();
    let hash = 0;
    for (let i = 0; i < hashString.length; i++) {
      hash = (hash << 5) + hash + hashString.charCodeAt(i);
      hash &= hash; // convert to 32-bit integer
    }
    return hash % this.size;
  }
  
  // 값 저장하기
  public set(key: K, value: V): void {
    const index = this.hash(key);
    const bucket = this.buckets.get(index);
    for (const pair of bucket) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    bucket.push([key, value]);
  }
  
  // 값 불러오기
  public get(key: K): V | undefined {
    const index = this.hash(key);
    const bucket = this.buckets.get(index);
    for (const pair of bucket) {
      if (pair[0] === key) {
        return pair[1];
      }
    }
    return undefined;
  }
  
  // 값 삭제하기	
  public delete(key: K): boolean {
    const index = this.hash(key);
    const bucket = this.buckets.get(index);
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        return true;
      }
    }
    return false;
  }
  
  // 값이 있는지 여부 확인
  public has(key: K): boolean {
    const index = this.hash(key);
    const bucket = this.buckets.get(index);
    for (const pair of bucket) {
      if (pair[0] === key) {
        return true;
      }
    }
    return false;
  }
}