如何制作有效的hashCode？

Question

我有三个hashCode方法如下,我根据它们的效率优先考虑它们.我想知道是否有任何其他方法来制作更有效的hashCode方法.

1) public int hashCode() { //terrible
     return 5; 
   }
2) public int hashCode() { //a bit less terrible
     return name.length; 
   }
3) public int hashCode() { //better
     final int prime = 31;
     int result = 1;
     result = prime * result + ((name == null) ? 0 : name.hashCode());
     return result;
   }

Answer 1

没有万无一失的方法可以保证您的hashcode功能是最佳的,因为它是通过两种不同的指标来衡量的.

• 效率 - 计算速度有多快.
• 碰撞 - 碰撞的几率是多少.

您的:

1. 以碰撞为代价最大限度地提高效率.
2. 找到一个位于中间的地方 - 但仍然不好.
3. 效率最低但最好避免碰撞 - 仍然不一定是最好的.

你必须自己找到平衡.

有时很明显,有一种非常有效的方法永远不会发生冲突(例如ordinala enum).

有时候记住这些值是一个很好的解决方案 - 这种方式甚至可以减轻非常低效的方法,因为它只能被计算一次.这有明显的成本,也必须平衡.

有时,代码的整体功能有助于您的选择.假设您想要将File对象放入HashMap.有很多选择是明确的:

1. 使用文件名的哈希码.
2. 使用文件路径的哈希码.
3. 使用文件内容的crc.
4. 使用文件内容的SHA1摘要的哈希码.

为什么碰撞很糟糕

其中一个主要用途hashcode是将对象插入到HashMap.该算法从对象请求哈希码并使用它来决定将对象放入哪个桶.如果哈希与另一个对象冲突,则该桶中将存在另一个对象,在这种情况下,桶将不得不增长,这会花费时间.如果所有哈希都是唯一的,那么地图将是每个桶一个项目,因此最大效率.

有关如何工作的更深入讨论,请参阅优秀的WikiPedia关于哈希表的文章HashMap.

Answer 2

我根据它们的效率对它们进行优先级排序

您的列表按效率升序排序- 如果您所说的“效率”是指应用程序的性能，而不是hashCode与其他所有内容隔离的方法的延迟。分散性不好的哈希码会导致通过内部链表进行线性或近线性搜索HashMap，完全抵消了哈希表的优势。

特别要注意的是，在当今的体系结构中，计算比指针取消引用便宜得多，并且成本固定较低。一次高速缓存未命中相当于一千次简单的算术运算，并且每次指针取消引用都是潜在的高速缓存未命中。