9

Hashtableが負のハッシュコードの使用を避けるのはなぜですか?

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

符号付きビットを 0 から正の値にするのはどこですか?(hash & 0x7FFFFFFF)しかし、符号付き 32 ビット整数を unsigned として扱うことができないのはなぜですか? またはモジュラートリックを使用して、それをポジティブにします。例えば、

public static long int_mod(int hashcode, int tab_length){
     return (hashcode % tab_length + tab_length) % tab_length;  
}
4

6 に答える 6

11

値 (およびオーバーフロー要素) を格納する内部配列 (この場合) へのインデックスとして使用されるため、値は と の間0である必要があります。したがって、マイナスになることはありません。tab.length - 1tab

衝突の可能性を過度に増加させることなく高速(hash & 0x7FFFFFFF) % tab.lengthであるため、 が優先して使用されると(hashcode % tab.length + tab.length) % tab.length思いますが、確実に知るには、設計ドキュメントを見つけるか、元の開発者に相談する必要があります。

于 2012-09-24T13:57:19.220 に答える
2

...しかし、なぜ私たちはできませんでした...

特定の実装が選択された理由を尋ねています。おそらくコードの元の作者を除いて、彼または彼女が覚えていれば、誰もあなたにそれを言うことができません。

コードにアイデアを実装するには、常に複数の方法があります。コードを書いている人は、そのうちの1つを選択する必要があります。事後に、別の特定の実装が選択されなかった理由を尋ねるのはあまり意味がありません。

于 2012-09-24T13:58:30.447 に答える
2

容量を 2 の累乗のままにすると、

private static final int CAPACITY = 64;
private static final int HASH_MASK = CAPACITY - 1;

final int index = obj.hashCode() & HASH_MASK;

基本的に、関心のある下位ビットを除くすべてをマスクします。下位 N ビットがハッシュ コード全体と同じくらい均等に分布していると仮定します。

于 2016-12-12T20:54:41.110 に答える
1

Javaにはネイティブの符号なし型はありません。が負の値になる場合は、配列へのインデックスとしてhashCode使用するすべての場所にそのようなマスキングトリックを適用する必要があります。hashCode

于 2012-09-24T13:59:37.410 に答える
1

signed int を unsigned として扱うことができないのには、表向きは大きな理由があります。最初の Java 開発者は、unsigned のサポートは不必要な複雑さであると考えていました。それ以来、これは Java が対処できるほど大きな問題ではありませんでした。

verdesmeraldが述べたように、あなたの巧妙なモッディングの効果で何かが選ばれた理由の明確な記録がない(hash & 0x7FFFFFFF) % tab.lengthため、決定の正当性を見つけることはできますが、最終的にはそれが行われた理由について推測することしかできません.

おそらくそれほど重要ではないセマンティクスの最後のポイント: Hashtable が負のハッシュコードを使用していないということは、ハッシュコードがインデックスの非負の形式に「変換」されているということです。

于 2015-05-05T05:18:42.017 に答える
0

彼自身（そしておそらく彼の同僚）を除いて、元の作者がその実装を選んだ理由について誰もあなたに話すことができません。それはうまく機能するので、とにかくそれは実際には問題ではありません。

提案された実装について：それはおそらくあなたがすべきだと思うことをしません。Javaの％演算子が実際に行うことを更新する必要があります。たとえば、ここにあります。整数のオーバーフローをミックスに追加すると、提案された式が負の値になる可能性があります。

于 2012-09-24T17:49:53.377 に答える