JavaScriptで簡単なハッシュテーブルを実装する方法

どれくらい美しいです{}か?

キーごとに値を保存し、非常にコスト効率の高い方法で値を取得できます(O(1)これについては後で詳しく説明します)。

この投稿では、非常に基本的なハッシュテーブルを実装し、その内部の仕組みを見て、コンピュータサイエンスで最も独創的なアイデアの1つを説明したいと思います。

問題

新しいプログラミング言語を構築していると想像してみてください。まず、非常に単純な型(文字列、整数、浮動小数点数など)を使用してから、非常に基本的なデータ構造の実装に進みます。最初に配列([])を思い付き、次にハッシュテーブル(別名、辞書、連想配列、ハッシュマップ、マップ、そして…リストが続きます)が思い浮かびます。

それらがどのように機能するのか疑問に思ったことはありませんか?彼らはどうしてそんなに速いの?

まあ、聞かせてのは、JavaScriptを持っていなかったと言う{}new Map()、と私たちの非常に自身を実装してみましょうDumbMap

複雑さに関する注記

ボールを転がす前に、関数の複雑さがどのように機能するかを理解する必要があります。ウィキペディアには計算の複雑さに関する優れた復習がありますが、怠惰なものについて簡単に説明します。

複雑さは、関数に必要なステップ数を測定します。ステップが少ないほど、実行が速くなります(「実行時間」とも呼ばれます)。

次のスニペットを見てみましょう。

function fn(n, m) { return n * m}

の計算の複雑さ(これからは単に「複雑さ」)fnO(1)、一定であることを意味します(O(1)コストは1つ読むことができます)。どの引数を渡しても、このコードを実行するプラットフォームは1つの操作を実行するだけで済みます。 (に乗算nしますm)。繰り返しますが、これは1つの操作であるため、コストはと呼ばれO(1)ます。

複雑さは、関数の引数が非常に大きな値を持つ可能性があると想定して測定されます。この例を見てみましょう:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

その複雑さはO(3)正しいと思いますか?

繰り返しますが、複雑さは非常に大きな引数のコンテキストで測定されるため、定数を「ドロップ」してO(3)、と同じと見なす傾向がありO(1)ます。したがって、この場合でも、の複雑さはfnですO(1)nとの値に関係なくm、常に3つの操作を実行することになります。これも一定のコストです(したがってO(1))。

この例は少し異なります。

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

ご覧のとおり、の値と同じ回数ループしています。nこれは数百万に達する可能性があります。この場合、O(n)引数の1つの値と同じ数の操作を実行する必要があるため、この関数の複雑さをとして定義します。

他の例?

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

この例では2 * n時間をループしますO(2n)。つまり、複雑さはである必要があります。関数の複雑さを計算するときに定数は「無視される」と述べたので、この例もに分類されO(n)ます。

もう1つ?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

ここでは、ループオーバーnしてメインループ内で再度ループしています。つまり、複雑さは「2乗」(n * nnです。2の場合はs.push(m)4回実行し、3の場合は9回実行します。

この場合、関数の複雑さはと呼ばれO(n²)ます。

最後の例は?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

この場合、ネストされたループはありませんが、2つの異なる引数を2回ループしO(n+m)ます。複雑さはとして定義されます。クリスタルクリア。

複雑さについて簡単に紹介(または復習)したので、複雑さのある関数は、のある関数O(1)よりもはるかに優れたパフォーマンスを発揮することを理解するのは非常に簡単O(n)です。

ハッシュテーブルにはO(1)複雑さがあります。素人の言葉で言えば、それらは超高速です。次へ移りましょう。

(私はいつもO(1)複雑なハッシュテーブルにちょっと横たわっていますが、読んでください;))

(ダム)ハッシュテーブルを作成しましょう

ハッシュテーブルには2つの簡単なメソッドがあります—set(x, y)get(x)。いくつかのコードを書き始めましょう:

