Hash Table

ハッシュテーブルとも呼ばれ、キー、値ペアを格納するデータ構造です.
鍵を保存するときにメモリ領域を節約するために、鍵をハッシュ関数という関数を介して特定の数値インデックスに変換して保存します.
キーをインデックスに変換し、配列[インデックス]に入力したキーと値を入れます.
storageには配列の形式が表示され、bucketにはオブジェクトと同じ形式が表示されます.

キー(キー):ハッシュ関数に入力された一意の値で、関数論理から一定の値の形式に変換されます.

値(値):最終的にリポジトリ(bucket,slot)に格納される値は、格納、削除、検索、アクセスのために鍵と一致する必要があります.

ハッシュ(hash):ハッシュ関数が返す値は、リポジトリ内の値と一致して格納されます.

ハッシュ関数(hash function):鍵を受け取り、ハッシュの役割に変換し、異なる長さの鍵を一定の長さのハッシュに変換する.

プロパティ:

は、任意の入力値に対して、常に固定長のハッシュ値を出力する.

入力値のほんの一部を変更するだけで全く異なる結果値(雪崩効果)

を出力することができる.

から出力された結果値から入力値を推定できません.

入力値は、常に同じハッシュ値を出力する.

ハッシュ競合

ハッシュ関数のキー値はカウントできませんが、indexは整数なので、一定の限界があります.
したがって、他のキーでも同じインデックスが作成され、同じ場所に格納されます.
この状況は衝突やハッシュ衝突が発生したことを示している.
ハッシュ関数でハッシュ値を取得しbucketにデータを格納し、ハッシュ値が同じ場合、同じ番号のアドレスにデータを格納しようとします.
このとき発生するのは衝突と呼ばれます.

ハッシュ競合の解決

オープン・アドレス・メソッド

線形調査:

、衝突時に隣の位置が空かどうかをチェック

デュアルハッシュ:最初の関数を継続的に使用する2つの関数を事前に準備し、競合が発生した場合、2番目の関数を使用して別のハッシュ値を取得します.

再ハッシュ:ハッシュ・リストのサイズを増やし、すべてのデータを新しいハッシュ・リストに移行します.

クローズドアドレッシング方法

切寧:上図で競合が発生した後、エントリにチェーンテーブルなどを使用して接続します.

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]
   }
 }
}