ハッシュ テーブルを使用すると、挿入、削除、検索操作の平均パフォーマンス O(1) の連想配列 (ディクショナリ) データ構造を実装できます。
以下は、nodeJS でのハッシュ マップの最も単純な実装の例です。
どのように機能するのでしょうか?手に注意してください:
- ハッシュ マップ内には配列があります
- 配列要素内には、リンクされたリストの最初のノードへのポインタがあります
- メモリはポインタの配列（たとえば、65535 要素）に割り当てられます
- ハッシュ関数を実装しており、辞書キーが入力であり、出力では何でもできますが、最終的には配列要素のインデックスを返します
録音の仕組み:
- 入り口にはキーペアがあります –値
- ハッシュ関数はキーごとにインデックスを返します
- インデックスを使用して配列からリンク リスト ノードを取得する
- キーと一致するかどうかを確認します
- 一致する場合は、値を置き換えます
- 一致しない場合は、必要なキーを持つノードが見つかるまで、次のノードに進みます。
- それでもノードが見つからない場合は、リンク リストの最後にノードを作成します
キーによる検索の仕組み:
- 入り口にはキーペアがあります –値
- ハッシュ関数はキーごとにインデックスを返します
- インデックスを使用して配列からリンク リスト ノードを取得する
- キーと一致するかどうかを確認します
- 一致する場合は値を返します
- 一致しない場合は、必要なキーを持つノードが見つかるまで、次のノードに進みます。
なぜ配列内にリンクされたリストが必要なのでしょうか?ハッシュ関数の計算時に衝突が発生する可能性があるため。この場合、いくつかの異なるキーと値のペアが配列内の同じインデックスに配置されます。この場合、必要なキーを見つけるためにリンク リストが走査されます。
ソース
https://ru.wikipedia.org/wiki/ハッシュ テーブル
https://www.youtube.com/watch?v=wg8hZxMRwcw
ソースコード
https://gitlab.com/demensdeum/data Structures
