Java集合源码浅析

简介

  • Java集合类是Java将一些基本的和使用频率极高的基础类进行封装和增强后再以一个类的形式提供。集合类是可以往里面保存多个对象的类，存放的是对象，不同的集合类有不同的功能和特点，适合不同的场合，用以解决一些实际问题。
  • Java中的集合类可以分为两大类：一类是实现Collection接口；另一类是实现Map接口
  • Collection中的集合称为单列集合(单身狗)，Map中的集合称为双列集合（情侣）。
  • 分析环境：JDK1.8

区别

  • 集合与数组的区别
    数组不仅可以存放基本数据类型也可以容纳属于同一种类型的对象，数组的长度是不可以变的，数组只能存放同一种类型的对象。
    集合类容纳的对象都是Object类的实例，集合类中容纳的都是指向Object类对象的指针，集合的长度是可变的，可以存放不同的对象。

  • 一、Collection
    集合的顶级接口

    • List
      接口：元素按进入先后有序保存，可重复

      • ArrayList
        底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素
        无参默认对象数组elementData为空，添加元素默认初始化大小为10，当大于10 调用grow(minCapacity),新的大小为 旧大小+旧大小右移1位，也就是：旧大小*（1+1/2）=旧大小的1.5陪，扩容之后调用Arrays.copyOf() 返回一个新的数组，底层用的是System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)方法。

      • LinkedList
        底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素
        有一个私有的静态内部类Node 节点，保存首尾指针的指向和本身的数据，插入可选首插入（addFirst()）和尾插(addLast()),默认的add() 最后使用的是linkLast() 尾插入

      • Vector
        底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素.
        默认数组的初始化大小为10，扩容最后调的也是grow(minCapacity) 方法，线程安全用的是synchronized 关键字
        该类和ArrayList非常相似，扩容数据拷贝用的也是System.arraycopy。Vector可以指定增长因子，如果该增长因子指定了，那么扩容的时候会每次新的数组大小会在原数组的大小基础上加上增长因子；如果不指定增长因子，那么就给原数组大小*2，
        源码：int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

        • Stack
          栈是Vector的一个子类，它实现了一个标准的后进先出的栈。也是线程安全的。常用方法： 
              E push(E item) //入栈、
    synchronized E pop() //栈顶元素出栈、
    boolean empty() //判定栈是否为空、
    synchronized E peek()  //获取栈顶元素、
    synchronized int search(Object obj) //判端元素obj是否在栈中，如果在返回1，不在返回-1
    • Set
      接口： 仅接收一次，不可重复，并做内部排序

      • HashSet
        如果看源码会发现，当创建HashSet时，内部会初始化一个HashMap,片段代码如下:

            private transient HashMap<E,Object> map;


    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     * 默认
     */
    public HashSet() {
        map = new HashMap<>();
    }

    /**
    * 创建的是一个LinkedHashMap带有制定大小和加载因子的容器
    */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

        底层数据结构采用HashMap来实现（Oh my God ！！！ Collection 才是爸爸呀，没想到真相却是隔壁老王的 Map.），元素都存到HashMap键值对的Key上面。
        add 方法调用的是map的put方法，然后 PRESENT 这个看源码是一个静态 final 的对象，主要就是判段是否add成功而已。为什么不为null呢（这样更省内存）？
        因为PRESENT=null,假设key已经存在了，put方法会返回旧的value，也就是null,null==null ,这样就和add方法的返回结果冲突了，添加失败也返回true。
        元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的

        • LinkedHashSet
          这货是继承HashSet,底层数据是用LinkedHashMap 实现的。元素有序且唯一。

      • TreeSet
        一个包含有序的且没有重复元素的集合，通过TreeMap实现,TreeSet中的元素必须实现Comparable接口并重写compareTo()方法(除非是Java类库中定义的类，如String，Integer等,因为这些类已经实现了Comparable接口)

    • 最后
      发现好多集合实现类继承或实现了AbstractList、RandmoAccess、Cloneable、Serializable
      - 继承了AbstractList，实现了List接口。
      - 实现了RandmoAccess接口，即提供了随机访问功能。
      - 实现了Cloneable接口，即实现克隆功能。
      - Serializable接口，表示支持序列化

  • 二、Map
    和 Collection 并列的顶级接口

    • 1、Hashtable
      接口实现类，Hashtable也叫散列表（也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
      这个映射函数叫做散列函数，存放记录的数组叫做散列表。上面集合介绍了数组与链表。数组的特点就是查找容易，插入删除困难；而链表的特点就是查找困难，但是插入删除容易。既然两者各有优缺点，那么我们就将两者的有点结合起来，让它查找容易，插入删除也会快起来。哈希表就是讲两者结合起来的产物。
      散列函数能使对一个数据序列的访问过程更加迅速有效，数据元素将被更快地定位，使用散列函数将被查找的键转化为数组的索引。
      在理想的状态下，不同的键会被转化成不同的索引值。但是这是现实社会，当有不同的键生成相同的索引时就会产生冲突。
      解决冲突的方法有拉链法(又叫链地址法)和开放寻址法。

      • 拉链法：
        就是把具有相同散列地址的索引值放在同一个单链表中。

        拉链法.png

        图中，”John Smith”和”Sandra Dee”通过散列函数都指向152这个索引，该索引又指向了一个链表，在链表中依次存储了这两个字符串。
        该方法就是链地址法，查找分为两步：首先是根据散列值找到对应的链表，然后沿着链表的顺序找到相应的键。

      • 开放寻址法：
        就是如果存在相同的散列地址索引时，如果Key被占用了，那就把索引值+1 ，如果是空那就存入，否则继续+1寻找。


        开放寻址法.png

        在该图中，”Ted Baker”有唯一哈希值153的，但是由于153被”Sandra Dee”占用了。而原先”Sandra Dee”和”John Smith”的哈希值都是152的，但是在对”Sandra Dee”进行哈希的是偶发现152已经被占用了，所以往下找发现153没有被占用，就将其存放在153。后面”Ted Baker”哈希到153上，发现被占用了，就会往下找，发现154没有被占用，所以将其存放到154上面。

        图片原文链接：https://blog.csdn.net/iva_brother/article/details/82253989

        我们的主角 Hashtable，使用的是拉链法，Entry单链表解决冲突,Entry是实现Map.Entry< K ,V>接口的静态内部类
        Hashtable在jdk1.0就开始引入，它是属于线程安全的，在很多方法使用了synchronized同步关键字，可以知道它效率是有点低的。
        但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常.
        重点：

      • HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，
      • Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。
      • Hashtable中key和value都不允许为null，而HashMap中key和value都允许为null（key只能有一个为null，而value则可以有多个为null）。
      • Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍
      • Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算，且Hashtable先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变
      • 1-1、Properties
        该类主要用于读取Java的配置文件，继承自Hashtable,也是使用一种键值对的形式来保存属性集。加载配置文件和读取配置文件一般用到它。

    • 2、HashMap
      我是一个很懒的程序员，会用不就好了吗，管它怎么实现的。但是面试被面试官吊打，痛定思痛觉得研究一番。
      在集合里面HashMap才是大佬（渣男），和Collection下的几个子类都有一腿。来吧扒一扒它身体构造。
      下面是一些部分的源码：

      // 初始化容量，左移N位，就等于乘于2的N次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 容量的极限值，默认设置为2^31
