logo标签列表

Java语言中使用的哈希函数

javaoophashfunction
4
我知道Java有内置的HashMaps或HashTables支持。
有人知道Java语言使用了哪些哈希函数或技术吗？
是否可以调整这些函数，使它们更具体地适用于一个应用程序，以提高性能并减少访问时间？
非常感谢您的阅读！
8个回答
11

Java允许你覆盖hashCode()方法，以使用与你的应用程序和个人类型都非常适合的哈希算法：

public class Employee {

   private int id;
   // Default implementation might want to use "name" for as part of hashCode
   private String name; 

   @Override
   public int hashCode() {
     // We know that ID is always unique, so don't use name in calculating 
     // the hash code.
     return id;
   }
}
我相信你忘记了等于号。 - Andrey Vityuk
也许还想在那里加上 @Override。 - Tom Hawtin - tackline
已添加。啊 - 在浏览器文本框中编写Java代码与在IDE中的区别真是神奇 :) - levik
1
我认为这个答案是不正确的。hashCode()返回的整数是Hashtble的真正键，然后Hashtable使用哈希函数来哈希hashCode()。这个答案暗示的是Java给了你一个机会给Hashtable提供一个哈希函数，但实际上不是这样的。hashCode()给出的是真正的键，而不是哈希函数。 - Jackson Tale
@Jackson，类比于CLRS，hashCode实际上是一种哈希函数！如果你看这里的链接，它说两个不同的对象可以有相同的hashCode()。如果hashCode()是一个键，这是一个问题：当对象不同时，将它们用作哈希键也应该反映这种差异。但这并不是真的。但哈希函数可能会将两个不同的键映射到同一个槽中。因此，hashCode似乎更接近于哈希函数而不是哈希键！ - qartal
4

请放心大胆地去做。

http://www.docjar.com/html/api/java/util/HashMap.java.html

此外，您可以随时将调整阈值和初始内存使用量设置得足够大，这将在映射接近满时减少put时间。如果您的映射是多线程的，使用ConcurrentHashmap也会带来巨大的性能提升。

4

需要注意的是，如果您要覆盖hashCode方法，您应该同时覆盖equals方法。

3

哈希码是针对集合中存储的每个对象计算的。它使用标准算法进行计算（根据Effective Java）。有关详细信息，请参见该书。

您确实可以基于每个对象覆盖hashcode方法。实现hashcode方法的最佳方式是通过HashcodeBuilder（它是Commons Lang框架的一部分，请参见此处：

http://commons.apache.org/lang/

如果想了解有关哈希码的更多详细信息，请参阅本文:

http://www.ibm.com/developerworks/java/library/j-jtp05273.html

希望这有所帮助。
1
我知道Java内置了对HashMap或HashTable的美妙支持。
虽然缺乏哈希映射字面量的语法，但我不会真正这么说...
无论如何，正如其他人指出的那样，由各个类来指定它们的hashCode()应该是什么（默认值是内存地址的哈希值）。如果您实现自己的hashCode()，请确保遵循hashCode()方法的契约（特别是它需要与equals()一致），否则该类将无法用作HashMap中的键。
您还可以直接查看java.util.HashMap和其它相关源代码，以了解它们的实现方式。例如，HashMap使用一个桶数组，桶可以使用链接列表进行溢出。
进一步阅读时，您可能需要查看ConcurrentHashMap，它可以被多个线程同时安全地访问，并且TreeMap，它提供了一种构建可排序（而不一定是哈希）键的映射的方法。
有一种语法技巧可以用来获取HashMap字面量： new HashMap<String, String>(){{ put("my key", "my val"); }}; - Chii
但那并不是一个真正的HashMap；它是一个继承了HashMap的匿名类。 - Adam Jaskiewicz
1
一般来说，不必过于担心标准JDK类的哈希函数。即使您可以重写String（实际上不行），在实践中，它的哈希函数几乎总是“足够好的”。可能有一些例外情况--例如，某些类（如BigInteger和集合）每次通过循环遍历它们包含的每个元素来计算它们的哈希码，在某些情况下相当无意义--但是您多久会关注这些类的实例？
对于设计自己类的哈希码，您要做的事情是将哈希码“随机”地分布在整数范围内。为此，通常需要“混合”对象中连续字段的位（您可能会对我网站上一个图形化说明字符串哈希码如何混合位的文章感兴趣）。将当前哈希乘以奇数（通常是质数），然后加入下一个元素的哈希通常足以作为第一次尝试。（但是，当组合的数字/哈希码倾向于在其低位中具有零时，使用此方法可能会出现问题--通常没有绝对保证在所有情况下都能正常工作的实用哈希函数。）

接下来，您可以考虑测试您的哈希码。生成一系列随机对象（甚至使用一些真实对象），计算它们的哈希码，并关闭底部的16位哈希码，然后查看您得到了多少冲突。检查您得到的冲突数量是否大致符合您预期通过偶然碰撞获得的哈希碰撞的数量。例如，如果您关闭哈希码的底部16位（& 0xffff），那么在1000个随机对象之后，您预计会有大约8个冲突。在2000个对象之后，您预计会有大约30个冲突。

就性能而言，我认为在某种程度上，获得一个分布良好的哈希码通常比为哈希计算速度牺牲哈希质量更有益。

1

在编程中，有一个“hashCode/equals合同”需要遵守，即根据equals()方法相等的对象必须提供相同的hashCode()值。但并不要求所有具有相同hashCode的对象也相等。您应该查看http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode(), 以了解详细信息。

一开始可能有点难以理解涉及到的对称性，但是如果您不想在将不遵守该合同的对象放入HashMap和其他类似容器时出现奇怪的行为，那么理解它肯定是值得的。

我还建议获取Effective Java的副本，并阅读关于hashCode/equals的章节，以充分理解它。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接