5

データ構造の最終試験を検討していたところ、昨年の最終試験で質問に出くわしました。過去3時間取り組んできましたが、試行錯誤を除いて、解決方法がわかりませんでした。ここに質問があります：

「ハッシュテーブルのサイズが31で、定数gも31であり、次のハッシュコードを使用するとします。

int hash = 0;
int n = s.length();
for (int i = 0; i < n; i++)
   hash = g * hash + s.charAt(i);

また、衝突を解決するために個別のチェーンを使用すること。テーブル内の同じ場所にハッシュされる5つの異なる名前をリストしてください。」

ハッシュテーブルのサイズが定数gと同じ31であることを考えると、この問題を解決するには、おそらくモジュロ演算子を含む何らかのトリックが必要だと思います。私がそのように聞こえたら申し訳ありませんが、私はコードや何かを求めているのではなく、質問についてのいくつかの考え/ヒントを求めています。コメントをいただければ幸いです。ありがとう

4

2 に答える 2

6

Java文字列にはゼロ文字（"\0"）を含めることができるため、次のすべてが同じ値にハッシュされます。

"a"
"\0a"
"\0\0a"
"\0\0\0a"
"\0\0\0\0a"

ここに証明があります（これが使用されているハッシュであることへの参照をEricに感謝します）：

> cat Foo.java
class Foo {
    public static void main(String[] args) {                                    
        System.out.println("a".hashCode());                                     
        System.out.println("\0a".hashCode());                                   
        System.out.println("\0a".length());
        System.out.println("\0a".equals("a"));
    }                                                                           
}           
> javac Foo.java                                        
> java Foo                                                       
97
97
2
false

しかし、これが期待される答えではないかと思います。

また、これが試験だったとしたら、ASCIIコードを覚えているとは思えません。したがって、他の回答でスタイルのシーケンスを使用するための代替アプローチは次のようになります。

"\002\000"
"\001\037"

など（これらは8進数のトリプレットです-上記は両方とも62にハッシュされます）。しかし、このスタイルの5つの例（すべて同じハッシュ）を生成するのは簡単ですか？

于 2012-05-17T03:51:54.383 に答える
5

Javaの文字列ハッシュアルゴリズム（これはあなたが提示するアルゴリズムと同じです）に関するウィキペディアの記事によると：

他の一般的なハッシュ関数と同様に、衝突が発生する可能性があります。たとえば、文字列「FB」と「Ea」のハッシュ値は同じです。StringのhashCode（）実装は素数31を使用し、「a」と「B」の差は31であるため、計算は70×31 + 66=69×31+97になります。

于 2012-05-17T03:07:10.953 に答える