HashMap的扩容机制、ConcurrentHashMap的原理
(n - 1) & hash : 相当于hash % n;
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
将高16位 向又移参与运算为的是使结果更加分散;
又移16位,去除高位,只使用低16位;
hashmap putVal操作
putVal 操作:
首先理解map中几个关键的元素:
table,table.length,size,threshold
table是map中的数组,该数组长度限制了map的k,v 数量;
table 默认初始值为16,loadfactor为0.75
如果设置初始容量,则table length为 capacity*4/3
table的length就是数组的长度;
size为map中k,v的个数
threshold为容量*加载因子的值,size大于该值就会进行下一次的扩容
---------------------------------------------------------------------------------------------
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put(k,v) ---> final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
// 如果evict为false,则表处于创建模式,只有ifabsent如果为真,不改变现有value;
----------------------------------------------------------------------------------------------------------------------
1. 如果没有设置初始容量,则方法调用后变开始进行resize()扩容,谈到resize(),先讨论下hashmap的构造方法;
1.1 无参构造,hashmap(), 方法内执行了loadfactor = 0.75
1.2 有参构造,hashmap(int capacity),方法内执行了loadfactor = 0.75 和 threshold = tableSizeFor(initialCapacity);
2. resize() 方法执行
2.1 oldCap、oldThr,如果是第一次调用put操作,oldCap = 0,若果执行有参构造,capacity大于0,则oldThr 大于 0;
2.1.1 如果 oldCap大于0, 大于maxInteger 则threshold=Integer.Max return oldCap;
2.1.2 如果 oldCap << 1 后,小于integer.MAX && oldCap 大于 16 则,threshold << 1;
2.2 oldCap为0,oldThr > 0,则newCap = oldThr;
2.3 其他情况, newCap = 16,newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
如果 newThr = 0,float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
如果oldCap = null ,return newCap;
否则,将oldCap中的元素放到newCap中;
1. 如果当前map中的table为空或者length为0,则初始化table的size为16,threshold为12此时创建一个table大小为16;
2. 先进行(n - 1) & hash 找到槽位,判空,为空直接插入新的节点
3. 槽点已经有值了,所以判断当前的槽点对应的值的hash和要插入的hash以及equals是否相同,相同则表示找到对应的节点了;
如果不同,则进行判断是否为节点树,如果是则按照红黑树的方式进行操作;
最后则就是不足八个节点,如果没有匹配成功,且当前节点的next为空,则插入,再接着判断当前节点个数是否为8个,如果是则转为红黑树;
last,如果存在对应的节点,修改对应的值,返回旧值;
4.最后判断size的值是否大于threshold的值,大于则进行扩容;(这个是防止所有的key都插入到同一个槽点中)