HashMap(1.8)

发表于 | 分类于

HashMap

HashMap 由数组+链表+红黑树构成(当当前链表的长度达到8时，并且数组的长度达到64时会将链表转化为红黑树)

HashMap的put过程

  1. 判断当前整个桶是否为空，如果空的话，进行扩容(叫初始化更准确一些，扩容和初始化公用了resize方法)

  2. 如果当前key的hashcode对应的桶的位置为空，直接新建一个node放到该桶上即可

  3. 如果当前桶的第一个node的hashcode和equals都返回true那么将该位置的值修改即可

  4. 如果当前节点是红黑树的node的话，调用红黑树的添加方法

  5. 如果当前节点是链表的话，遍历链表，如果hashcode和equals都返回true的话，修改对应的值,如果找到节点尾部，那么在尾部新建一个节点，并判断是否将链表转化为红黑树

  6. 判断是否需要扩容，如果需要进行扩容

tableSizeFor方法解析

HashMap 在初始化时需要指定initialCapacity(默认16)和loadFactor(默认0.75),initialCapacity在很多规范中建议，为需要初始化数据的1.5倍或者大于等于1.5倍的2的n次方，原因是防止扩容。
但是实际上这是没有必要的，在jdk1.8中HashMap中已经解决了该问题，HashMap的tableSizeFor中通过位运算的方式会将一个不是2的n次方的数转换为大于该数的最小的2的n次方数。如果恰好是2的n次方的话那么只要大于该值就可以了。

1
2
3
4
5
6
7
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;

ConcurrentHashMap的put过程

HashMap的基本构造相同，区别是node中value和next被标识为volatile保证数据可见性，CAS + synchronized保证数据可见性。

  1. 如果tab为空初始化数组(通过sizeCtl参数使用CAS方式确保只有一个线程在初始化数组)

  2. 如果当前桶是空的，新建一个node，放到该桶的头部，通过CAS算法保证线程安全

  3. 如果当前是在扩容中通过helpTransfer并发扩容

  4. 如果当前的桶的第一个node等于(hashcode相等并且equals相等)key且不需要更新，则返回该节点

  5. 否则对该桶加锁，遍历该链表，如果找到key相等的就更新该位置位置的数据，否则就把该节点放到链表尾部

  6. 如果链表长度达到8并且桶的个数大于64会将该列表转化为红黑树。通过synchronized实现同步

  7. 计数加1，并且判断是否需要扩容，如果需要扩容，将进行并发扩容