hashcode几点规定:
- 在 Java 应用程序执行期间,在对同一对象多次调用 hashCode 方法时,必须一致地返回相同的整数,前提是将对象进行 equals 比较时所用的信息没有被修改。
- 如果根据 equals(Object) 方法,两个对象是相等的,那么对这两个对象中的每个对象调用
hashCode
方法都必须生成相同的整数结果。 - 如果根据
equals(Object) 方法,两个对象不相等,那么对这两个对象中的任一对象上调用 hashCode 方法不要求一定生成不同的整数结果。
HashMap使用分离链接法,就是在hashcode冲突的时候在hashcode对应的槽位使用链表,查找的时候先hashcode找到槽位,然后equals()方法找到链表中对应的对象。
jdk的容量是2^n次,找到槽位使用位与的方式代替模的方式提高性能
装载因子是装载的对象和hash表总数量的比值,记为λ,这个代表平均链表的长度,在一次不成功要查找的平均节点为
λ,一次成功的查找则为1+λ/2
分离链接法之外还有线性探测法和平方探测法,双散列等探测法
探测法不是在冲突的时候利用链表进行存储,而是在冲突的位置往后查找一个空位置进行存储
线性探测法会遇到一次聚焦的问题,就是一个冲突的位置后面连续的位置都不为空
那么可以进行平方探测法消除一次聚焦的问题,虽然我们引进了二次聚焦的较小影响的问题,流行的函数为f(i)=i^2。
这个时候hash表的容量必须为素数,这样在表一半为空时,才能总数插入一个元素
如果容量为非素数的时候,备选位置要少很多
网上讨论hashmap的个数为素数或者2^n次问题,是没有分清分离链接法和探测法,只有在探测法的时候,素数才是最有效的