Question

java中HashMap查找的时间复杂度是多少？

我知道哈希法的复杂度O(1)。
即使key的类型是某个类，也能哈希吗？java怎样哈希一个任意的类呢？
准确地说，是“java怎样哈希一个任意的类的实例呢？”

Answer 1

如果一个类没有重写hash方法，那么就是默认使用Object的hash方法。
怎么实现的，可以看Object类的源码。
hashMap是用数组加链表来实现的。

containsKey的复杂度是O(1)
containsValue的复杂度是O(n)

Answer 2

这个可以直接去看HashMap的源码，“java怎样哈希一个任意的类的实例呢？” 简单地说 就是通过类的equals和hashCode方法。

追问

如果很好地实现了equals和hashCode方法，HashMap能保证以O(1)的复杂度查找我自定的类的实例吗？
以及，如果没有重写equals和hashCode方法，会影响吗效率吗？
（不考虑深判等）

追答

你不写的话，就不能用自定义的类做key，HashMap不能保证O(1)的复杂度，它是根据hashcode计算出一个对象在桶的位置，一般情况下，同一类不同对象能保证hashcode值不同就可以了。

理想的情况下在较好实现了hashcode后是复杂度是O(1)，理想情况是所有键值对在桶中均匀分布，很显然不太现实把