0

Javaの関数を改ざんすることなく、ハッシュマップバケットごとのエントリ数を厳密に保証する方法はありますか？object.hashcode()

負荷率は平均です:(エントリの数）/（バケットの数）。基本的に、容量が1000のハッシュマップがあるとします。この例では、負荷率1を使用するとします。HashMapに格納する100個のオブジェクトには、常にすべてのオブジェクトに同じ値。100個のオブジェクトの保存が完了すると、それらはすべて同じHashMapバケットにマップされ、最終的にLinkedListのパフォーマンスになります。100エントリ/1000バケット=0.1<1であるため、負荷率はサイレントになります。同じオブジェクトを1M配置するとどうなりますか。LFがトリガーされることはないため、HashMapのサイズは変更されません（とにかく使用されません） 。

これは現実の世界では珍しいシナリオですが、理解を深めたいと思います。これを防ぐ方法、または少なくとも構造自体から警告を受け取る方法はHashMapにありますか？

4

2 に答える 2

5

AHashMapは、キーのハッシュ コードに基づいて、使用するバケットを常に計算します。各キーのハッシュ コードが同じ場合、それらはすべて同じバケットにマップされます。hashCode()より良い実装を提供しない限り、説明した動作を防ぐことはできません。

オープン アドレス指定を使用する Map の実装 (例: TroveのTHashMap) を見ることができます。バケットごとに常に 1 つのエントリしかありません。しかし、パフォーマンスは向上しません。衝突を別の方法で処理するだけであり、根本的な問題である不適切なハッシュ コードも解決しません。

于 2012-12-25T21:31:21.470 に答える
0

完璧な HashFunction を記述することが、探しているものを実現する唯一の方法です。

少数の特権的な入力セットが与えられると、これらの入力が個別のハッシュ値を生成するように順列テーブルを調整して、いわゆる完全ハッシュ関数を生成できます。

ピアソンのハッシングをチェックしてください

于 2012-12-25T23:00:27.060 に答える