完美哈希函数及其好处

Question

Consider this class :

    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位 存储日（1到31），在黄色部分，4位 存储月份（1到12），其余部分存储年份（1到16777215）。

完美的hashFunction的好处是什么？据我所知，在HashSet中，它可以保证O(1)的添加/删除/包含操作，但我还能从中获得其他好处吗？

我看到许多哈希函数使用质数，构建哈希函数的最佳方法是什么（我想创建一个完美的哈希函数是不常见/罕见的）？

---

编辑：

关于质数->在这里回答

- user2336315

---

你的完美哈希函数只有在底层哈希数组大小适合所有可能的值时才有用（这在jdk HashSet/HashMap中是不太可能的）。 - jtahlborn

我不明白：为什么要把日期放入哈希集中，而我需要时可以轻松创建一个新实例呢？ - Andy

@Andy 这是一个例子。 - user2336315

Answer 1

完美哈希函数保证不会出现冲突。然而，要使用这种函数，必须确切知道需要哈希的键值集合，而这通常并非如此。

其他一些不那么完美但依然好用的哈希函数（以及冲突解决机制），不需要满足上述要求，并且计算速度非常快，因此它们更加适合使用。

- Juan Pablo Rinaldi

Answer 2

根据Juampi的说法，它很快。 有多快？ 大约是O(1)。 Redis是内存中通过哈希表进行常数时间查找的绝佳示例。

如果您在哈希结果上没有恰好一个元素的桶中，则需要使用equals来比较每个项目，以便获得O(1加z)的查找，其中z是桶大小。

但是确实，非常慢的哈希函数肯定不是一个好主意。

- JasonG