static final int MAXIMUM_CAPACITY = 1 << 30;

// 负载因子默认值
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 需要从链表转换为红黑树时,链表节点的最小长度
static final int TREEIFY_THRESHOLD = 8;

// 转换为红黑树时数组的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

// resize操作时,红黑树节点个数小于6则转换为链表。
static final int UNTREEIFY_THRESHOLD = 6;

// Node数组，在第一次使用时需要初始化，当分配时，长度总是2的幂次方
transient Node<K,V>[] table;

// map中所包含键值对的数量
transient int size;

//用于记录集合的修改次数
transient int modCount;

//HashMap阈值，用于判断是否需要扩容(threshold = 容量*loadFactor)
int threshold;

//负载因子
final float loadFactor;

//链表节点
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;  //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next; //链表的下一个节点
        //...
 }

// 红黑树节点
 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        // ....
}

      在JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度大于8，并且数组大小大于等于 MIN_TREEIFY_CAPACITY=64 时，链表转为红黑树。
      而红黑树的个数小于UNTREEIFY_THRESHOLD=6时又转为链表。HashMap的初始化默认大小是16，负载因子是0.75， 如果自己传入初始大小x，初始化大小为 大于x的 2的整数次方，例如如果传10，大小为16。来看源码：

      //如果我们指定大小，最终走的是这个方法
 public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    // 看这个代码，
    this.threshold = tableSizeFor(initialCapacity);
}

