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？AFAIK，它可以保证添加/删除/包含在其中O(1)，HashSet但我可以获得其他好处吗？

我看到许多散列函数使用素数，构造一个的最佳方式是什么（我想创建一个完美的散列函数是不常见的/罕见的）？

编辑 ：

关于素数->在这里回答

4

2 回答 2

8

一个完美的哈希函数保证你不会有冲突。但是，为了能够使用一个，您必须确切地知道需要散列的一组键值，但通常情况并非如此。

其他不是那么完美但仍然很好的哈希函数（以及冲突解决机制）没有这个要求并且无论如何计算都非常快，因此它们通常更合适。

于 2013-05-07T20:11:17.323 回答
1

根据 Juampi，它很快。多快？大约 O(1)。Redis 是通过哈希表在内存中进行恒定时间查找的一个很好的例子。

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

但是是的，非常慢的散列函数当然不是一个好主意。

于 2013-05-07T21:09:46.217 回答