关于java hashcode方法对性能影响的一些疑问

Question

java api中关于hashcode的规定，就是两个值相等，他们的hashcode一定相等，但hashcode相等，其对应的值不一定相等，说hashcode相等会影响hashtables性能，具体怎么影响性能的。

Answer 1

最好的办法是去阅读HashMap或者Hashtable的代码（二者的实现是比较接近的），或者研究一下数据结构里面讲述的Hash表的数据结构，HashMap&Hashtable是通过拉链法来构造的。 检索的时候使用HashCode作为Hash算法的Key，当多个HashCode相同时，需要逐个调用equals方法来查找。

极端情况下，如果所有的对象HashCode都相同，则检索复杂度为O(n)，如果Hash后所有的对象的Hash编码都不同（不同HashCode的Hash结果也有可能是相同的），则检索复杂度为O(1)