ZTM Data Structures & Algorithms - Hash Tables

udemy 에서 Master the Coding interview: Data Structures & Algorithms 강의를 수강한 내용을 정리하는 포스팅입니다.

---

Hash Tables

https://en.wikipedia.org/wiki/Hash_table

Hash table - Wikipedia

-해시테이블은 입력값(키-값 페어)을 해시 함수를 거쳐 해시값을 구한뒤 해시값을 메모리주소를 가리키게해서 입력값을 해당 메모리 주소에 저장하는 자료구조이다. 

자료가 저장될때는 키-값 페어 둘다 메모리에 저장한다.

-자바스크립트로 직접 해시 테이블을 구현한다면 아래와 같은 형태로 구현해볼 수 있다. 

class HashTable {
  constructor(size){
    this.data = new Array(size);
    // this.data = [];
  }
 
  _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;
  }
 
  get(key){
    const 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]
        }
      }
    }
    return undefined;
  }
}
 
const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')
myHashTable.set('apples', 9)
myHashTable.get('apples')

 

-해시함수가 간혹 다른 입력에 대해 똑같은 해시값을 출력하는 경우가 있으며 Hash Collision 이라고 한다. 
-해시값 충돌이 될경우 위의 사진처럼 같은 메모리 주소에 여러개의 정보가 들어갈수 있으며 이경우 해시테이블의 구현방법에 따라 중복데이터 저장방법이 달라진다. (위의 사진에서는 linked list를 활용)
-시간 복잡도의 경우 해시충돌이 일어나지 않는 다는 가정하에 데이터 삽입, 삭제, 검색 모두 O(1)으로 매우 빠르지만 ...
-최악의 경우 해시값이 모두 충돌한다면 데이터 삽입 삭제 검색 모두 O(n)이 걸릴 수도 있다. 
-빌트인 해시함수의 경우 대부분 언어별로 최적화가 되어있기 때문에 해시함수를 실행하는 시간은 빅오 계산에서 포함시기키지 않는다. (물론 직접 해시테이블과 해시함수를 구현할 경우 해시함수가 실행이 오래걸릴수도 있다.)

-해시테이블은 공간복잡도를 희생한 대신(데이터를 키-값 페어로 저장하므로) 키를 통해서 데이터를 바로 빠르게 접근 가능하기 때문에 아래와 같은 장단점이 존재 한다.