55

ハッシュ テーブルの基本的な概念について、私はかなり混乱しています。ハッシュをコーディングするとしたら、どうやって始めますか? ハッシュテーブルと通常の配列の違いは何ですか?

基本的に、誰かがこの質問に答えた場合、私のすべての質問に答えられると思います: 100 個のランダムに生成された数字 (キーとして) がある場合、ハッシュ テーブルをどのように実装し、配列よりも有利なのですか?

擬似コードまたは Java は、学習ツールとして高く評価されます...

4

11 に答える 11

70

これまでの回答は、ハッシュ テーブルを定義し、いくつかの理論を説明するのに役立ちましたが、例を使用すると、それらをよりよく理解するのに役立つと思います。

ハッシュテーブルと通常の配列の違いは何ですか?

ハッシュ テーブルと配列はどちらも、データの格納と取得を可能にする構造です。どちらもインデックスを指定し、それに関連付けられた値を取得できます。Daniel Spiewak が指摘したように、違いは、配列のインデックスはシーケンシャルであるのに対し、ハッシュ テーブルのインデックスはそれらに関連付けられたデータの値に基づいていることです。

ハッシュ テーブルを使用する理由

ハッシュ テーブルを使用すると、大量のデータ (特に他の方法では簡単に検索できないデータ) 内の項目を効率的に検索できます。(ここでの「大規模」は、シーケンシャル検索を実行するのに長い時間がかかるという意味で、途方もないことを意味します)。

ハッシュをコーディングするとしたら、どうやって始めますか?

問題ない。N最も簡単な方法は、数値(通常は整数)を返す、データに対して実行できる任意の数学演算を発明することです。次に、その番号を「バケット」の配列へのインデックスとして使用し、データをバケット # に保存しますN。トリックは、後で簡単に見つけることができるように、さまざまなバケットに値を配置する傾向がある操作を選択することです。

例: 大きなショッピング モールでは、買い物客が駐車した場所を思い出せるように、常連客の車と駐車場所のデータベースを保持しています。データベースには、、、、およびが格納さmakeれます。店を出るとき、買い物客は車のメーカーと色を入力して自分の車を見つけます。データベースは、ナンバー プレートと駐車スペースの (比較的短い) リストを返します。クイックスキャンで買い物客の車を見つけます。colorlicense plateparking location

これを SQL クエリで実装できます。

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

データが配列 (基本的には単なるリスト) に格納されている場合、一致するすべてのエントリに対して配列をスキャンすることでクエリを実装することを想像できます。

一方、ハッシュ ルールを想像してみてください。

make と color のすべての文字の ASCII 文字コードを加算し、100 で割り、余りをハッシュ値として使用します。

このルールは、各項目を 0 ～ 99 の数値に変換し、基本的にデータを 100 個のバケットに並べ替えます。顧客が車の場所を特定する必要があるたびに、メーカーと色をハッシュして、情報を含む 100 個のバケットから1 個を見つけることができます。すぐに検索を 100 分の 1 に減らしました。

ここで、数十の基準に基づいて検索される数百万のエントリを持つデータベースなど、膨大な量のデータに例をスケーリングします。「優れた」ハッシュ関数は、追加の検索を最小限に抑え、時間を大幅に節約する方法でデータをバケットに分散します。

于 2008-11-12T02:57:43.403 に答える
46

まず、ハッシュ関数とは何かを理解する必要があります。ハッシュ関数は、キー (任意の長さの文字列など) を受け取り、可能な限り一意の数値を返す関数です。同じキーは常に同じハッシュを返す必要があります。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;
}
于 2008-11-12T02:36:23.243 に答える
17

ハッシュテーブルは連想的です。これは、単なる線形データ構造である配列との大きな違いです。配列を使用すると、次のようなことができます。

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ください。

おそらくこれでほとんどの質問に答えられると思います。ハッシュテーブルの実装はかなり興味深いトピックであり、ウィキペディアはまずまずうまく扱っています。

于 2008-11-12T01:30:02.270 に答える
8

