[JS]알고리즘 문제풀이1_해시테이블 활용

해시테이블의 개념을 활용한 알고리즘 문제이다. 해시테이블화 해시함수에 대한 설명은 블로그에서 정리해두었으니

아래 링크 들어가서 참고하면 좋을 듯 하다!

https://hazel-developer.tistory.com/2

해시테이블(HashTable)과 해시함수(HashFunction)에 대해서

두 문제 모두 동일한 유형의 문제이나, 해시테이블 resize를 다루느냐 다루지 않느냐 차이 뿐이라 같이다뤄보고자 한다.

 

첫 번째 문제

/**
 * Create a hash table with `insert()`, `retrieve()`, and `remove()` methods.
 * The hashtable does not need to resize but it should still handle collisions.
 */
 
var makeHashTable = function () {
  var result = {}; // 해시값과 value의 짝
  var storage = []; //result 안에 해시값으르 가지는 value의 linkedlist 저장소
  var storageLimit = 1000;
  result.insert = function (key, value) {
    let index = getIndexBelowMaxForKey(key, storageLimit);
    if (result[index] === undefined) {
      //let storage = []; //result 안에 해시값으르 가지는 value의 linkedlist 저장소
      storage.push([key, value]);
      result[index] = storage; //result = {index: [(key,value),(key2,value2)] , index2:[(key,value)]}
      storage = [];
    } else {
      storage = result[index]; // [(key,value),(key2,value2)]
      let flag = false;
      for (let i = 0; i < storage.length; i++) {
        if (storage[i][0] === key) {
          //이 경우는 이미 있는 값을 변경하고 싶을때,
          storage[i][1] = value;
          flag = true;
        }
      }
      if (flag === false) {
        storage.push([key, value]);
      }
      storage = [];
    }
  };
 
  result.retrieve = function (key) {
    let index = getIndexBelowMaxForKey(key, storageLimit);
    if (result[index]) {
      //result = {index: [[key,value],[key2,value2]] , index2:[[key,value]]}
      storage = result[index]; // [[key,value],[key2,value2]]
      for (let i = 0; i < storage.length; i++) {
        if (storage[i][0] === key) {
          return storage[i][1];
        }
      }
    } else {
      return undefined;
    }
  };
 
  result.remove = function (key) {
    let index = getIndexBelowMaxForKey(key, storageLimit);
    if (result[index]) {
      storage = result[index]; // [[key,value],[key2,value2]]
      for (let i = 0; i < storage.length; i++) {
        if (storage[i][0] === key) {
          storage[i].splice(i, 1);
        }
      }
      return storage;
    }
    return undefined;
  };
 
  return result;
};
 
// This is a "hashing function". You don't need to worry about it, just use it
// to turn any string into an integer that is well-distributed between
// 0 and max - 1
var getIndexBelowMaxForKey = function (str, max) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash = hash & hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};
 

 

두번째 문제

resize가 추가된 해시테이블 문제.

/**
 * Create a hash table with `insert()`, `retrieve()`, and `remove()` methods.
 * Be sure to handle hashing collisions correctly.
 * Set your hash table up to double the storage limit as
 * soon as the total number of items stored is greater than
 * 3/4th of the number of slots in the storage array.
 * Resize by half whenever utilization drops below 1/4.
 */
 