// 这个方法就是实现初始化的大小最终为大于cap的最小的2的整数次方
static final int tableSizeFor(int cap) {
        // 是为了防止，cap已经是2的幂。如果cap已经是2的幂， 又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍
        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;
}

      比如cap=9时，进行，无符号位移是怎样的，如下图：


      tableSizeFor.png

      由上图可知，当执行到 n |= n >>> 16 时，n 的二进制为：0000 1111，由最后一步知道n 不是大于 MAXIMUM_CAPACITY的，所以：n=n+1 转换为二进制为 0001 0000 转换为十进制:2^4 = 16。这个是哪位大佬想出来的算法确实牛掰！！！

      HashMap在哈希冲突的时候用的也是拉链法。HashMap的哈希函数是这样的，key的hash值高16位不变，低16位与高16位异或作为key的最终hash值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）。源码如下：

      static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
      hash.png

      为啥这样设计呢？，这个和HashMap 的table下标计算有关，在代码里多处地方会看到这样的代码tab[i = (n - 1) & hash] 因为，table的长度都是2的幂，因此index仅与hash值的低n位有关，hash值的高位都被与操作置为0了。
      假设table.length=2^4=16.

      hash2.png

      由上图可以看到，只有hash值的低4位参与了运算。
      这样做很容易产生碰撞。设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。接下来看看HashMap的存储,put 方法，源码分析：

      public V put(K key, V value) {
    // 将key 散列传入
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果为空，初始化数组，调用resize() 进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
        //计算对应的数组下标 (n - 1) & hash，也就是key所在数组的索引
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果该位置为空，直接存入
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果key存在，并且相同，则直接覆盖
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            // 如果是红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        // 链表节点
            for (int binCount = 0; ; ++binCount) {
            //遍历链表，找到尾节点插入
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果数组大小大于等于8，则转为红黑树（为啥是TREEIFY_THRESHOLD - 1，因为遍历是从0开始）
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //遍历过程中，碰到key已经存在直接覆盖并break退出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
                // HashMap专门预留给LinkedHashMap 回调的
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 达到数组扩容阀值，则进行扩容
    if (++size > threshold)
        resize();
        // 这个也是预留给LinkedHashMap 的，看源码其实都是空，可以不用管
    afterNodeInsertion(evict);
    return null;
}

      看了源码，感觉没想象中的那么复杂吧？你确定不复杂？？？ 在来看看链表转为红黑树的方法treeifyBin(tab, hash) 源码分析:

      final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 这里还有一个限制条件，当table的长度小于MIN_TREEIFY_CAPACITY（64）时，只是进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
        // 根据hash值和数组长度进行取模运算后，得到链表的首节点
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 定义首、尾节点
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 将该节点转换为 树节点
            TreeNode<K,V> 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);
    }
}

// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