「ハッシュ テーブルがキーを検索する方法と、キーが生成される方法に興味があります。」

  1. ハッシュは、キー オブジェクトを数値に変換します。これは「ハッシュ」と呼ばれ、オブジェクトからハッシュを作成します。ハッシュ関数を参照してください。たとえば、文字列のバイトを合計することは、標準的なハッシュ手法です。ハッシュを扱いやすいサイズに保つために、 2 32を法とする合計を計算します。ハッシュは常に同じ答えを返します。O (1)です。

  2. 数値は、HashTable の「スロット」を提供します。任意のキー オブジェクトを指定すると、ハッシュ値によってハッシュ値が計算されます。ハッシュ値は、テーブル内のスロットを提供します。通常mod( hash, table size )。こちらもO (1)です。

それが一般的な解決策です。2 つの数値計算により、キーとしての任意のオブジェクトから値としての任意のオブジェクトに移動しました。これほど高速なものはほとんどありません。

オブジェクトからハッシュ値への変換は、これらの一般的な方法のいずれかで行われます。

  1. 4 バイトの「プリミティブ」オブジェクトの場合、オブジェクトのネイティブ値は数値です。

  2. オブジェクトのアドレスは 4 バイトで、オブジェクトのアドレスをハッシュ値として使用できます。

  3. 単純なハッシュ関数(MD5、SHA1 など) は、オブジェクトのバイトを累積して 4 バイトの数値を作成します。高度なハッシュはバイトの単純な合計ではありません。単純な合計は元の入力ビットすべてを十分に反映していません。

ハッシュ テーブルのスロットは mod( number, size of table ) です。

そのスロットに目的の値があれば、完了です。それが望ましい値でない場合は、別の場所を探す必要があります。テーブル内の空きスポットを探すための一般的な調査アルゴリズムがいくつかあります。Linear は、次のフリー スポットの単純な検索です。Quadratic は、空いているスロットを探す非線形ホッピングです。乱数ジェネレーター (固定シードを使用) を使用して、データを均等に任意に拡散する一連のプローブを生成できます。

プロービング アルゴリズムはO (1) ではありません。テーブルが十分に大きい場合、衝突の可能性は低く、プローブは問題になりません。テーブルが小さすぎると、衝突が発生し、プローブが発生します。その時点で、プローブとテーブル サイズのバランスを取り、パフォーマンスを最適化するための「調整と微調整」の問題になります。通常、テーブルを大きくするだけです。

ハッシュ テーブルを参照してください。

于 2008-11-12T02:35:43.603 に答える
6

まだ特に注目されていないもの：

配列に対してハッシュ テーブルを使用するポイントはパフォーマンスです。

配列を反復処理すると、通常、O(1) から O(x) までの範囲で処理されます。ここで、x は配列内の項目の数です。ただし、特に配列内の数十万のアイテムについて話している場合、アイテムを見つけるまでの時間は非常に変動します。

適切に重み付けされたハッシュ テーブルでは、通常、ハッシュ テーブル内の項目数に関係なく、O(1) をわずかに上回るほぼ一定のアクセス時間になります。

于 2008-11-12T02:47:03.707 に答える
4

ランダムに生成された 100 個の数値に対してハッシュ テーブルを使用することは望ましくありません。

ハッシュ テーブルについて考える良い方法は、値のペアについて考えることです。学生を使用してみましょう。誰もが学籍番号を持っているとします。プログラムでは、学生に関する情報 (名前、電話番号、請求書など) を保存します。基本的な情報 (名前や学生 ID など) のみを使用して、学生に関するすべての情報を検索する必要があります。

10,000 人の学生がいるとします。それらをすべて配列に格納する場合は、各エントリの学生 ID を探しているものと比較して、配列全体をループする必要があります。

代わりに、学生 ID 番号を配列内の位置に「ハッシュ」(以下を参照) すると、同じハッシュを持つ学生の番号を検索するだけで済みます。欲しいものを見つけるための作業がはるかに少なくなります。

