HashMap源码阅读记录
先说说1.7
1.7的时候主要存在几个问题
- key的hash值计算方式很复杂
- 在扩容的时候,因为使用的是尾插法,所以在多线程对这个变量进行操作的时候会产生一个环,导致死循环
- 最大的问题就是hash冲突问题,当一个桶里元素过多的时候,就相当于一个很长的链表,查询的时候需要从头到尾遍历一遍,时间复杂度是O(n)。
在1.8的优化
- hash计算方式,是通过key的hashcode的高16位与hashcode进行异或运算
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 使用了尾插法,解决了死循环的问题
- 计算初始容量的方式发生改变,1.7的时候是通过对1进行左移运算,直到找到比入参容量大的一个2的n次幂的数。1.8的时候,用了一种更优雅的方式,就是通过5个移位运算,得到一个低位全是1的值,最后得到一个初始容量。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
- 最重要的就是使用了数组+链表+红黑树。在数组长度大于64并且链表的长度大于8的时候会转换成一个红黑树。这样他的查询效率得到提升,以前是O(n),红黑树是O(logn)
讲一下put方法,插入的流程
- 首先通过key的hashcode来计算hash值
- 这个时候看map是否为空,如果为空的话就会先进行一次resize扩容,这时候他的初始容量大小是16
- 通过hash值和hashmap长度-1进行与运算得到桶的索引下标
- 找到桶的位置后,观察这个桶的头节点是否为空,如果是空的话就直接放进去,因为hashmapkey是不允许相同的,所以,如果不为空就检查头节点的key是否与入参的key相同,如果相同的话就直接覆盖value,如果不同就遍历这个链表,如果发现相同的key也进行覆盖,否则通过尾插法插入到链表的最后。
- 当链表的长度大于8并且数组的长度大于64的时候,会转变为红黑树