Hash Table

해시 맵이라고도 하며 키, 값 쌍을 저장하고 있는 자료구조이다.
키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 해시함수라는 함수를 통해 특정 숫자값 인덱스로 변환 후 저장한다.
키를 인덱스로 바꿔서 배열[인덱스]에다가 우리가 입력한 키와 값을 넣는 것이다.
storage는 배열의 형태를 띄고 있고, buckest은 객체와 같은 형태를 띄고 있다.

• 키(key): 고유한 값이며, 해시 함수에 입력되어 함수로직에 의해 일정한 값의 형태로 바뀌게 된다.
• 값(value): 저장소(bucket,slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야한다.
• 해시(hash): 해시 함수에서 반환되는 값이며, 저장소에서 값과 매칭되어 저장된다.
• 해시함수(hash function): 키를 받아 해시로 바꿔주는 역할, 다양한 길이를 가지는 키를 일정한 길이를 가지는 해시로 변경한다.
  • 특징:
    • 어떤 입력 값에도 항상 고정된 길이의 해시 값을 출력한다.
    • 입력 값의 아주 일부만 변경되어도 전혀 다른 결과 값을 출력한다(눈사태 효과)
    • 출력된 결과 값을 토대로 입력 값을 유추할 수 없다.
    • 입력 값은 항상 동일한 해시 값을 출력한다.

해시 충돌(collision)

해시 함수의 key의 양은 셀 수 없지만 index는 정수라서 한계가 있따.
그래서 다른 key라도 같은 index를 만들어 내어 같은 곳에 저장하기도 한다.
이런 경우를 collision 혹은 해시 충돌이 일어났다라고 표현한다.
hash function을 통해서 해시값을 얻어 bucket에 데이터를 저장하는 과정에서 해시값이 동일할 경우 같은 번지수의 주소에 데이터를 저장을 시도하게 된다.
이럴때 발생하는 것을 충돌(collision)이라고 한다.

해시 충돌 해결

• 열린 어드레싱 방법(Open Addressing Method)
  • 선형 조사법: 충돌이 발생했을때 옆자리가 비어있는지 살펴보고, 비어 있을경우 그자리에 대신 저장하는 방식
  • 이중 해시: 미리 함수를 두개를 준비해서 첫번째 함수를 지속적으로 사용하다 충돌이 발생하면 두번째 함수를 사용해서 다른 해시값을 갖도록 한다.
  • 재해싱: hash table 크기를 늘리고 새로운 hash table에 모든 데이터를 이주시킨다.
• 닫힌 어드레싱 방법(Closed Addressing Method)
  • 체이닝: 위 그림에서 충돌이 발생한 후 entries에 linked list 등으로 연결하는 방식이다.

Hash Table 구현

class HashTable {
 constructor() {
   this._size = 0;
   this._bucketNum = 8;
   this._storage = LimitedArray(this._bucketNum);
 }
	//주어진 키와 값을 저장한다.
 insert(key, value) {
   if(this._size >= this._bucketNum * 0.75){
     this._resize(this._bucketNum * 2);
   }
   const index = hashFunction(key, this._bucketNum);
   let bucket = [];
   let tuple = [key,value];
   if(!this._storage[index]){
     bucket.push(tuple);
     this._storage[index] = bucket;
   }else{
     //index가 존재 할 경우 덮어쓰기
     for(let element of this._storage[index]){
       if(element[0] === key){
         element[1] = value;
       }else{
         this._storage[index].push(tuple);
       }
     }
   }
   this._size ++;
 }
	//주어진 키에 해당하는 값을 반환, 없다면 undefined를 반환
 retrieve(key) {
   const index = hashFunction(key, this._bucketNum);
   if(this._storage[index]){
     for(let element of this._storage[index]){
       if(element[0] === key){
         return element[1];
       }
     }
   }
 }
	//주어진 키에 해당하는 값을 삭제하고 값을 반환, 없다면 undefined를 반환
 remove(key) {
   if(this._size <= this._bucketNum * 0.25){
     this._resize(this._bucketNum / 2);
   }
   const index = hashFunction(key, this._bucketNum);
   let bucket = this._storage[index];
   let result ;
   if(bucket){
     for(let element of bucket){
       if(element[0] === key){
         result = bucket.splice(bucket.indexOf(element),1);
       }
     }
   }
   this._size--;
   return result;
 }
	//해시 테이블의 스토리지 배열을 newBucketNum으로 리사이징하는 함수 
	//해시 테이블에 저장된 key-value 쌍이 bucketNum의 75%를 넘는 경우 bucketNum을 2배로 늘리고, 
	//25%보다 작아지는 경우 bucketNum을 절반으로 줄인다.
	//리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 한다
	//구현 후 HashTable 내부에서 사용하시면 된다.
 _resize(newBucketNum) {
   let perStorage = this._storage; // 구
   this._bucketNum = newBucketNum;
   this._storage = LimitedArray(newBucketNum)// 신 
   //구 > 신 이주
   for(let i in perStorage){
     this._storage[i] = perStorage[i]
   }
 }
}