var makeHashTable = function () {
  var result = {};
  var storage = [];
  var storageLimit = 4;
  var size = 0;
  result.insert = function (key, value) {
    //insert에서는 넣을때 마다 size를 +1 해주고, storageLimit을 점검해서 resize해줘야 한다.
    let oldLimit = storageLimit; //resize 위해 추가해준 부분
    if (size >= oldLimit * 0.75) {
      storageLimit = storageLimit * 2; //리미트를 정수화? 해줄 필요가 잇을까용? 일단 테스트는 통과했습니다.
    }
    let index = getIndexBelowMaxForKey(key, storageLimit);
    if (result[index] === undefined) {
      storage.push([key, value]);
      result[index] = storage; //result = {index: [[key,value],[key2,value2]] , index2:[[key,value]]}
      storage = [];
      size++;
    } else {
      storage = result[index]; // [[key,value],[key2,value2]]
      let flag = false;
      for (let i = 0; i < storage.length; i++) {
        if (storage[i][0] === key) {
          //이 경우는 이미 있는 값을 변경하고 싶을때,
          storage[i][1] = value;
          flag = true;
        }
      }
      if (flag === false) {
        storage.push([key, value]);
        size++;
      }
      storage = [];
    }
  };
 
  result.retrieve = function (key) {
    //여기는 resize 필요X
    let index = getIndexBelowMaxForKey(key, storageLimit);
    if (result[index]) {
      //result = {index: [[key,value],[key2,value2]] , index2:[[key,value]]}
      storage = result[index]; // [[key,value],[key2,value2]]
      for (let i = 0; i < storage.length; i++) {
        if (storage[i][0] === key) {
          return storage[i][1];
        }
      }
    } else {
      return undefined;
    }
  };
 
  result.remove = function (key) {
    //요소를 하나씩 뺄때마다 size 를 하나씩 줄이고 resize는 가장 최종에 해준다. 메소드 시작 전에 resize 했던 insert와 다른점
    let index = getIndexBelowMaxForKey(key, storageLimit);
    if (result[index]) {
      storage = result[index]; // [[key,value],[key2,value2]]
      for (let i = 0; i < storage.length; i++) {
        if (storage[i][0] === key) {
          storage[i].splice(i, 1);
          size--;
        }
      }
      let oldLimit2 = storageLimit;
      if (size <= oldLimit2 * 0.25) {
        storageLimit = storageLimit * 0.5;
      }
      return storage;
    }
    return undefined;
  };
 
  return result;
};
 
// This is a "hashing function". You don't need to worry about it, just use it
// to turn any string into an integer that is well-distributed between
// 0 and max - 1
var getIndexBelowMaxForKey = function (str, max) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash = hash & hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};
 

 

우선 테스트는 통과했는데, resize 해줄 때, storageLimit을 정수화 해줄 필요가 있을까?

알고리즘 코드 리뷰할때 한번 이야기해봐야겠다!

 

기존의 풀이 방식에서 나는 해시함수에서 객체 자체를 활용했다.

index 활용 및 배열로써 정리하는 것이 좀 더 해시함수의 개념에 부합하다고 보았고

코드를 수정했다.

리사이즈 부분에 대한 개념은 다르지 않아서 해시테이블에 대해 정의 한 코드만 수정했다.

 

수정버전

var makeHashTable = function () {
  var result = {}; // 해시테이블 자체
  var storage = []; //result 안에 실제 값들을 저장하는 저장소, result = {[[[key,value],[key, value2]],[]]} 이런 형태
  //result 안에 storage가 들어있고, 실제로 storage에 값이 쌓임. 해시 충돌을 대비해서 storage 안에 실제 값이 모여있는 bucket 생성 필요
  var storageLimit = 1000;
  result.insert = function (key, value) {
    let index = getIndexBelowMaxForKey(key, storageLimit);
    let bucket = storage[index] || [];
    if (storage[index] === undefined) {
      //let storage = []; //result 안에 해시값으르 가지는 value의 linkedlist 저장소
      bucket.push([key, value]);
      storage[index] = bucket;
    } else {
      let flag = false;
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          //이 경우는 이미 있는 값을 변경하고 싶을때,
          bucket[i][1] = value;
          flag = true;
        }
      }
      if (flag === false) {
        bucket.push([key, value]);
      }
    }
  };
 
  result.retrieve = function (key) {
    let index = getIndexBelowMaxForKey(key, storageLimit);
    let bucket = storage[index] || [];
    if (storage[index]) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          return bucket[i][1];
        }
      }
    } else {
      return undefined;
    }
  };
 
  result.remove = function (key) {
    let index = getIndexBelowMaxForKey(key, storageLimit);
    let bucket = storage[index] || [];
    if (storage[index]) {
      for (let i = 0; i < bucket.length; i++) {
        if (bucket[i][0] === key) {
          bucket[i].splice(i, 1);
        }
      }
      return bucket;
    }
    return undefined;
  };
 
  return result;
};
 
// This is a "hashing function". You don't need to worry about it, just use it
// to turn any string into an integer that is well-distributed between
// 0 and max - 1
var getIndexBelowMaxForKey = function (str, max) {
  var hash = 0;
  for (var i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash = hash & hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};