7

Hashtable クラスの Java API ドキュメントを読んでいて、いくつかの質問に出くわしました。ドキュメントでは、「ハッシュテーブルが開いていることに注意してください。「ハッシュ衝突」の場合、単一のバケットに複数のエントリが保存され、順番に検索する必要があります。」私は自分で次のコードを試しました

Hashtable<String, Integer> me = new Hashtable<String, Integer>();
me.put("one", new Integer(1));
me.put("two", new Integer(2));
me.put("two", new Integer(3));
System.out.println(me.get("one"));  
System.out.println(me.get("two"));

アウトプットは

1
3
  1. これが「開く」ということですか？
  2. 整数 2 はどうなりましたか? ゴミとして回収？
  3. 「閉じた」例はありますか？
4

6 に答える 6

12

いいえ、これは「開く」という意味ではありません。

キーの衝突とハッシュの衝突の違いに注意してください。

ハッシュテーブルは、同じキーを持つ複数のエントリを許可しません(例のように、キー「2」を持つ 2 つのエントリを配置し、2 番目のエントリ (3) が最初のエントリ (2) を置き換え、残りはハッシュテーブルの 2 番目のもの)。

ハッシュ衝突は、2 つの異なるキーが同じハッシュコード (hashCode() メソッドによって返される) を持つ場合に発生します。さまざまなハッシュ テーブルの実装では、これをさまざまな方法で処理できますが、主に低レベルの実装に関してです。「オープン」であるため、Hashtable は、キーが同じ値にハッシュされるエントリのリンク リストを格納します。これにより、最悪の場合、単純な操作で O(N) のパフォーマンスが発生する可能性があります。これは通常、ハッシュがほとんど異なる値であるハッシュ マップでは O(1) です。

于 2009-08-17T15:49:45.910 に答える
3

これは、ハッシュコードが同じでキーが異なる 2 つのアイテムが同じバケットに入ることを意味します。

あなたの場合、キー「two」は同じであるため、2番目の put は最初のものを上書きします。

ただし、独自のクラスがあると仮定すると

class Thingy {
    private final String name;

    public Thingy(String name) {
         this.name = name;
    }

    public boolean equals(Object o) {
        ...

    }

    public int hashcode() {
       //not the worlds best idea
       return 1;
    }

}

そしてそれの複数のインスタンスを作成しました。すなわち

Thingy a = new Thingy("a"); 
Thingy b = new Thingy("b"); 
Thingy c = new Thingy("c");

そして、それらをマップに挿入しました。次に、1 つのバケット、つまりハッシュコード 1 の要素を含むバケットには、3 つのアイテムのリスト (チェーン) が含まれます。

Map<Thingy, Thingy> map = new HashMap<Thingy, Thingy>();
map.put(a, a);
map.put(b, b);
map.put(c, c);

そのため、Thingy キーでアイテムを取得すると、ハッシュコード O(1) のルックアップに続いて、ハッシュコード 1 のバケット内のアイテムのリストで線形検索 O(n) が行われます。

また、hashcode と equals を実装するときは、正しい関係に従うように注意してください。つまり、2 つのオブジェクトが等しい場合、それらは同じハッシュコードを持っている必要がありますが、複数のキーが同じハッシュコードを取得する可能性があるため、必ずしもそうであるとは限りません。

ああ、オープンハッシュとクローズドハッシュテーブルの完全な定義については、http://www.c2.com/cgi/wiki? HashTable を参照してください。

于 2009-08-17T15:54:57.273 に答える
2

これは、Hashtable がオープン ハッシュ(別のチェーンとも呼ばれる) を使用してハッシュの衝突を処理することを意味します。2 つの別々のキーが同じハッシュコードを持つ場合、それらは両方とも同じバケット (リスト内) に格納されます。

于 2009-08-17T15:53:21.253 に答える
2

オープンとは、2 つのキーが等しくなくてもハッシュ値が同じである場合、それらが同じ「バケット」に格納されることを意味します。この場合、各バケットはリンクされたリストと考えることができるため、同じバケットに多くのものが格納されていると、検索のパフォーマンスが低下します。

バケット 0: なし
バケット 1: アイテム 1
バケット 2: アイテム 2 -> アイテム 3
バケット 3: なし
バケット 4: アイテム 4

この場合、バケット 2 にハッシュされるキーを検索する場合は、リストに対して O(n) 検索を実行して、検索対象と等しいキーを見つける必要があります。キーがバケット 0、1、3、または 4 にハッシュされる場合、O(1) 検索パフォーマンスが得られます。

于 2009-08-17T15:54:16.633 に答える
1

警告:一般的な使用法では、「オープン ハッシュ」の矛盾する定義があります。

別の回答で引用されているhttp://www.c2.com/cgi/wiki?HashTableからの引用:

注意: 「オープン ハッシュ」という用語を、私がここで「クローズド ハッシュ」と呼んでいるものを意味するために使用する人もいます。ここでの使用法は、TheArtOfComputerProgramming と IntroductionToAlgorithms の使用法に準拠しています。どちらも、ハッシュ テーブルについて詳しく知りたい場合に参照することをお勧めします。

たとえば、上記のページでは「オープン ハッシュ」を次のように定義しています。

主な戦略は 2 つあります。オープン アドレッシングとも呼ばれるオープン ハッシングは、次のように 述べています。クローズドハッシュとは、テーブル内の各エントリは、実際のデータを含む二次データ構造 (通常はリンクされたリストですが、他の可能性もあります) であり、このデータ構造は無制限に拡張できます。

対照的に、ウィキペディアが提供する定義は次のとおりです。

個別チェーン、直接チェーン、または単にチェーンとして知られる戦略では、バケット配列の各スロットは、同じ場所にハッシュされたキーと値のペアを含むリンク リストへのポインターです。ルックアップでは、指定されたキーを持つエントリのリストをスキャンする必要があります。挿入には、ハッシュされたスロットのリストのいずれかの末尾に新しいエントリ レコードを追加する必要があります。削除するには、リストを検索して要素を削除する必要があります。(この手法はオープン ハッシングまたはクローズド アドレッシングとも呼ばれますが、「オープン アドレッシング」または「クローズド ハッシング」と混同しないでください。 )

いわゆる「専門家」が「オープンハッシュ」という用語の意味に同意できない場合は、使用を避けるのが最善です。

于 2009-08-17T23:06:23.890 に答える
1

ハッシュは、1 つのオブジェクト (サンプルでは「1」または「2」) を (この場合) 整数にマップする計算関数です。これは、同じ整数にマップされる複数の値が存在する可能性があることを意味します (整数には有限数の許容値がありますが、無限数の入力が存在する可能性があります)。この場合、「等しい」はこれら 2 つを区別できる必要があります。したがって、コード例は正しいですが、同じハッシュコードを持つ他のキーが存在する可能性があります (「2」と同じバケットに入れられます)。

于 2009-08-17T15:49:00.637 に答える