そして、これらのキーと値のペアを格納し、後で取得するための非常に単純で非効率的な方法を実装しましょう。まず、それらを内部配列に格納することから始めます({}実装しているため、使用できないことを忘れないでください{}—驚かされます!):

次に、リストから適切な要素を取得するだけです。

私たちの完全な例:

私たちDumbMap がすごい!箱から出してすぐに機能しますが、キーと値のペアを大量に追加するとどのように機能しますか?

簡単なベンチマークを試してみましょう。最初に、要素が非常に少ないハッシュテーブルで存在しない要素を見つけようとし、次に、要素が多いハッシュテーブルで同じことを試みます。

結果?それほど勇気づけられない:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

私たちの実装ではthis.list、一致するキーを持つ要素を見つけるために、内部のすべての要素をループする必要があります。コストはですO(n)、そしてそれはかなりひどいです。

速くする(er)

置くための時間:私たちは私たちのリストをループ回避する方法を見つける必要があるハッシュへのバックハッシュテーブルを

このデータ構造がなぜハッシュテーブルと呼ばれるのか疑問に思ったことはありませんか?これは、設定して取得するキーにハッシュ関数が使用されているためです。この関数を使用してキーを整数iに変換し、値をi内部リストのインデックスに格納します。リストから要素にインデックスでアクセスするには一定のコスト(O(1))があるため、ハッシュテーブルのコストもO(1)。になります。

これを試してみましょう:

ここでは、文字列を数値ハッシュに変換するだけのstring-hashモジュールを使用しています。これを使用してhash(key)、リストのインデックスにある要素を格納およびフェッチします。結果?

with lots of records in the map: 0.013ms

W — O — W.これが私が話していることです!

リスト内のすべての要素をループする必要はなく、要素の取得DumbMapは非常に高速です。

これをできるだけ簡単に言えば、ハッシュはハッシュテーブルを非常に効率的にするものです。魔法はありません。これ以上何もない。灘。シンプルで、賢く、独創的なアイデアです。

適切なハッシュ関数を選択するためのコスト

もちろん、高速ハッシュ関数を選択することは非常に重要です。私たちの場合はhash(key)数秒で実行し、私達の機能は非常に遅いにかかわらず、その複雑になります。

同時に、ハッシュテーブルの複雑さに悪影響を与えるため、ハッシュ関数が多くの衝突を生成しないようにすることが非常に重要です。

混乱していますか?衝突を詳しく見てみましょう。

衝突

ああ、優れたハッシュ関数は衝突を生成しない!」:まあ、現実の世界に戻って考え直してください。GoogleはSHA-1ハッシュアルゴリズムの衝突を生成することができました。ハッシュ関数が2つの異なる入力に対して同じハッシュをクラックして返す前に、それは時間または計算能力の問題です。ハッシュ関数が衝突を生成すると常に想定し、そのような場合に対して適切な防御を実装してください。

適切な例としてhash()、多くの衝突を生成する関数を使用してみましょう。

この関数は、10個の要素の配列を使用して値を格納します。これは、要素が置き換えられる可能性が高いことを意味します。これは、次の厄介なバグですDumbMap

この問題を解決するために、複数のキーと値のペアを同じインデックスに格納するだけで済みます。それでは、ハッシュテーブルを修正しましょう。

お気づきかもしれませんが、ここでは元の実装にフォールバックします。キーと値のペアのリストを保存し、それぞれをループします。リストの特定のインデックスに多くの衝突がある場合、これは非常に遅くなります。

hash()1から10までのインデックスを生成する独自の関数を使用してこれをベンチマークしましょう。

with lots of records in the map: 11.919ms

からのハッシュ関数を使用して、string-hashランダムインデックスを生成します。

with lots of records in the map: 0.014ms

うわあ!適切なハッシュ関数を選択するにはコストがかかります。それ自体で実行速度が低下しないほど高速であり、多くの衝突が発生しないほど十分に高速です。

一般的にO(1)

