有人知道Java语言使用了哪些哈希函数或技术吗?
是否可以调整这些函数,使它们更具体地适用于一个应用程序,以提高性能并减少访问时间?
非常感谢您的阅读!
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;
}
}
请放心大胆地去做。
http://www.docjar.com/html/api/java/util/HashMap.java.html
此外,您可以随时将调整阈值和初始内存使用量设置得足够大,这将在映射接近满时减少put时间。如果您的映射是多线程的,使用ConcurrentHashmap也会带来巨大的性能提升。
需要注意的是,如果您要覆盖hashCode方法,您应该同时覆盖equals方法。
哈希码是针对集合中存储的每个对象计算的。它使用标准算法进行计算(根据Effective Java)。有关详细信息,请参见该书。
您确实可以基于每个对象覆盖hashcode方法。实现hashcode方法的最佳方式是通过HashcodeBuilder(它是Commons Lang框架的一部分,请参见此处:
http://commons.apache.org/lang/
如果想了解有关哈希码的更多详细信息,请参阅本文:
http://www.ibm.com/developerworks/java/library/j-jtp05273.html
希望这有所帮助。接下来,您可以考虑测试您的哈希码。生成一系列随机对象(甚至使用一些真实对象),计算它们的哈希码,并关闭底部的16位哈希码,然后查看您得到了多少冲突。检查您得到的冲突数量是否大致符合您预期通过偶然碰撞获得的哈希碰撞的数量。例如,如果您关闭哈希码的底部16位(& 0xffff),那么在1000个随机对象之后,您预计会有大约8个冲突。在2000个对象之后,您预计会有大约30个冲突。
就性能而言,我认为在某种程度上,获得一个分布良好的哈希码通常比为哈希计算速度牺牲哈希质量更有益。
在编程中,有一个“hashCode/equals合同”需要遵守,即根据equals()方法相等的对象必须提供相同的hashCode()值。但并不要求所有具有相同hashCode的对象也相等。您应该查看http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode(), 以了解详细信息。
一开始可能有点难以理解涉及到的对称性,但是如果您不想在将不遵守该合同的对象放入HashMap和其他类似容器时出现奇怪的行为,那么理解它肯定是值得的。
我还建议获取Effective Java的副本,并阅读关于hashCode/equals的章节,以充分理解它。
如果你知道你需要快速哈希,我建议使用另一种实现:尝试使用fastutil(http://fastutil.dsi.unimi.it/)或trove(http://trove4j.sourceforge.net/)。它们显然更快,但是类型特定。