//JDK1.8以后的HashMap部分源码
static final int hash(Object key){
int h;
return (key == null)?0(h=key.hashCode())^(h>>>16);
}
对每个hash值,将他的高低十六位进行异或操作,让低十六位同时保持了高低十六位的特征。同时也可以避免一些hash值后续出现冲突。
寻址算法就是对长度为n的数组取模,得到在数组中的位置。根据数学规律,对n取模,就是和n-1进行与运算。与运算的效率远远高于求模运算,所以采用与运算。而数组的长度通常没有很大,所以高位与出来都是0,如果不进行hash算法优化,那么高位的信息就会丢失。 综上就是JDK8的hash算法的优化。
hash冲突问题, 链表 + 红黑树 ,o(n)和o(logn) 当发生hash冲突时,会在数组中重复的位置放置一个链表,然后将value的值加入链表中。但是由于链表的查询时间复杂度是o(n),所以当链表的变的很长的时候,我们获取值会变的很慢。为了提升性能,当链表的长度到达一定值时,我们将链表转换成红黑树,红黑树的查询时间复杂度是o(logn),提升性能。
hashMap底层默认是一个数组,当这个数组满了以后,就会自动扩容,变成一个更大的数组,可以在里面放更多的元素。 hashMap的默认大小是16位的,当16存满以后就会进行2倍扩容,变成长度为32的数组。这个时候就要对原先数组中存储的元素进行rehash,即将他们的哈希值和(32-1)进行与运算,原本在长度为16的处于相同位置的几个元素,可能就要变换位置,不在同样的位置了。 为什么进行两倍扩容? 两倍扩容就是二进制位的上一位变成1,比如 0000 0000 0000 1111 变成 0000 0000 0001 1111 在进行rehash操作时,判断二进制结果是否多了一个bit的1,如果没多,那么就是原来的index,如果多了,那么就是index + oldcap,通过这个方式,避免rehash的时候,进行取模运算,位运算的性能更高。 注意,我们最好在使用hashMap的时候能够指定合适的hashMap的大小,来避免扩容,这样就能避免rehash操作,影响性能。