ハッシュテーブルの基礎？
https://stackoverflow.com/questions/282712
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ハッシュテーブルの基本概念についてかなり混乱しています。ハッシュをコーディングする場合、どのように始めますか？ハッシュテーブルと通常の配列の違いは何ですか？
基本的に誰かがこの質問に答えた場合、私の質問はすべて答えられると思います。 （キーとして）ランダムに生成された100個の数値がある場合、ハッシュテーブルを実装する方法と、配列よりも有利なのはなぜですか？
擬似コードまたはJavaは学習ツールとして高く評価されます...
解決
これまでの回答は、ハッシュテーブルを定義し、いくつかの理論を説明するのに役立ちましたが、例を使用すると、より良い感覚を得ることができると思います。
ハッシュテーブルと通常の配列の違いは何ですか？
ハッシュテーブルと配列はどちらも、データを保存および取得できる構造です。どちらも、インデックスを指定し、それに関連付けられた値を取得できます。 Daniel Spiewakが指摘したように、配列のインデックスはシーケンシャルであるのに対して、ハッシュテーブルのインデックスはそれらに関連付けられたデータの値に基づいています。
ハッシュテーブルを使用する理由
ハッシュテーブルは、大量のデータ、特に他の方法では簡単に検索できないデータのアイテムを検索するための非常に効率的な方法を提供できます。 （ここで＆quot; Large＆quot;とは、 ginormous という意味です。順次検索を実行するには長い時間がかかります）。
ハッシュをコーディングする場合、どのように始めますか？
問題ありません。最も簡単な方法は、データに対して実行できる任意の数学演算を発明することです。これは、数値 N （通常は整数）を返します。次に、その番号を「バケット」の配列のインデックスとして使用します。バケット＃ N にデータを保存します。トリックは、後で簡単に見つけられるように、異なるバケットに値を配置する傾向がある操作を選択することです。
例：大規模なモールでは、買い物客が駐車した場所を覚えやすくするために、顧客の車と駐車場のデータベースを保持しています。データベースには、 make 、 color 、 license plate 、および parking location が保存されます。店を出ると、買い物客はメーカーと色を入力して自分の車を見つけます。データベースは、ナンバープレートと駐車スペースの（比較的短い）リストを返します。クイックスキャンで買い物客の車を見つけます。
SQLクエリでこれを実装できます：
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
データが本質的に単なるリストである配列に格納されていた場合、一致するすべてのエントリについて配列をスキャンすることでクエリを実装することを想像できます。
一方、ハッシュルールを想像してください：
メーカーと色のすべての文字のASCII文字コードを追加し、100で除算し、残りをハッシュ値として使用します。
このルールは、各アイテムを0〜99の数値に変換し、基本的にデータを100個のバケットにソートします。顧客が車を見つける必要があるたびに、メーカーと色をハッシュして、情報を含む100個のバケットから one バケットを見つけることができます。検索はすぐに100分の1に削減されました！
ここで、数十の基準に基づいて検索される数百万のエントリを持つデータベースなど、膨大な量のデータに例を拡張します。 「良い」ハッシュ関数は、追加の検索を最小限に抑える方法でデータをバケットに分散し、時間を大幅に節約します。
他のヒント
まず、ハッシュ関数とは何かを理解する必要があります。 ハッシュ関数とは、キー（たとえば、任意の長さの文字列）を受け取り、可能な限り一意の数値を返す関数です。同じキーは常に同じハッシュを返す必要があります。 Javaの本当に単純な文字列ハッシュ関数は次のようになります
public int stringHash(String s) {
int h = s.length();
for(char c : s.toCharArray()) {
h ^= c;
}
return h;
}
http://www.azillionmonkeys.com/qed/で適切なハッシュ関数を学習できます。 hash.html
現在、ハッシュマップはこのハッシュ値を使用して値を配列に配置します。単純なjavaメソッド：
public void put(String key, Object val) {
int hash = stringHash(s) % array.length;
if(array[hash] == null) {
array[hash] = new LinkedList<Entry<String, Object> >();
}
for(Entry e : array[hash]) {
if(e.key.equals(key)){
e.value = val;
return;
}
}
array[hash].add(new Entry<String, Object>(key, val));
}
（このマップは一意のキーを強制します。すべてのマップが強制するわけではありません。）
2つの異なるキーが同じ値にハッシュすること、または2つの異なるハッシュが同じ配列インデックスにマップすることが可能です。これに対処するための多くのテクニックがあります。最も簡単な方法は、各配列インデックスにリンクリスト（またはバイナリツリー）を使用することです。ハッシュ関数が十分であれば、線形検索は不要になります。
キーを検索するようになりました：
public Object get(String key) {
int hash = stringHash(key) % array.length;
if(array[hash] != null) {
for(Entry e : array[hash]) {
if(e.key.equals(key))
return e.value;
}
}
return null;
}
ハッシュテーブルは連想です。これは、単なる線形データ構造である配列とは大きな違いです。配列を使用すると、次のようなことができます。
int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
正確なメモリオフセット（ i ）を指定して、配列から要素を取得する方法に注意してください。これは、後でキーに基づいて値を取得するキー/値ペアを保存できるハッシュテーブルとは対照的です：
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
上記の表を使用して、次の呼び出しを行うことができます。
int n = table.get("Chris");
... n は 18 で評価されます。
これはおそらくあなたの質問のほとんどに答えると思います。ハッシュテーブルの実装はかなり興味深いトピックで、ウィキペディアがまずまずに対処しています。 >
＆quot;ハッシュテーブルがキーを検索する方法とキーの生成方法に興味があります。
-
ハッシュは、キーオブジェクトを数値に変換します。これは「ハッシュ」と呼ばれます。 -オブジェクトからハッシュを作成します。 ハッシュ関数をご覧ください。たとえば、文字列のバイトを合計することは、標準のハッシュ手法です。 2 32 を法とする合計を計算して、ハッシュを管理可能なサイズに保ちます。ハッシュは常に同じ答えを与えます。これは O （1）です。
-
数字は、「スロット」を示します。 HashTableで。任意のキーオブジェクトを指定すると、ハッシュ値はハッシュ値を計算します。ハッシュ値は、テーブル内のスロットを提供します。通常、
mod（hash、table size）。これも O （1）です。
これが一般的な解決策です。 2つの数値計算で、キーとしての任意のオブジェクトから値としての任意のオブジェクトに移動しました。速くなることはほとんどありません。
オブジェクトからハッシュ値への変換は、これらの一般的な方法のいずれかで行われます。
-
それが＆quot;プリミティブ＆quot;の場合4バイトのオブジェクトの場合、オブジェクトのネイティブ値は数値です。
-
オブジェクトのアドレスは4バイトです。オブジェクトのアドレスはハッシュ値として使用できます。
-
単純なハッシュ関数（MD5、SHA1、なんでも）は、 4バイトの数値を作成するオブジェクト。高度なハッシュは単純なバイトの合計ではなく、単純な合計では元の入力ビットのすべてが十分に反映されません。
ハッシュテーブルのスロットはmod（number、size of table）です。
そのスロットに目的の値があれば、完了です。それが望ましい値でない場合は、別の場所を調べる必要があります。テーブル内の空きスポットを探すための一般的なプローブアルゴリズムがいくつかあります。線形は、次の空きスポットの単純な検索です。 Quadraticは、空きスロットを探すための非線形ホッピングです。乱数ジェネレーター（固定シードを使用）を使用して、データを均等に任意に拡散する一連のプローブを生成できます。
プローブアルゴリズムは O （1）ではありません。テーブルが十分に大きければ、衝突の可能性は低く、プローブは重要ではありません。テーブルが小さすぎる場合、衝突が発生し、プローブが発生します。その時点で、「チューニングと微調整」の問題になります。プローブとテーブルサイズのバランスをとり、パフォーマンスを最適化します。通常、テーブルを大きくするだけです。
ハッシュテーブルを参照してください。
まだ具体的に指摘されていないもの：
配列でハッシュテーブルを使用するポイントはパフォーマンスです。
配列を反復処理するには、通常、O（1）からO（x）のいずれかを使用します。xは配列内のアイテムの数です。ただし、特に配列内の何十万ものアイテムについて話している場合は、アイテムを見つける時間は非常に可変になります。
適切に重み付けされたハッシュテーブルのアクセス時間は、通常、ハッシュテーブル内のアイテム数に関係なく、O（1）を超えるほぼ一定です。
ランダムに生成された100個の数値にハッシュテーブルを使用することは望ましくありません。
ハッシュテーブルについて考える良い方法は、値のペアについて考えることです。学生を使用して、全員に学生ID番号があるとしましょう。プログラムでは、学生に関する情報（名前、電話番号、請求書など）を保存します。基本情報（名前や学生IDなど）のみを使用して、学生に関するすべての情報を検索したい場合。
10,000人の学生がいるとします。それらをすべて配列に格納する場合、各エントリの学生IDと探しているものを比較して、配列全体をループする必要があります。
代わりに、「ハッシュ」 （以下を参照）学生ID番号を配列内の位置に配置すると、同じハッシュを持つ番号の学生のみを検索する必要があります。必要なものを見つけるための作業がはるかに少なくなります。
この例では、学生IDが6桁の数字であるとします。ハッシュ関数では、「ハッシュキー」として数字の下3桁のみを使用できます。したがって、232145は配列の位置145にハッシュされます。したがって、必要なのは999要素の配列のみです（各要素は学生のリストです）。
それはあなたにとって良いスタートになるはずです。もちろん、この種の情報については、教科書またはウィキペディアを読む必要があります。しかし、私はあなたがすでにそれをやったと読んで疲れていると思います。
簡単に言えば、ハッシュテーブルの仕組みです。
本でいっぱいの図書館があると想像してください。本をアレイに保管する場合、各本を棚のある場所に置き、誰かが本を見つけるように頼んだら、すべての棚に目を通します-かなり遅いです。誰かが「本＃12345」と言ったとしても、かなり簡単に見つけることができます。
代わりに、本のタイトルが「A」で始まる場合、行1に移動します。2番目の文字が「B」の場合、行1、ラック2に移動します。3番目の文字が「C '、1行目、ラック2、棚3 ...などに移動して、書籍の位置を特定します。そうすれば、本のタイトルに基づいて、どこにあるべきかを正確に知ることができます。
今、単純化した「ハッシュ」にはいくつかの問題があります。私が説明したアルゴリズム-一部の棚はかなり過負荷になり、他の棚は空になり、一部の本は同じスロットに割り当てられます。したがって、このような問題を回避するために実際のハッシュ関数は慎重に構築されます。
しかし、これは基本的な考え方です。
ハッシュテーブルと配列の違いについてその部分に答えます...しかし、インポートのハッシュアルゴリズムを実装したことがないので、それをもっと知識のある人に任せます：）
配列は、オブジェクトの順序付きリストです。オブジェクト自体は実際には重要ではありません...重要なのは、オブジェクトを挿入順にリストしたい場合、常に同じであるということです（つまり、最初の要素 always のインデックスは0）。
ハッシュテーブルについては、順序ではなくキーでインデックス付けされています...ハッシュアルゴリズムの基本的な検索は、私ができる以上の洞察を与えると思います...ウィキペディアには非常にまともなものがあります... 「バケット」を決定します。キーとして使用される任意のオブジェクトをすばやく取得するためにキーが挿入されること。
利点について：挿入の順序が重要な場合、配列またはある種の順序付きリストが必要です。任意のキー（さまざまなハッシュ関数でキー設定）による高速ルックアップが重要な場合、ハッシュテーブルが意味を持ちます。
[これは上記のme.yahoo.com/aによるコメントへの返信です]
それはハッシュ関数に依存します。ハッシュ関数が単語の長さごとに単語をハッシュすると、chrisのキーは5になります。同様に、yahooのキーも5になります。 5）によってキー設定された「バケット」内。この方法では、配列をデータのサイズと等しくする必要はありません。
この質問は、今では非常に明確に、さまざまな方法で回答されていると思います。
別のパースペクティブを追加したいだけです（新しい読者も混乱させる可能性があります）
最小限の抽象化レベルでは、配列は単なる連続したメモリブロックです。単一の要素の開始アドレス（ startAddress ）、サイズ（ sizeOfElement ）、および index を指定すると、要素のアドレスは次のように計算されます：
elementAddress = startAddress + sizeOfElement * index
ここで興味深いのは、 index をキーとして、上記の関数をの値の位置を計算するハッシュ関数として、配列をハッシュテーブルとして抽象化/表示できることです。 O（1）
ハッシュテーブルは、クイックルックアップ用に作成されるデータ構造です。
エントリの数が非常に少ない場合、ハッシュテーブルは効果的ではありません。
いくつかの例：
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class HashtableDemo {
public static void main(String args[]) {
// Creating Hashtable for example
Hashtable companies = new Hashtable();
// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map
companies.put("Google", "United States");
companies.put("Nokia", "Finland");
companies.put("Sony", "Japan");
// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable
companies.get("Google");
// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable
System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));
// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value
System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));
// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values
Enumeration enumeration = companies.elements();
while (enumeration.hasMoreElements()) {
System.out.println("hashtable values: "+enumeration.nextElement());
}
// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java
System.out.println("Is companies hashtable empty: "+companies.isEmpty());
// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java
System.out.println("Size of hashtable in Java: " + companies.size());
// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java
Set hashtableKeys = companies.keySet();
// you can also get enumeration of all keys by using method keys()
Enumeration hashtableKeysEnum = companies.keys();
// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection
Enumeration hashtableValuesEnum = companies.elements();
Collection hashtableValues = companies.values();
// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.
companies.clear();
}
}
出力：
Does hashtable contains Google as key: true
Does hashtable contains Japan as value: true
hashtable values: Finland
hashtable values: United States
hashtable values: Japan
Is companies hashtable empty: false
Size of hashtable in Java: 3
