学习笔记——HashMap、ConcurrentHashMap

学习笔记——HashMap、ConcurrentHashMap

目录

• HashMap
• ConcurrentHashMap
• HashTable

HashMap

• 数组+链表+红黑树JDK>=1.8
  • 链表长度大于8转红黑树前提是当前map大小 不小于64，否则会优先扩容

// Map转红黑树方法源码 会判断如果 tab.length < MIN_TREEIFY_CAPACITY 也就是64 则优先选择扩容
final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        do {
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

• 线程不安全
  • JDK1.7头插法在多线程扩容下可能导致 链表成环循环链表，导致后续的所有插入无法找到尾结点
  • JDK1.8用高低位拆分转移方 式，避免了链表环的产生。
  • JDK1.8尾插法多线程下插入修改时指针指向未加锁，会丢数据这个问题1.8之前也有
  • map中的每个Node节点都保留了他的hash值便于扩容使用
  • 扩容是两倍扩容方便hash值进行 ‘&’ 运算

ConcurrentHashMap

• 线程安全的
  • JDK1.7
    • ReentrantLock 实现分段锁 AQS
      • 定位一个元素的过程需要进行两次Hash *** 作。第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。
    • 调用 size() 方法时当有较多的并发写有可能会导致全局加锁
      • 在size方法的设计上，ConcurrentHashMap 先尝试无锁 的方法，如果遍历所有segment 分段锁数组的时候整个ConcurrentHashMap没有发生写入 *** 作，则直接返回每个segment数组的size()之和，否则重新遍历，如果写入 *** 作频繁，则不得已加锁处理，这里的加锁相当于是一个全局的锁，因为对segment数组的每一个元素都加了锁。当无锁重试的次数超过阈值的话就全局加锁处理。
    • 单线程扩容
  • JDK1.8注意哦1.8的实现和1.7不一样
    • 对于hashCode对应的链表为空节点时采用 CAS
    • 对于链表已经初始化有值的使用 synchronized 实现
    • 定位一个元素只需要一次Hash
    • 调用 size() 方法引入 baseCount ，在put方法的最后，有一个addCount方法。并引入 辅助队列 来避免大量线程都在自旋等待写入baseCount。调用size()的时候只需要将baseCount和辅助队列中的数值相加即可，这样就实现了调用size()无需加锁。
  • 多线程扩容
    • ForwardingNode: 一个特殊的 Node 节点, 其hashcode=MOVED-1, 代表着此时 table 数组正在做扩容 *** 作。扩容期间, 若table某个元素为null, 那么该元素设置为 ForwardingNode, 当下个线程向这个元素插入数据时, 检查hashcode=MOVED, 就 会帮着扩容
    • 通过成员变量 transferIndex标记当前扩容至那个索引
      • table容量从n扩到2n时, 是从索引n->1的元素开始迁移, transferIndex代表当前已经迁移的元素下标
    • 在迁移过程中将元素全部迁移到 nextTable
    • MAX_RESIZERS : 定义最大可协助扩容的线程数，每新增一个线程协助扩容则 sizeCtl +1，每个线程每次最少需要扩容 16 个table的元素，如果完成一轮扩容后transferIndex <= 0 则 sizeCtl -1 ，所有线程完成迁移后则代表扩容完成。
    • 迁移完成后旧的table直接丢弃, 直接使用新的 table。
• 链表转红黑树这一块和HashMap是一样的

HashTable

全表加锁synchronized 不推荐使用

高级JAVA面试题详解(一)——CurrentHashMap、HashMap、HashTable的区别