[Hash Table] 배열과 달리 비연속적인 공간에 데이터를 저장

배열이 데이터를 메모리에 연속으로 따닥따닥 보관했다면,

 

해시테이블은 메모리 이곳저곳에 랜덤으로 자료를 보관한다.

 

해시테이블은 언어에 따라 명칭이 다르지만, 모두 가지고 있는 중요한 자료구조다.

 

해시테이블은 key-value 쌍으로 이루어져 있는데, 여기서의 key는 배열에서 숫자 인덱스 역할을 한다.

 

배열은 데이터들이 0번칸부터 차례로 존재했기 때문에, 맨뒤 원소를 제외한 데이터의 추가/삭제를 하려면 인덱스 전체를 다시 싹 뜯어고쳐야하므로 O(n)의 시간이 소요됐다.

 

하지만 해시테이블은 key를 Hash Function에 넣어서 나온 해시를 메모리 주소로 하는 장소에 데이터를 보관하기 때문에, 주소의 중복만 일어나지 않는다면 O(1)의 시간복잡도를 가진다.

 

다시 말해, 같은 key값은 언제나 같은 해시를 갖지만, 서로 다른 key라도 언제나 다른 주소를 반환하지 않을 수 있다는 것이다.

 

그래서 Hash Collision을 해결하기 위해 겹친 칸 안에서는 Linked List로 데이터들을 연결해준다.

 

---

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }

  _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) {
    const index = this._hash(key);
    if (!this.data[index]) {
      this.data[index] = [];
    }
    this.data[index].push([key, value]);
    return this.data
  } // O(1)

  get(key) {
    const index = this._hash(key);
    const currentRoom = this.data[index];
    if (currentRoom) {
      for (let i=0; i < currentRoom.length; i++) {
        if (currentRoom[i][0] === key) {
          return currentRoom[i][1];
        }
      }
    return undefined;
    }
  } // O(1) ~ O(n)-충돌시

}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
myHashTable.get('grapes')

---

https://www.cs.usfca.edu/~galles/visualization/OpenHash.html

Open Hashing Visualization