データ構造ハッシュ表

HashTableって何ですか?

LinkedListを習ってからスケジュールを見て理解しやすくなりました
ハッシュテーブルの仕組みは思ったより簡単!
簡単に言えば

ハッシュ関数に鍵を入れます.

ハッシュ関数は、そのキーと値に含まれるインデックス番号を与える.

キーと値は、対応するインデックス番号に格納されます.

そうなんです!
上の順番と写真を一緒に見ると感じます

では、なぜHash Tableを使うのでしょうか。

はい、データを通常の配列に格納していますが、必要な値を検索するにはauto kが必要ですか?配列の特性を知らない以上、最初から巡回しなければ見つけられません.運が悪ければ、最後まで行けば見つかるのではないでしょうか.短い配列なら大丈夫ですが、データ量が100万や1000万を超えるとどうなりますか?運が悪ければ、1000万回まで確認する必要があるかもしれません.
この場合、ハッシュ・テーブルを使用すると、検索したい鍵をハッシュ関数に挿入し、表示された番号を対応する番号に使用して鍵を検索できます.これにより、より迅速に見つけることができます.メモリも効率よく使えます!

Hash Table Sudoコード

1.Insert
1.1. 空のオブジェクトを作成
1.2. ハッシュ関数に入力したキーと最大長を加え、インデックスを取得します.
1.3. パッケージ[インデックス]が空の場合
1.4. 空のオブジェクトに値を入れます.
1.5. オブジェクトをパッケージに入れます.
1.6. もしなかったら、かばんの中で値上げします.
1.7. サイズ+1
2. Retrieve
2.1. パケット[インデックス]が空の場合、undefinedが返されます.
2.2. パケットのインデックスに鍵を返す
3. Remove
3.1. インデックスにキーがある場合
3.2. deleteとして削除
3.3. サイズ-1
4. Resize
4.1. 現在のパッケージを変数に保存
4.2. 最大パッケージサイズを入力パッケージサイズに変更
4.3. パッケージの内容を初期化
4.4. パッケージサイズのリセット
4.5. 保存したパッケージからinsert関数として実行する

Hash Table jsコード

class HashTable {
  constructor() {
    this._size = 0;
    this._bucketNum = 8;
    this._storage = LimitedArray(this._bucketNum);
  }

  insert(key, value) {
    let obj = {}
    const index = hashFunction(key, this._bucketNum);
    if(this._storage.get(index) === undefined){
      obj[key] = value
      this._storage.set(index, obj)
    }
    else{
      obj = this._storage.get(index)
      obj[key] = value
      this._storage.set(index, obj)
    }
    this._size++
    if(this._size > (this._bucketNum * 0.75)){
    this._resize(this._bucketNum * 2)
    }
  }
  

  retrieve(key) {  /// 현재 한 객체에 다 모여 있는 형태임 ex : {key: value, key: value, key: value, key: value .....}
    const index = hashFunction(key, this._bucketNum);
      if(this._storage.get(index) === undefined){
        return undefined;
      }
      return this._storage.get(index)[key]
  }
  

  remove(key) {
    const index = hashFunction(key, this._bucketNum);
    if(this._storage.get(index)[key]){
      delete this._storage.get(index)[key]
      this._size--
      if(this._size < (this._bucketNum * 0.25)){
        this._resize(this._bucketNum / 2)
        }
    }
    }
 
  _resize(newBucketNum) {
    let oldstorage = this._storage
    this._bucketNum = newBucketNum
    this._storage = LimitedArray(newBucketNum);
    this._size = 0;

    oldstorage.each(obj => {
      for(let key in obj){
        this.insert(key, obj[key])
      }
    })
  return this._storage
  }
}