Hash table

Hash Table

---

Key를 해시 함수를 통해 해싱한 후 나온 결과값을 hash table의 인덱스로 사용하여 데이터를 저장한다. 저장하는 곳은 보통 배열!

해시 함수

• 임의의 길이를 가지고 있는 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 해시 함수가 뱉어내는 결과물을 해시라고 함

해시 함수의 원리

• 해시 테이블의 길이로 나눈 나머지 값을 해시로 사용하기 때문에 해시 테이블의 길이 범위 안에서 해시값이 도출된다.

function _hash(key) {
	return key % myHashTableSize;
}

해시 충돌

• 다른 key값을 넣었지만 같은 해시값을 내놓는 경우 발생하는 충돌

_hash(1000) // 2
_hash(500) // 2

• 동일한 index 위치에 다른 값들이 들어가게 됨

해시 충돌 해결

• 해시 충돌 해결 방법 중 중요한 두가지는 Open Addressing, Separate Chaining
• Open Addressing(개방 주소법)
  • 이 방식은 해시 함수를 통해 얻은 해시값(index)에 동일한 데이터가 저장되어 있으면 해당 index가 아니라 다른 index에 저장하는 방법이다.
  • 다른 index를 찾는 방법에는 여러 가지가 존재
• Separate Chaining(분리 연결법)
  • 해시 테이블 버킷에 하나의 데이터를 저장하는 것이 아닌 링크드 리스트나 트리를 사용하는 방법

set(key, value) {
  let index = this._hash(key);
  if (!this.dataMap[index]) {
  	this.dataMap[index] = [];
  }
  this.dataMap[index].push([key, value]);
}

구현

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

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * 23) % this.dataMap.length;
    }
    return hash;
  }

  set(key, value) {
    let index = this._hash(key);
    if (!this.dataMap[index]) {
      this.dataMap[index] = [];
    }
    this.dataMap.push([key, value]);
    return this;
  }

  get(key) {
    let index = this._hash(key);
    if (this.dataMap[index]) {
      for (let i = 0; i < this.dataMap[index].length; i++) {
        if (this.dataMap[index][i][0] === key) {
          return this.dataMap[index][i][1];
        }
      }
    }
    return undefined;
  }

  keys() {
    let allKeys = [];
    for (let i = 0; i < this.dataMap.length; i++) {
      if (this.dataMap[i]) {
        for (let j = 0; j < this.dataMap[i].length; j++) {
          allKeys.push(this.dataMap[i][j][0]);
        }
      }
    }
    return allKeys;
  }
}