私の言葉を覚えていますか?

ハッシュテーブルにはO(1)複雑さがあります

まあ、私は嘘をついた:ハッシュテーブルの複雑さはあなたが選ぶハッシュ関数に依存する。生成する衝突が多いほど、複雑さが増す傾向がありO(n)ます。

次のようなハッシュ関数:

function hash(key) { return 0}

これは、ハッシュテーブルの複雑さがO(n)。であることを意味します。

これが、一般に、計算の複雑さには、最良、平均、および最悪のシナリオの3つの指標がある理由です。ハッシュテーブルは、O(1)最良のシナリオと平均的なシナリオでは複雑ですO(n)が、最悪のシナリオでは分類されます。

覚えておいてください:優れたハッシュ関数は効率的なハッシュテーブルの鍵です—それ以上でもそれ以下でもありません。

衝突の詳細…

DumbMap衝突の場合に修正するために使用した手法は、個別チェーンと呼ばれます。衝突を生成するすべてのキーペアをリストに格納し、それらをループします。

もう1つの一般的な手法は、オープンアドレス法です。

  • リストの各インデックスに、1つだけのキーと値のペアを格納します
  • ペアをインデックスに格納しようとするときにx、キーと値のペアがすでに存在する場合は、新しいペアをに格納してみてください。x + 1
  • x + 1取られたら、試してみてくださいx + 2
  • 要素を取得するときは、キーをハッシュして、その位置(x)の要素がキーと一致するかどうかを確認します
  • そうでない場合は、位置にある要素にアクセスしてみてください x + 1
  • リストの最後に到達するまで、または空のインデックスが見つかるまで、すすぎ、繰り返します。つまり、要素がハッシュテーブルにないことを意味します。

スマート、シンプル、エレガント、そして通常は非常に効率的です!

FAQ(またはTL; DR)

ハッシュテーブルは、保存している値をハッシュしますか?

いいえ、キーは整数に変換できるようにハッシュされ、iキーと値の両方がiリスト内の位置に格納されます。

ハッシュテーブルで使用されるハッシュ関数は衝突を生成しますか?

絶対に—ハッシュテーブルは、厄介なバグを回避するための防御戦略とともに実装されます。

ハッシュテーブルは内部でリストまたはリンクリストを使用しますか?

状況によって異なりますが、どちらも機能します。この例では、[]動的にサイズ変更できるJavaScript配列()を使用します。

> a = []
> a[3] = 1
> a[ , 1 ]

なぜ例としてJavaScriptを選んだのですか?JS配列はハッシュテーブルです!

例えば:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

私は知っている、JavaScriptを酷評します。

JavaScriptは「ユニバーサル」であり、サンプルコードを見るとおそらく最も理解しやすい言語です。JSは最良の言語ではないかもしれませんが、これらの例が十分に明確であることを願っています。

あなたの例はハッシュテーブルの本当に良い実装ですか?本当にそんなに簡単ですか?

いいえ、まったくありません。

Matt Zeunertによる「JavaScriptでのハッシュテーブルの実装」をご覧ください。これにより、もう少しコンテキストがわかります。学ぶべきことはまだたくさんあるので、ぜひチェックしてみることをお勧めします。

  • ハッシュテーブルに関するPaulKubeのコース
  • Javaで個別のチェーンを使用して独自のハッシュテーブルを実装する
  • アルゴリズム、第4版—ハッシュテーブル
  • 高速ハッシュテーブルの設計

最終的には…

ハッシュテーブルは、Pythonで辞書を作成するか、PHPで連想配列を作成するか、JavaScriptでマップを作成するかに関係なく、私たちが定期的に使用する非常に賢いアイデアです。それらはすべて同じ概念を共有し、(おそらく)一定のコストで、識別子によって要素を格納および取得できるように美しく機能します。

この記事を楽しんでいただければ幸いです。フィードバックをお寄せください。

この記事をレビューしてくれたJoeに特に感謝します。

アディオス!