final void treeify(Node<K,V>[] tab) {
    // 定义树的根节点
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;// 设置当前节点的左右节点为空
        if (root == null) {
            x.parent = null;
            x.red = false;// 当前节点的红色属性设为false（把当前节点设为黑色）
            root = x;// 根节点指向到当前节点
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
             // 从根节点开始遍历，此遍历没有设置边界，只能从内部跳出
            for (TreeNode<K,V> p = root;;) {
                // dir 标识方向（左右）、ph标识当前树节点的hash值
                int dir, ph;
                K pk = p.key;
                // 如果当前树节点hash值 大于 当前链表节点的hash值
                if ((ph = p.hash) > h)
                    dir = -1;// 标识当前链表节点会放到当前树节点的左侧
                else if (ph < h)
                    dir = 1;//否则右侧
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                /*
                 * 如果dir 小于等于0 ： 当前链表节点一定放置在当前树节点的左侧，但不一定是该树节点的左孩子，也可能是左孩子的右孩子 或者 更深层次的节点。
                 * 如果dir 大于0 ： 当前链表节点一定放置在当前树节点的右侧，但不一定是该树节点的右孩子，也可能是右孩子的左孩子 或者 更深层次的节点。
                 * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩子 为 起始节点  再从GOTO1 处开始 重新寻找自己（当前链表节点）的位置
                 * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂载到当前树节点的左或者右侧了。
                 * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点进行处理了。
                 */
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;//做为左孩子
                    else
                        xp.right = x;
                        // 平衡算法，保证该树始终维持红黑树的特性，这个不解析了好吗
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    // 把所有的链表节点都遍历完之后，最终构造出来的树可能经历多个平衡操作，根节点目前到底是链表的哪一个节点是不确定的
    // 因为我们要基于树来做查找，所以就应该把 tab[N] 得到的对象一定根节点对象，而目前只是链表的第一个节点对象，所以要做相应的处理。
    // 这个方法里做的事情，就是保证树的根节点一定也要成为链表的首节点
    // 不能再挖了，好多
    moveRootToFront(tab, root);
}

      老实说链表转换为红黑树的代码还是有点东西的，有兴趣自己看，还是看相对简单的，扩容方法resize() :

      final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 保存当前阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
    // 保存当前阈值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新的数组容量为老的数组容量的2倍（左移1位相当于乘以2），并且老的数组容量大于等于默认初始化容量（16）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 老阀值的2倍
    }
    else if (oldThr > 0) // initial capacity was placed in threshold 这一步也就意味着构造该map的时候，指定了初始化容量
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults 
        // 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                 /** 这里注意, table中存放的只是Node的引用,这里将oldTab[j]=null只是清除旧表的引用
                   * 但是真正的node节点还在, 只是现在由e指向它
                   */
                oldTab[j] = null;
                //桶中只有一个节点，直接放入新桶中
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //  类型为红黑树，则对树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //否则为链表
                    //如下两个就是原链表拆分成的两个链表
                    //  loHead 表示老值,老值的意思是扩容后，该链表中计算出索引位置不变的元素
                    Node<K,V> loHead = null, loTail = null;
                    //  hiHead 表示新值，新值的意思是扩容后，计算出索引位置发生变化的元素
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引，也就是老值链表
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                        // 原索引+oldCap
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                     // 老值链表赋值给新数组到原来的数组索引位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //新值链表赋值到新的数组索引位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 返回扩容后的新数组
    return newTab;
}

      在JDK1.7时，扩容方法transfer 在多线程下可能会出现环状链表但是在jdk8中优化了不会出现这个问题了。至此，HashMap 的大部分核心算是讲完了，还有红黑树的核心没讲(篇幅有限)。还有get(),这个比较简单，知道拉链法也就是链地址法，首先通过(n - 1) & hash 找到索引，然后判断是链表还是红黑树和key是否相等最终返回，不算难，不贴代码了，最终调用的是getNode(hash(key), key) 这个方法。有兴趣可以自己去看一下。

      • LinkedHashMap
        继承自HashMap,所以和HashMap大致是一样的。双向链表可以保持顺序,可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)。如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序。如果accessOrder为flase的话，则按插入顺序来遍历。
        accessOrder 默认为false,在创建LinkedHashMap 可以修改。

    • ConcurrentHashMap
      这个可以说是HashMap和Hashtable的结合优化版本。JDK1.5后为了改进Hashtable的痛点，ConcurrentHashMap应运而生，那时候的它使用的是分段锁技术（将锁一段一段的存储，然后给每一段数据配一把锁（segment），当一个线程占用一把锁（segment）访问其中一段数据的时候，其他段的数据也能被其它的线程访问，默认分配16个segment。默认比Hashtable效率提高16倍。）。但在JDK1.8 取消了segment分段锁，而采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构一样，数组+链表+红黑二叉树。别看后面也有个HashMap，但是它可不是继承自HashMap的哦。它继承自AbstractMap。
      ConcurrentHashMap 结构和HashMap 类似，下面列出HashMap没有的几个属性

          /*

    这个sizeCtl是volatile的，那么他是线程可见的
    未初始化：
        sizeCtl=0：表示没有指定初始容量。
        sizeCtl>0：表示初始容量。

    初始化中：
        sizeCtl=-1,标记作用，告知其他线程，正在初始化

    正常状态：
        sizeCtl=0.75n ,扩容阈值

    扩容中:
    sizeCtl < 0 : 表示有其他线程正在执行扩容
    sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2 :表示此时只有一个线程在执行扩容

     */
    private transient volatile int sizeCtl; 

    // 以下两个是用来控制扩容的时候 单线程进入的变量
    private static int RESIZE_STAMP_BITS = 16;
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    static final int MOVED     = -1; // hash值是-1，表示这是一个forwardNode节点
    static final int TREEBIN   = -2; // hash值是-2  表示这时一个TreeBin节点

      ConcurrentHashMap 如何利用CAS和Synchronized进行高效的同步更新数据的。看看put 方法。

      public V put(K key, V value) {
    return putVal(key, value, false);
}

