ハッシュテーブルとハッシュマップとそれらの典型的なユースケースとは何ですか？

Question

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

Answer 1

まあ、このように考えてください。

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

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

一方、ハッシュテーブルには、エントリを取得し、それをハッシュキーという数字に変換する関連関数があります。この番号は、配列のインデックスとして使用され、エントリを保存する場所です。

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

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

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

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

理論では、キーをハッシュキーに変換する関数、その数は、線形検索よりも計算上はるかに安価であるということです。

一般的なハッシュテーブルには、保存に使用できる要素の数に制限はありません。そのため、通常、配列のサイズに収まるインデックスまでその数をさらに減らします。これを行う1つの方法は、配列のサイズと比較してインデックスのモジュラスを取得することです。サイズが10の配列の場合、インデックス0〜9はインデックスに直接マッピングされ、インデックス10〜19は再び0〜9にマッピングされます。

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

衝突解決には多くの実装があり、最も簡単な方法は、配列内の次の空の要素に移動することです。ただし、この単純なソリューションには他の問題もあるため、正しい解決アルゴリズムを見つけることは、ハッシュテーブルにとっても優れた練習です。

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

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

このテーマに関する優れたウィキペディアの記事もあります。こちら。

>

Answer 2

lassevkの答えは非常に優れていますが、詳細が少し多すぎるかもしれません。以下がエグゼクティブサマリーです。私は、特定の関連情報を意図的に省略しています。これは、99％の時間を無視しても安全です。

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

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

真剣に。 3つのことを保証する以外のすべての魔法のデータ構造。 （例外があります。それらをいつか学ぶことはあなたにとって役に立つかもしれませんが、ほとんど無視できます。）

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

2）ハッシュテーブルの単一のキーで何かをしている場合、非常に高速です。これは、 put（key、value）、 get（key）、 contains（key）、および remove（key）はすべて非常に高速です。

3）汎用ハッシュテーブル＃2にリストされていないものを実行することに失敗する！ （「失敗」とは、非常に遅いことを意味します。）

いつハッシュテーブルを使用しますか

ハッシュテーブルを使用しますそれらの魔法が問題に適合する場合。

たとえば、キャッシュではハッシュテーブルが頻繁に使用されます。たとえば、大学に45,000人の学生がいて、すべてのレコードを保持する必要があるプロセスがあるとします。 ID番号で生徒を定期的に参照する場合、 ID =＆gt;スチューデントキャッシュは非常に理にかなっています。このキャッシュに対して最適化する操作は、高速ルックアップです。

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

また、次のいずれかを実行する必要がある場合を除き、データ構造に対してかなり良い最初の選択を行います。

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

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

並べ替え。反復できない場合、並べ替えも非常に面倒です。

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

Answer 3

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

ただし、Javaについて言及する場合の重要な違いは、ハッシュテーブルは本質的に同期されているため、ハッシュマップはスレッドセーフなコレクションではないが、スレッドセーフであることです。

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

ハッシュの仕組みを確認する必要がある場合は、データ構造とハッシュ手法について少しグーグルすることをお勧めします。

Answer 4

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