해시 테이블

해시 테이블은 고정된 크기의 자료 구조로 처음에 크기가 정해진다.

해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고 키-값 쌍을 기반으로 자료를 얻을 수 있다.자바스크립트에서 객체는 해시 테이블과 같은 방식으로 키(속성)와 해당 키의 연관된 값을 정의하는 방식으로 동작한다.

해시 테이블에는 put()과 get()이라는 함수가 있다. 시간복잡도 O(1)

ex) localStorage

 

해싱 기법

좋은 해시 함수가 되기 위한 요구 사항

1. 결정성 : 동일한 키는 동일한 해시 값을 생성해야 한다.

2. 효율성 : 시간 복잡도가 O(1)이어야 한다.

3. 균일한 분배 : 배열 전체를 최대한 활용해야 한다.

 

소수 해싱 : 소수를 사용한 모듈러 나눗셈이 균일한 방식으로 배열 인덱스를 생성한다.

=> 충돌이 발생

 

선형 탐사 : 한 번에 한 인덱스를 증가시킴으로써 사용 가능한 인덱스를 찾는다. 

책

// Start of: Linear Probing -----------------------------------
function HashTable(size) {
  this.size = size;
  this.keys = this.initArray(size);
  this.values = this.initArray(size);
  this.limit = 0;
}

HashTable.prototype.initArray = function(size) {
  var array = [];
  for (var i = 0; i < size; i++) {
      array.push(null);
  }
  return array;
}

HashTable.prototype.put = function(key, value) {
  if (this.limit >= this.size) throw 'hash table is full'

  var hashedIndex = this.hash(key);

  // Linear probing
  while (this.keys[hashedIndex] != null) {
      hashedIndex++;

      hashedIndex = hashedIndex % this.size;

  }

  this.keys[hashedIndex] = key;
  this.values[hashedIndex] = value;
  this.limit++;
}

HashTable.prototype.get = function(key) {
  var hashedIndex = this.hash(key);

  while (this.keys[hashedIndex] != key) {
      hashedIndex++;

      hashedIndex = hashedIndex % this.size;

  }
  return this.values[hashedIndex];
}

HashTable.prototype.hash = function(key) {
  // Check if int
  if (!Number.isInteger(key)) throw 'must be int';
  return key % this.size;
}

var exampletable = new HashTable(13);
exampletable.put(7, "hi");
exampletable.put(20, "hello");
exampletable.put(33, "sunny");
exampletable.put(46, "weather");
exampletable.put(59, "wow");
exampletable.put(72, "fourty");
exampletable.put(85, "happy");
exampletable.put(98, "sad");
// End of: Linear Probing ------------------------------------0

 

class 기법으로 바꾸고 몇 개 코드 수정

class HashTable {
  constructor(size) {
    this.size = size;
    this.keys = this.initArray(size);
    this.values = this.initArray(size);
    this.limit = 0;
  }
  initArray(size) {
    let arr = [];
    for (let i = 0; i < size; i++) {
      arr.push(null);
    }
    return arr;
  }
  put(key, value) {
    if (this.limit >= this.size) throw "hash table is full";

    let hashIdx = this.hash(key);
    while (this.keys[hashIdx] !== null) {
      hashIdx++;
      hashIdx %= this.size;
    }
    this.keys[hashIdx] = key;
    this.values[hashIdx] = value;
    this.limit++;
  }
  get(key) {
    let hashIdx=this.hash(key);
    while(this.keys[hashIdx]!==key){
      hashIdx++;
      hashIdx %= this.size;
    }
    return this.values[hashIdx];
  }
  hash(key) {
    return key % this.size;
  }
}

var exampletable = new HashTable(13);
exampletable.put(7, "hi");
exampletable.put(20, "hello");
exampletable.put(33, "sunny");
exampletable.put(46, "weather");
exampletable.put(59, "wow");
exampletable.put(72, "fourty");
exampletable.put(85, "happy");
exampletable.put(98, "sad");
console.log(exampletable);

 

단점 : 군집cluster이 쉽게 발생.

 

이차 탐사 : 군집 문제를 해결하는 데 좋은 기법. 완전 제곱을 사용

// Start of: Quadratic Probing --------------------------------
HashTable.prototype.put = function(key, value) {
    if (this.limit >= this.size) throw 'hash table is full'

    var hashedIndex = this.hash(key),
        squareIndex = 1;

    // quadratic probing
    while (this.keys[hashedIndex % this.size] != null) {
        hashedIndex += Math.pow(squareIndex, 2);
        squareIndex++;
    }

    this.keys[hashedIndex % this.size] = key;
    this.values[hashedIndex % this.size] = value;
    this.limit++;
}

HashTable.prototype.get = function(key) {
    
    var hashedIndex = this.hash(key),
        squareIndex = 1;

    while (this.keys[hashedIndex % this.size] != key) {
        hashedIndex += Math.pow(squareIndex, 2);
        hashedIndex = hashedIndex % this.size;
        squareIndex++;
    }
    return this.values[hashedIndex % this.size];
}
// End of: Quadratic Probing ----------------------------------

 

 

 

재해싱/이중 해싱

키를 균일하게 분배하는 또 다른 좋은 방법으로 이차 해싱 함수를 사용해 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하는 것이 있다. 다음은 좋은 두 번째 해싱 함수가 지녀야 할 세 가지 주요 요구 사항이다.

일반적인 이차 해시 함수 : hash₂(x)=R-(x%R)  (x는 첫번째 해시의 결과, R은 해시 테이블의 크기보다 작다)

1. 달라야 함 : 두 번째 해싱 함수가 키를 더 잘 분배하기 위해서는 첫 번째 해싱 함수와 달라야 한다.

2. 효율적이어야 함 : 두 번째 해싱 함수의 시간 복잡도가 여전히 O(1)이어야 한다.

3. 0이 아니어야 함 : 두 번째 해싱 함수의 결과가 0이 돼서는 안 된다. 0은 초기 해시 값을 결과로 내기 때문이다.

// Star of: Double Hashing with Linear Probing ----------------
HashTable.prototype.put = function(key, value) {
    if (this.limit >= this.size) throw 'hash table is full'

    var hashedIndex = this.hash(key);

    while (this.keys[hashedIndex] != null) {
        hashedIndex++;

        hashedIndex = hashedIndex % this.size;

    }
    this.keys[hashedIndex] = key;
    this.values[hashedIndex] = value;
    this.limit++;
}

HashTable.prototype.get = function(key) {
    var hashedIndex = this.hash(key);

    while (this.keys[hashedIndex] != key) {
        hashedIndex++;

        hashedIndex = hashedIndex % this.size;

    }
    return this.values[hashedIndex];
}

HashTable.prototype.hash = function(key) {
    if (!Number.isInteger(key)) throw 'must be int'; // check if int
    return this.secondHash(key);
}

HashTable.prototype.secondHash = function(hashedKey) {
    var R = this.size - 2;
    return R - hashedKey % R;
}