0

ハッシュテーブルで衝突が発生すると、リンクリストに格納されている複数の値を持つ1つのキーが発生し、どのキーが必要な値にマップされているかを確認するために等しい呼び出しを行うことを何度も読みましたが、ハッシュテーブルのコードにはリンクリストコードがありませんputメソッドまたはgetメソッド。Entry []配列を使用しており、これがリンクリストとしてどのように使用されるかわかりません。

for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
        }
    }

親切に私の疑問を導き、クリアしてください。

4

1 に答える 1

2

実装はJVM間で異なる可能性があると思いますが、私の理解では、リンクリストが使用されています（ただし、java.util.LinkedListは必須ではありません）。これは、私が使用するJVMのHashTableに「put」を実装する方法です。

public Object put(Object key, Object value) {
    // Make sure the value is not null
    if (value == null) throw new NullPointerException();

    // Makes sure the key is not already in the hashtable.
    HashtableEntry e;
    HashtableEntry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;

    for (e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        Object old = e.value;
        e.value = value;
        return old;
        }
    }

このバージョンとあなたが投稿したバージョンにはいくつかの違いがありますが、その背後にあるロジックは同じだと思います。HashtableEntryは次のようになります。

class HashtableEntry {
    int hash;
    Object key;
    Object value;
    HashtableEntry next;
(...)

「HashtableEntrynext」参照は、HashtableEntryをリンクリストにします（リンクリストは、リストの最後の要素でない限り、各要素が同じタイプの別の要素への参照を持つ構造です）。あなたが探していたのはjava.util.LinkedListだったと思いますが、HastTableは独自の方法でリンクリスト構造を実装しています。

于 2012-12-08T16:43:07.557 に答える