[Data Structure] Hash Table

해시테이블 = 해시맵

키와 값 쌍을 저장 하고 있는 자료 구조 입니다.
키를 저장 할때에 메모리 공간을 덜 사용할 수 있도록, 키를 해시함수라는 함수를 통해 특정 숫자값 인덱스로 변환후 저장합니다.
그림에서 storege가 저장을 하는 테이블이고 0~7은 해시함수로 변환된 인덱스를 뜻합니다. cat이라는 키가 해시함수를 통해 1로 전환 되어 인덱스1에 feisty 값과 함께 저장 되었습니다. 한 인덱스에 여러 키 값이 저장 되어질 수 있습니다. 그럼 거기 안에서는 buckets이라는 곳에 키와 값이 저장되어 입니다.
storage는 배열의 형태를 띄고 있고 buckets은 객체와 같은 형태를 띄고 있습니다.

자 그럼 코딩해 봅시다.

insert(key, value) - 주어진 키와 값을 저장합니다. 이미 해당 키가 저장되어 있다면 값을 덮어씌웁니다.
retrieve(key) - 주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
_resize(newLimit) - 해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 구현 후 HashTable 내부에서 사용하시면 됩니다.

1. insert(key, value)

insert(key, value) {
	const index = hashFunction(key, this._limit);
	let buckets = {};
 if(this._storage.get(index) === undefied){// 인덱스가 비어있을때
   buckets[key] = value;//새로운값 버켓에 넣기
   this._storage.set(index,buckuts);//_storage에 넣기
 }else{//이미 인덱스 안에 값이 있는경우
   buckets = this._storage.get(index);//빈 버켓에 기존 저장된거 가져오기
   buckets[key] = value;
   this._storage.set(index,buckuts);
 }
 this._size++;// 값을 추가 했으니 사이즈 +1 여기서 사이즈는 채워지는 키값의 갯수이다. 
 const cursize = this._size / this._limit * 100 ;
   if(cursize > 75){// 키값의 갯가 전체 범위에 75%를 넘을 경우 storage를 두배로 확장 해야한다. 
     this._resize(this._limit * 2);// 두배로 확장후 리사이즈 함수에 전달
   }
 }

새로운 키값을 해시테이블에 주입 할때 함수이다.
키가 해시함수를 거쳐 나온 인덱스에 키값이 저장 되는데 저장 될 인덱스에 값이 있는경우와 없는 경우 두가지 경우로 생각하여 값을 넣어 줘야한다.

2.retrieve(key)

retrieve(key) {
  const index = hashFunction(key, this._limit);
  //먼저 해당 인덱스가 있는지 확인하고 그 인덱스에 키가 있는지도 확인해야한다.
  if(this._storage.get(index) === undefined || this._storage.get(index)[key] === undefined){
    return undefined;
  }
  return this._storage.get(index)[key];
}

key를 입력하면 그 키에 해당하는 값을 가져오는 함수 이다.
한개의 인덱스에는 여러 키값이 들어 갈 수 있으므로 먼더 인덱스가 존재하는지도 확인해야 하지만 그 인덱스 안에 키가 존재 하는지도 확인 해야 합니다.

3.remove(key)

remove(key) {
  const index = hashFunction(key, this._limit);
  delete this._storage.get(index)[key];
  this._size--;
  if(this._size / this._limit * 100 < 25){//_storage에 요소가 전체 범위에 25프로 이하로 내려가면 반으로 크기를 줄여 줘야합니다.
      this._resize(this._limit / 2);
    }

객체를 삭제 할때와 똑같이 delete를 이용합니다.

4. _resize(newLimit)

_resize(newLimit) {
	this._limit = newLimit;
  	let curStorage = this._storage;//확장이나 축소전 현재 storage
  this._storage = LimitedArray(this._limit); //늘어나거나 줄어든 new사이즈로 새로 storage생성;
  this._size = 0;// 새로 크기를 변경 했으니 일단 안에 있던 요소들의 수는 0으로 초기화 한다. 새로 담아 줄꺼기 때문에 
  curstorage.each(bucket =>{/
      for(let key in bucket){
        this.insert(key, bucket[key]);
      }
    });
}

사이즈를 축소(요소의 수가 전체범위에 25%이하)하거나 확장(요소의 수가 전체범위에 80%이상)을 한다.
this._storage = LimitedArray(this._limit);
새로 바뀐 제한을 매개변수로 주어 storage사이즈를 변경하고
요소들을 재 배치 해야 하기에 this._size = 0; 요소들 갯수를 초기화 한다. 리사이즈전 storage를 순회 하며 그 안 버켓에 있는 키값을 다시 만든 storage에 insert해준다. 근데 이과정에서 우리는 한가지 주의 할점이 있다. !!!

curstorage.each(bucket =>{//여기서 화살표 안쓰면 this가 curstorage가되서 오류뜸
      for(let key in bucket){// 화살표를 씀으로써 this가 원래 this였던 LimitedArray로 됨
        this.insert(key, bucket[key]);
      }
    });

arrow함수를 이용해주어야 한다. !!화살표 함수는 this를 바인딩 하지 않는다. 그래서 그냥 function이라고 로직을 작성하였다면 this는 curstorage를 가르켜 insert 함수를 사용할 수 없다. 그러나 바인딩 하지 않는 화살표 함수를 이용하면 기존에 this가 가르키고 있던 LimitedArray로 되어 insert를 이용할 수 있다.