7

このクラスを検討してください：

    public final class MyDate {
        private int year, month, day;

        public MyDate(int year, int month, int day) {
             this.year = year;
             this.month = month;
             this.day = day;
        }

        //Some stuff

        @Override
        public int hashCode() {
             return ((year << 4) | month) << 5 | day;
        }
}

これは完全なハッシュ関数です。なぜなら、メモリには以下があるからです。

ここに画像の説明を入力

赤5 bitsは日（1～31）、黄色4 bitsは月（1～12）、その他は年（1～16777215）を格納します。

完璧の利点は何hashFunctionですか? 私の知る限り、追加/削除/含むことを保証できますが、それO(1)をHashSet持つことで他の利点を得ることができますか?

多くのハッシュ関数が素数を使用しているのを見ましたが、素数を構築する最良の方法は何ですか (完全なハッシュ関数を作成することは一般的でない/まれだと思います) ?

編集 ：

素数について ->ここで答えた

4

2 に答える 2

8

完全なハッシュ関数は、衝突がないことを保証します。ただし、これを使用できるようにするためには、ハッシュする必要がある一連のキー値を正確に把握する必要がありますが、これは多くの場合そうではありません。

他のものは完璧ではありませんが、(衝突解決メカニズムとともに) 優れたハッシュ関数にはその要件がなく、とにかく計算が非常に高速であるため、多くの場合、より適切です。

于 2013-05-07T20:11:17.323 に答える
1

Juampi によると、高速です。どのくらい速いのか？約 O(1)。Redis は、ハッシュ テーブルを介したメモリ内の一定時間のルックアップの好例です。

ハッシュの結果に正確に 1 つの要素のバケットがない場合は、equals を使用して各項目を比較する必要があるため、O(1 プラス z) のルックアップを取得します。ここで、z はバケット サイズです。

しかし、そうです、非常に遅いハッシュ関数は確かに良いアイデアではありません。

于 2013-05-07T21:09:46.217 に答える