final V putVal(K key, V value, boolean onlyIfAbsent) {
    //ConcurrentHashMap 不允许插入null键
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    //for循环的作用：因为更新元素是使用CAS机制更新，需要不断的失败重试，直到成功为止
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            //如果第一次来，初始化
            tab = initTable();
            // 和HashMap 熟悉的(n - 1) & hash 一样，定位索引位置
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            //使用CAS进行添加，失败则break重新添加
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // 检查到内部正在移动元素（Node[] 数组扩容）
        else if ((fh = f.hash) == MOVED)
            // 帮助它扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            //锁住链表或红黑二叉树的头结点
            synchronized (f) {
                //判断f是否是链表的头结点
                if (tabAt(tab, i) == f) {
                    //如果fh>=0 是链表节点
                    if (fh >= 0) {
                        binCount = 1;
                         //遍历链表所有节点
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 存在key,则覆盖
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 否则插入尾部
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    // 红黑树节点
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        //添加树节点
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // binCount != 0 说明上面在做链表操作
            if (binCount != 0) {
                //如果链表长度已经达到临界值8 就需要把链表转换为树结构，但是它还要满足一个条件就是数组要大于等于 MIN_TREEIFY_CAPACITY=64
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

      看看初始化数组的源码，initTable()。

      private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // 如果小于0 背其他线程抢到初始化了
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
            // cas 正在初始化
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

      HashMap 的扩容方法是 resize(),而ConcurrentHashMap 则是tryPresize与 transfer :

      private final void tryPresize(int size) {
    // 判断是否大于最大值，否则计算最小的2次幂，tableSizeFor 方法之前讲过贼经典
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
        tableSizeFor(size + (size >>> 1) + 1);
    int sc;
    while ((sc = sizeCtl) >= 0) {
        Node<K,V>[] tab = table; int n;
        // 如果还没初始化
        if (tab == null || (n = tab.length) == 0) {
            n = (sc > c) ? sc : c;
            //cas修改sizeCtl为-1，表示table正在进行初始化
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if (table == tab) {
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = nt;
                        sc = n - (n >>> 2); // n*(1-1/4)= n * 0.75
                    }
                } finally {
                    sizeCtl = sc;
                }
            }
        }
        else if (c <= sc || n >= MAXIMUM_CAPACITY)
            break;
        else if (tab == table) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                Node<K,V>[] nt;
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null); //数据迁移，这个核心中的核心
        }
    }
}


private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // stride 在单核下直接等于 n，多核模式下为 (n>>>3)/NCPU，如果比最小值(16)小那等于最小值
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // initiating
        try {
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];//初始化 容量大小是n的2倍
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;//用于控制迁移的位置
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // to ensure sweep before committing nextTab
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;

            else if ((nextIndex = transferIndex) <= 0) {
             // 这里 transferIndex 一旦小于等于 0，说明原数组的所有位置都有相应的线程去处理了
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        else if ((f = tabAt(tab, i)) == null)
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            advance = true; // already processed
        else {
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    if (fh >= 0) {
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) {
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
                            if ((h & n) == 0) {
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    loTail.next = p;
                                loTail = p;
                                ++lc;
                            }
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}

      只要把这几个方法看懂，其他的都容易。

    • WeakHashMap
      继承AbstractMap类，使用弱密钥的哈希表。它的特殊之处在于 WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法

    • 3、TreeMap
      底层数据结构红黑树，可以实现元素的自动排序，默认情况下通过Key值的自然顺序进行排序。

    • 4、IdentifyHashMap
      我没用过 囧 ，它和HashMap有个不同就是：HashMap一般比较值相同(equals)就行了,IdentifyHashMap 用的是 ==

参考链接：
https://www.cnblogs.com/liujinhong/p/6576543.html
https://blog.csdn.net/weixin_42340670/article/details/80503863
https://blog.csdn.net/weixin_42340670/article/details/80531795
https://www.jianshu.com/p/d10256f0ebea

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,013评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,205评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,370评论 0赞 342
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,168评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,153评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,954评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,271评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,916评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,382评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,877评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,989评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,624评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,209评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,199评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,418评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,401评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,700评论 2赞 345