私のような単純な人間にもわかるように、ハッシュ テーブルがどのように動作するのかをわかりやすい英語で説明していただけると嬉しいです。
たとえば、キーを取得してハッシュを計算し（その方法の説明を探しています）、何らかのモジュロを実行して、値が格納されている配列のどこにあるかを判断することはわかっていますが、私の知識はそこまでです。
誰かそのプロセスを明確に説明してもらえますか?
編集:ハッシュ コードの計算方法について具体的に質問しているのではなく、ハッシュ テーブルがどのように機能するかについての一般的な概要を質問しています。
ベストアンサー1
素人にもわかるように説明しましょう。
図書館に本を詰め込みたいが、ただ本を詰め込むのではなく、必要なときに簡単に見つけられるようにしたいとします。
そこで、本を読みたい人が本のタイトルと正確なタイトルを知っていれば、それで十分だと判断します。タイトルがあれば、その人は司書の助けを借りて、簡単に素早く本を見つけることができるはずです。
では、どうすればそれができるのでしょうか。各本をどこに置いたかを示すリストのようなものを保管することはできますが、そうすると図書館を検索するのと同じ問題が発生します。リストを検索する必要があります。確かに、リストは小さくなり、検索しやすくなりますが、それでも図書館 (またはリスト) の端から端まで順番に検索することは望ましくありません。
本のタイトルですぐに適切な場所がわかるようなものが欲しいですよね。そうすれば、適切な棚まで歩いて行って、本を手に取るだけで済みます。
しかし、それはどのようにできるのでしょうか? ライブラリを埋めるときに少し事前に考え、ライブラリを埋めるときに多くの作業を行う必要があります。
図書館の端から端までただ本を埋めていくのではなく、ちょっとした巧妙な方法を考案します。本のタイトルを取り、それを小さなコンピュータ プログラムに通すと、棚番号とその棚のスロット番号が出力されます。これが本を置く場所です。
このプログラムの優れた点は、後になって、人が本を読みに戻ってきたときに、もう一度プログラムにタイトルを入力すると、最初に与えられたのと同じ棚番号とスロット番号が返され、そこに本が置かれている場所がわかることです。
他の人がすでに述べたように、このプログラムはハッシュ アルゴリズムまたはハッシュ計算と呼ばれ、通常は入力されたデータ (この場合は本のタイトル) を取得して、そこから数値を計算します。
簡単に言うと、各文字と記号を数字に変換して、それをすべて合計するだけだとしましょう。実際には、それよりもずっと複雑ですが、今はこのままにしておきましょう。
このようなアルゴリズムの優れた点は、同じ入力を何度も入力すると、毎回同じ数値が出力され続けることです。
はい、これがハッシュテーブルの基本的な仕組みです。
技術的な内容は後ほど説明します。
まず、数字の大きさがあります。通常、このようなハッシュ アルゴリズムの出力は、ある大きな数字の範囲内にあり、通常はテーブル内のスペースよりもはるかに大きくなります。たとえば、図書館にちょうど 100 万冊の本を収容できるスペースがあるとします。ハッシュ計算の出力は、0 から 10 億の範囲になる可能性があり、これははるかに大きくなります。
では、どうすればいいのでしょうか? モジュラス計算と呼ばれるものを使います。これは基本的に、必要な数 (つまり 10 億の数) まで数えたが、それよりずっと狭い範囲内にとどめておきたい場合、その狭い範囲の限界に達するたびに 0 から開始しますが、大きな数列の中でどこまで進んだかを記録しておく必要があるというものです。
ハッシュ アルゴリズムの出力が 0 から 20 の範囲にあり、特定のタイトルから値 17 を取得するとします。ライブラリのサイズが 7 冊だけの場合、1、2、3、4、5、6 と数え、7 に達したら 0 に戻ります。17 回数える必要があるため、1、2、3、4、5、6、0、1、2、3、4、5、6、0、1、2、3、4、5、6、0、1、2、3 となり、最終的な数字は 3 になります。
もちろん、剰余の計算はこのようには行われず、割り算と余りで行われます。17 を 7 で割った余りは 3 です (7 は 17 の 2 倍で 14 になり、17 と 14 の差は 3 です)。
したがって、本をスロット番号 3 に置きます。
これは次の問題、衝突につながります。アルゴリズムには、ライブラリ (またはハッシュ テーブル) にぴったり収まるように本を配置する方法がないため、必ず、以前に使用された番号を計算することになります。ライブラリの感覚で言えば、本を入れたい棚とスロット番号に到達すると、そこにはすでに本があります。
衝突処理の方法は様々あり、その中には、データをさらに別の計算にかけ、テーブル内の別の場所を取得する方法（ダブルハッシュ）、または単に与えられたスペースに近いスペース（つまり、スロットが空いていたと仮定して、前の本のすぐ隣）を見つけることもできます。リニアプローブ）。これは、後で本を探すときに少し探す必要があることを意味しますが、それでも単に図書館の端から始めるよりはましです。
最後に、ある時点で、図書館に収まる本の数よりも多くの本を図書館に置きたくなるかもしれません。言い換えれば、より大きな図書館を構築する必要があります。図書館の正確な場所は、図書館の正確な現在のサイズを使用して計算されたため、図書館のサイズを変更すると、場所を見つけるための計算が変更され、すべての本に新しい場所を見つける必要がある可能性があります。
この説明がバケットや関数よりも少し現実的であったことを願っています :)