-10

私は HashMap を調べていて、次の分析を読みました..

  1. HashMap のインスタンスには、そのパフォーマンスに影響を与える 2 つのパラメーターがあります。初期容量と負荷係数です。

  2. 容量はハッシュ テーブル内のバケットの数であり、初期容量は単にハッシュ テーブルが作成された時点の容量です。

  3. 負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。

  4. ハッシュ テーブルのエントリ数が負荷係数と現在の容量の積を超えると、ハッシュ テーブルが再ハッシュされ (つまり、内部データ構造が再構築され)、ハッシュ テーブルのバケット数が約 2 倍になります。

  5. デフォルトの初期容量は 16 で、デフォルトの負荷係数は 0.75 です。マップのコンストラクターで他の値を指定できます。

今、私が地図を持っているとしましょう..

HashMap map=new HashMap();//HashMap key random order.
         System.out.println("Amit".hashCode());
         map.put("Amit","Java");
         map.put("mAit","J2EE");
         map.put("Saral","J2rrrEE");

衝突が発生したい 衝突がどのように発生するか教えてください..!!

4

4 に答える 4

2

正確なハッシュマップの動作は実装に依存すると思います。クラスライブラリがハッシュを行っているのを見て、衝突を構築してください。とてもシンプルです。

文字列ではなく任意のオブジェクトで衝突が必要な場合は、はるかに簡単です。hashCode()alwaysというカスタムでクラスを作成するだけreturns 0です。

于 2012-08-05T05:30:05.533 に答える
1

実際に衝突を発生させたい場合は、独自のカスタム ハッシュ コードを作成することをお勧めします。たとえば、 と の衝突が必要な場合Amit、mAitできることは 1 つで、文字の ascii 値をハッシュ コードとして使用するだけです。異なるキーの衝突が発生します。

于 2012-08-05T05:42:01.097 に答える
0

衝突は、2 つのキーが同じハッシュ キーを持つ場合に発生します。私はあなたのキーのハッシュキーを計算しませんでしたが、同じハッシュキーを持っているとは思わないので、同じハッシュキーを持っていなければ衝突は発生しません。キーと同じ文字列を配置すると、衝突が発生します

于 2012-08-05T05:32:44.613 に答える
0

ここでの衝突は間違いなく可能であり、ハッシュ テーブルの実装とは関係ありません。 HashMapは、 Object.hashCodeを使用してオブジェクトをバケットにマップすることで内部的に機能し、次にObject.equalsで衝突解決メカニズム (OpenJDK 実装は個別チェーンを使用) を使用します。

あなたの質問に答えるために、String.hashCodeは互換性のために明確に定義されています...

この文字列のハッシュ コードを返します。オブジェクトのハッシュ コードは次のStringように計算されます 。s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

intここで、は文字列s[i]のi番目の文字、 は文字列nの長さであり、べき乗を示し^ます。(空の文字列のハッシュ値はゼロです。)

または、コード内 ( OpenJDKから)

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

他のハッシュ関数と同様に、衝突が発生する可能性があります。ウィキペディアの記事によると、たとえば"FB"と"Ea"が同じ値になることが示されています。

さらに必要な場合は、ここで同じハッシュ値を持つ衝突を見つけるのは簡単な力ずくの問題になるはずです。

補足として、これがThe C Programming Languageの第 2 版の関数とどのように非常に似ているかを指摘したいと思います。

#define HASHSIZE 100

unsigned hash(char *s)
{
    unsigned hashval;

     for(hashval = 0; *s != '\0'; s++)
         hashval = *s + 31 * hashval;

     return hashval % HASHSIZE;
}
于 2012-08-05T22:18:28.040 に答える