41

私は最近、これらの用語に何度か出くわしましたが、それらがどのように機能し、いつ実装されるのかについてかなり混乱していますか?

4

4 に答える 4

74

さて、こう考えてみてください。

単純なインデックスベースのデータ構造である配列を使用し、ランダムなもので埋める場合、特定のエントリを見つけることは、基本的に次から検索を開始する必要があるため、データで埋めるにつれてますます高価な操作になります。必要なものが見つかるまで、一方の端をもう一方の端に向けます。

データへのアクセスを高速化する場合は、通常、配列を並べ替えてバイナリ検索を使用します。ただし、これにより、既存の値を検索する速度が向上しますが、要素を途中で挿入する必要があるときに既存の要素を移動する必要があるため、新しい値の挿入が遅くなります。

一方、ハッシュテーブルには、エントリを取得し、それを数値であるハッシュキーに還元する関連関数があります。この番号は、配列へのインデックスとして使用され、ここにエントリを格納します。

ハッシュテーブルは、最初は空から始まる配列を中心に展開します。空は長さがゼロという意味ではありません。配列はサイズで始まりますが、配列内のすべての要素には何も含まれていません。

各要素には、データと、データを識別するキーの 2 つのプロパティがあります。たとえば、米国の郵便番号のリストは、郵便番号 -> 名前タイプの関連付けになります。この関数はキーを減らしますが、データは考慮しません。

したがって、ハッシュテーブルに何かを挿入すると、関数はキーを数値に減らします。これは、この (空の) 配列へのインデックスとして使用されます。これは、データ (キーと関連データの両方) を格納する場所です。

その後、キーがわかっている特定のエントリを見つけたいので、同じ関数を使用してキーを実行し、そのハッシュ キーを取得して、ハッシュ テーブルの特定の場所に移動し、そこにあるデータを取得します。

理論的には、キーをハッシュキー (その数値) に減らす関数は、線形検索よりも計算コストがはるかに低いということになります。

典型的なハッシュテーブルには、ストレージに使用できる要素の数が無限にあるわけではないため、通常、数は配列のサイズに収まるインデックスまでさらに削減されます。これを行う 1 つの方法は、配列のサイズと比較して単純にインデックスのモジュラスを取得することです。サイズが 10 の配列の場合、インデックス 0 ～ 9 はインデックスに直接マップされ、インデックス 10 ～ 19 は再び 0 ～ 9 にマップされます。

一部のキーは、ハッシュテーブル内の既存のエントリと同じインデックスに縮小されます。この時点で、キーのデータ型の比較に関連するすべてのルールを使用して、実際のキーが直接比較されます (つまり、通常の文字列比較など)。完全に一致する場合は、新しいデータを無視する (既に存在する) か、上書きする (そのキーの古いデータを置き換える) か、追加します (多値ハッシュテーブル)。一致しない場合、つまり、ハッシュ キーは同一であるにもかかわらず、実際のキーは同一ではなかったことを意味します。通常、そのキーとデータを格納する新しい場所を見つけます。

衝突解決には多くの実装があり、最も単純なものは、配列内の次の空の要素に移動することです。ただし、この単純な解決策には別の問題があるため、適切な解決アルゴリズムを見つけることは、ハッシュテーブルの練習にもなります。

ハッシュテーブルが完全に (またはほぼ) いっぱいになると、ハッシュテーブルも大きくなる可能性があります。これは通常、新しいサイズの新しい配列を作成し、すべてのインデックスをもう一度計算し、項目を新しい配列の新しい配列に配置することによって行われます。場所。

キーを数値に減らす関数は、線形値を生成しません。「AAA」が 1 になり、「AAB」が 2 になるため、ハッシュテーブルは一般的な値でソートされません。

この件に関しては、ウィキペディアにも優れた記事があります。

于 2008-09-26T08:25:12.100 に答える
63

lassevk の回答は非常に優れていますが、詳細が少し多すぎる可能性があります。エグゼクティブサマリーはこちら。99% の確率で安全に無視できる特定の関連情報を意図的に省略しています。

99% の確率で、ハッシュ テーブルとハッシュ マップの間に重要な違いはありません。

ハッシュテーブルは魔法です

真剣に。3 つのことを保証する魔法のデータ構造です。(例外もあります。大部分は無視できますが、いつかそれらを学ぶことは役に立つかもしれません。)

1) ハッシュ テーブル内のすべてがペアの一部です。キーと値があります。操作対象のキーを指定して、データを出し入れします。

2) ハッシュ テーブルの 1 つのキーで何かを実行している場合、非常に高速です。これはput(key,value)、get(key)、 、contains(key)、およびremove(key)がすべて非常に高速であることを意味します。

3) 一般的なハッシュ テーブルは、#2 に記載されていないことを行うと失敗します。(「失敗」とは、非常に遅いことを意味します。)

ハッシュ テーブルはいつ使用するのですか?

ハッシュテーブルの魔法が私たちの問題に適合する場合、ハッシュテーブルを使用します。

たとえば、キャッシングは頻繁にハッシュ テーブルを使用して終了します。たとえば、大学に 45,000 人の学生がいて、何らかのプロセスで全員のレコードを保持する必要があるとします。定期的に学生を ID 番号で参照する場合、ID => studentキャッシュは非常に理にかなっています。このキャッシュ用に最適化している操作は高速ルックアップです。

ハッシュは、オブジェクト自体を完全に変更したくない場合に、データ間の関係を保存するのにも非常に役立ちます。たとえば、コースの登録時に、受講しているクラスに学生を関連付けることができるとよいでしょう。ただし、何らかの理由で Student オブジェクト自体にそのことを知らせたくない場合があります。ハッシュを使用し、studentToClassRegistration必要なことをしている間はそれを保持してください。

また、次のいずれかを行う必要がある場合を除いて、データ構造の最初の選択肢としてかなり適しています。

ハッシュ テーブルを使用しない場合

要素を反復処理します。ハッシュ テーブルは通常、反復処理をあまりうまく行いません。（つまり、一般的なものです。特定の実装には、リンクされたリストが含まれていることがあります。これは、それらの反復を少なくするために使用されます。たとえば、Javaでは、LinkedHashMapキーまたは値をすばやく反復できます。）

並べ替え。 反復できない場合、並べ替えも王様の苦痛です。

value から key へ。2 つのハッシュ テーブルを使用します。私を信じてください、私はあなたに多くの苦痛を救っただけです。

于 2008-09-26T09:33:09.287 に答える
4

Javaの観点から話している場合、どちらもオブジェクトの追加、削除、更新を許可し、Hasing アルゴリズムを内部で使用するコレクションです。

ただし、Java に関して言えば、大きな違いは、ハッシュ テーブルは本質的に同期されているためスレッド セーフであるのに対し、ハッシュ マップはスレッド セーフ コレクションではないということです。

同期とは別に、オブジェクトを保存および取得する内部メカニズムは、どちらの場合もハッシュです。

ハッシュがどのように機能するかを確認する必要がある場合は、データ構造体とハッシュ手法について少しグーグルで調べることをお勧めします。

于 2008-09-26T08:30:49.997 に答える
-2

ハッシュテーブル/ハッシュマップは、値 (あいまいさをなくすために「キー」と呼ばれる) を別の値に関連付けます。それらは一種の辞書 (単語: 定義) またはデータベース レコード (キー: データ) と考えることができます。

于 2008-09-26T08:26:37.230 に答える