この例では、学生 ID が 6 桁の数字だとします。このハッシュ関数は、数字の下 3 桁のみを「ハッシュ キー」として使用できます。したがって、232145 は配列位置 145 にハッシュされます。したがって、999 要素の配列のみが必要です (各要素は学生のリストです)。

それはあなたにとって良いスタートになるはずです。もちろん、この種の情報については、教科書やウィキペディアを読む必要があります。しかし、あなたはすでにそれを行っており、読むのにうんざりしていると思います.

于 2008-11-12T01:30:23.690 に答える
3

要するに、ハッシュテーブルがどのように機能するかを次に示します。

本でいっぱいの図書館があると想像してください。本を並べて保管する場合、それぞれの本を棚の特定の場所に置き、誰かが本を探すように頼んだら、すべての棚を調べます。かなりゆっくりです。誰かが「book #12345」と言えば、簡単に見つけることができます。

代わりに、本のタイトルが「A」で始まる場合、それは行 1 に配置されます。2 番目の文字が「B」の場合、行 1 のラック 2 に配置されます。3 番目の文字が「C」の場合、それは行 1 に配置されます。本の位置を特定するまで、行 1、ラック 2、棚 3... と続きます。次に、本のタイトルに基づいて、それがどこにあるべきかを正確に知ることができます.

ここで、私が説明した単純な「ハッシュ」アルゴリズムにはいくつかの問題があります。ある棚は過負荷になり、他の棚は空のままになり、一部の本は同じスロットに割り当てられます..そのため、実際のハッシュ関数は慎重に構築されていますそのような問題を回避しようとします。

しかし、これが基本的な考え方です。

于 2008-11-12T02:38:27.297 に答える
0

[上記 me.yahoo.com/a のコメントへの返信です]

それはあなたのハッシュ関数に依存します。ハッシュ関数が単語の長さに従って単語をハッシュすると仮定すると、chris のキーは 5 になります。同様に、yahoo のキーも 5 になります。これで、両方の値 (chris と yahoo) が 5 未満になります (つまり、 5 をキーとする「バケット」内)。この方法では、データのサイズに等しい配列を作成する必要はありません。

于 2008-11-12T01:47:24.933 に答える
0

この質問は、今では非常に明確に、そしてさまざまな方法で答えられていると思います。

別の視点を追加したいだけです（新しい読者も混乱する可能性があります）

最小の抽象化レベルでは、配列はメモリの連続したブロックにすぎません。単一要素の開始アドレス ( startAddress)、サイズ ( sizeOfElement)、および を指定すると、要素のアドレスは次のように計算されます。index

elementAddress = startAddress + sizeOfElement * index

ここで注目すべき興味深い点は、キーとして配列をハッシュ テーブルとして抽象化/表示し、上記の関数をO(1)indexの値の位置を計算するハッシュ関数として表示できることです。

于 2010-05-24T12:46:24.603 に答える
0

ハッシュテーブルと配列の違いについてその部分に答えます...しかし、以前にインポートのハッシュアルゴリズムを実装したことがないので、それはもっと知識のある人に任せます:)

配列は、オブジェクトの順序付きリストです。オブジェクト自体はそれほど重要ではありません... 重要なのは、挿入順にオブジェクトをリストしたい場合、常に同じであるということです (つまり、最初の要素のインデックスは常に0 です)。

ハッシュテーブルに関しては、それは順序ではなくキーによって索引付けされています...ハッシュアルゴリズムの基本的な検索は、私ができるよりもはるかに多くの洞察を与えると思います...ウィキペディアには非常にまともなものがあります...それは「バケットを決定します"キーとして使用される任意のオブジェクトをすばやく取得するためにキーが入ります。

利点について: 挿入の順序が重要な場合は、配列または何らかの順序付きリストが必要です。任意のキー (さまざまなハッシュ関数をキーとする) による高速検索が重要な場合は、ハッシュ テーブルが適しています。

于 2008-11-12T01:31:53.920 に答える