15Dec2019 TIL

Today I learned : 

• Hash Table Implementation

 

---

 

오늘의 생각 : 

오늘 꽃꽃이는 향나무를 가지고 크리스마스 트리를 만들었다! 너무 귀엽다 ㅠㅠ
조만간 블로그에 취미 생활에 대한 포스팅을 해야지! (도대체 언제 할건지..ㅎㅎ;;)

구글링과 학습 자료를 통해서 해쉬 테이블 리사이징 하는 부분 구현을 해냈다.

코드가 보기 좋게 작성된 건 아니지만, 일단 기능이 내가 의도한 대로 작동하는 것에 만족.

 

화상 영어 30분 하고, 저녁 간단하게 삶은 계란으로 해결하고,

집 앞 공원 산책 30분 하고, 집안일 하고, 사피엔스 2챕터 읽고 자면 주말 끝! 

 

다음 주 일요일은 달랏에 여행갈 거니 이번주는 빡세게 열공+운동+열일 해야지!

 

Hash Table - Pseudoclassical Style 로 구현하기 

(나는 왕초보니까..  하단의 코드는 좋은 답이 절대절대 아님을 참고해주시길^^;;)

일단, Hash Table의 기본 전제 코드는 다음과 같다.

const LimitedArray = function(limit) {
  const storage = [];

  const limitedArray = {};
  limitedArray.get = function(index) {
    checkLimit(index);
    return storage[index];
  };
  limitedArray.set = function(index, value) {
    checkLimit(index);
    storage[index] = value;
  };
  limitedArray.each = function(callback) {
    for (let i = 0; i < storage.length; i++) {
      callback(storage[i], i, storage);
    }
  };

  var checkLimit = function(index) {
    if (typeof index !== "number") {
      throw new Error("setter requires a numeric index for its first argument");
    }
    if (limit <= index) {
      throw new Error("Error trying to access an over-the-limit index");
    }
  };

  return limitedArray;
};

const getIndexBelowMaxForKey = function(str, max) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash &= hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};

 

내가 구현한 Hash Table Code 는 다음과 같다. (정답 아님 주의! 코드 더러움 주의!)

const HashTable = function() {
  this._limit = 8;
  this._storage = LimitedArray(this._limit);
  this._length = 0;
  this._cashe = {};
};

HashTable.prototype.checkSize = function() {
  if (this._length >= this._limit * 0.75) this.resizeUp();
  else if (this._length < this._limit * 0.25) this.resizeDown();
  else this.sizeSame();
};

HashTable.prototype.resizeUp = function() {
  this._limit = this._limit * 2;
  let newStorage = LimitedArray(this._limit);
  for (let key in this._cashe) {
    const index = getIndexBelowMaxForKey(this._cashe[key], this._limit);
    newStorage[index] = key;
  }
  this._storage = newStorage;
};

HashTable.prototype.resizeDown = function() {
  this._limit = (this._limit * 1) / 2;
  let newStorage = LimitedArray(this._limit);
  for (let key in this._cashe) {
    const index = getIndexBelowMaxForKey(this._cashe[key], this._limit);
    newStorage[index] = key;
  }
  this._storage = newStorage;
};

HashTable.prototype.sizeSame = function() {
  this._limit;
};

HashTable.prototype.insert = function(k, v) {
  if (!(v in this._cashe)) {
    this._length++;
    this.checkSize();
    const index = getIndexBelowMaxForKey(k, this._limit);
    if (index in this._storage) {
      this.resizeUp();
      const index = getIndexBelowMaxForKey(k, this._limit);
      this._storage[index] = v;
      this._cashe[v] = k;
    }
    this._storage[index] = v;
    this._cashe[v] = k;
  }
};

HashTable.prototype.retrieve = function(k) {
  const index = getIndexBelowMaxForKey(k, this._limit);
  return this._storage[index];
};

HashTable.prototype.remove = function(k) {
  const index = getIndexBelowMaxForKey(k, this._limit);
  if (index in this._storage) {
    delete this._cashe[this._storage[index]];
    delete this._storage[index];
    this._length = Object.keys(this._cashe).length;
    this.checkSize();
  }
};