jdk8/11

概览

集合总体可以分为两大类：Collection和Map，Collection是存储对象的集合，Map是存储键值对的映射表。

1、Collection

集合 - 图1

  1. Set：唯一对象的集合
    • TreeSet：基于红黑树实现，支持有序操作，例如范围查找。由于是基于树结构的查找，所以查找效率最优为集合 - 图2#card=math&code=O%28logN%29&id=ovOxy)，效率不及HashSet。
    • HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作，并且失去了插入顺序的概念，即使用Iterator遍历HashSet得到的结果是不确定的。
    • LinkedHashSet：具有HashSet的查找效率，内部使用双向链表维护元素的插入删除，所以与HashSet不同，LinkedHashSet的Iterator遍历结果是确定的。
  2. List：线性存储结构
    • ArrayList：基于动态数组实现，空间连续，所以随机访问效率高。
    • Vector：加了重锁的ArrayList（几乎所有操作的方法都使用了synchronized关键字），可以看成是线程安全的ArrayList。
    • LinkedList：基于双向链表实现，空间不连续，插入删除元素比较高效。可以用作栈、队列、双向队列。
      • 用作栈的时候，栈顶在第一个元素；
      • 用作队列的时候，队头为第一个元素，队尾为最后一个元素；
      • 用作双向队列的时候，同上。
  3. Queue：一种先进先出的结构。
    • LinkedList实现；
    • PriorityQueue：基于堆结构实现的优先队列。

2、Map

集合 - 图3

  • TreeMap：基于红黑树实现，可以实现有序遍历
  • HashMap：基于哈希、链表、b红黑树实现，遍历时无序
  • HashTable：线程安全的HashMap，已经不推荐使用。
  • LinkedHashMap：使用双向链表来维护数据的顺序，典型的LRU逻辑，最近使用的元素在链表头。

设计模式

迭代器模式

集合 - 图4

Collection 继承了Iterable接口，其中的iterator()方法能够产生一个Iterator对象，接着就可以通过这个迭代器对象遍历Collection中的元素。注意，JDK5之后可以直接使用foreach的语法来更加便捷地实现遍历。

适配器模式

Arrays工具类提供asList(T…a)方法将数组类型转换为List类型。

  1. public static <T> List<T> asList(T... a) {
  2.     return new ArrayList<>(a);
  3. }

Map

HashMap

关键点

1. 底层数据结构

底层的数据结构主要是Node类型的数组table、链表和红黑树。其中Node类型实现的是Map.Entry接口，其定义结构如下：

  1. static class Node<K,V> implements Map.Entry<K,V> {
  2.     final int hash; // 对应key的hash值，为了方便之后的比较
  3.     final K key;    // HashMap中的key值必须是唯一的
  4.     V value;
  5.     Node<K,V> next;    // 使用拉链法来解决冲突，链表的关系指针
  6.     // methods ...
  7. }

2. 初始化，懒加载

初始化HashMap的时候，主要是初始了负载因子（默认情况下为0.75）。而底层的存储结构数组在初始化的时候仍然是空的，只有在第一次put的时候，才会通过resize()方法建立初始长度为 16 的table。（懒加载）

3. 哈希桶的长度

table的长度cap必然是 2 的幂次，这跟存储元素的下标计算有关，所以无论用户在构造函数指定的大小为多少，最终都会通过tableSizeFor方法将大小转为大于且最近的2的幂次。

  1. static final int tableSizeFor(int cap) {
  2.     // 获取cap的前导零个数，然后用-1逻辑右移，接着+1构造盘子（数组的上边界）
  3.     // 最终获取的值就是比cap大的最近的2的幂次
  4.     int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
  5.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  6. }

4. 元素定位

元素在数组中的下标=哈希值和哈希表容量-1相与hash & (cap - 1)。由于cap的大小必然是2的幂次，所以cap-1就是一连串的1，与hash值一与恰好就和求余等价，限制了下标在0~cap-1之间。

5. hash值计算

hash(k)方法。在获取了**key**对象的hashCode之后与这个hashCode的高16位相与的结果作为key的hash值。因为一般情况下哈希表不会太大，所以给元素分配位置的时候往往只使用了低16位，这样子相当于高16位就浪费了。故这么做是为了让高位也参与影响最终数组下标，增加散列性。

  1. static final int hash(Object key) {
  2.     int h;
  3.     // key为空的情况下，hash为0
  4.     // 否则利用Object的hashCode再进行处理
  5.     // 不处理的话：
  6.     //      那么之后每一次访问元素，只利用了hash值的低lgn位，高位没有利用到
  7.     //      使得冲突的概率较大，导致hashmap的效率变低
  8.     // 所以希望高位也被利用：
  9.     //      将高位逻辑右移一段长度与低位进行异或
  10.     //      使得高位也能够影响之后计算数组下标的结果
  11.     //      减少冲突，增加散列性
  12.     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  13. }

6. 红黑树优化

红黑树优化。jdk8之后使用的红黑树，原因可以这样理解：之前的版本中使用链表来解决哈希冲突，会出现链表过长的情况，导致元素的访问效率下降。如果不在某个阶段改变这个数据结构，这个问题就一直存在。

链表插入非常高效，但访问慢；红黑树呢，插入删除都非常可以，put/get都能够比较均衡。

7. 树化标准

为了转换为红黑树，有两个标准要同时满足：

  1. 达到树化阈值=8，但并不是一旦到达8就进行树化，从源码可以看出当整个数组的长度<64的时候仍然是使用拓容来解决，因为拓容往往能够缩小一定的链表长度。
  2. 故第二个标准就是，数组长度>=64.

还有一个反向的阈值=6，变回链表。之所以两个阈值不同，是为了防止频繁的在临界插入删除导致转化频繁。

并发问题

在并发情况下，链表转换成红黑树可能会出现死循环。测试方法，用多线程来操作 hashmap，出现了程序不退出的情况：

  1. 查看 CPU 的使用率，使用率很高说明大概率出现了死循环
  2. jps 和 jstack 命令，查看 JVM 进程的执行状态，定位出错的位置
  3. 发现是在 TreeNode 的 treeify 函数位置出现的死循环

关键源码

大佬写的代码都是能简则简，看起来还是有那么些吃力⊙﹏⊙∥

put

put方法。若key值之前存储过，则put会返回上一次的oldValue；否则返回null。

大体分为四种情况：

  1. 定位的槽没有元素，直接将key和value包装成一个新的Node节点存在该槽即可。
  2. 出现了key值是完全相同的，则用新value覆盖旧的，保证key值的唯一性。
  3. 若树化了就在红黑树上进行遍历比较key
  4. 没有树化，就从头遍历链表匹配key。匹配到key值则覆盖旧的value；若最终都没有匹配到key，就在链表的尾部添加一个新的节点，后检查是否达到树化条件。（尾插法）
  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                boolean evict) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  4.     if ((tab = table) == null || (n = tab.length) == 0) // 第一次初始
  5.         n = (tab = resize()).length; // 拓容和初始化统一为 resize()
  6.     if ((p = tab[i = (n - 1) & hash]) == null) // p对应着要访问的节点(链表头)
  7.         // n为当前table大小，tab指向table
  8.         // 根据key的hash值取余之后得到在table中的下标
  9.         // 若没有元素，则是第一次新添加，创建一个新节点
  10.         tab[i] = newNode(hash, key, value, null);
  11.     else {
  12.         Node<K,V> e; K k;
  13.         if (p.hash == hash &&
  14.             ((k = p.key) == key || (key != null && key.equals(k)))) // key值完全相同
  15.             e = p;
  16.         else if (p instanceof TreeNode) // 树化，遍历红黑树
  17.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  18.         else {
  19.             // 遍历链表，检查是否有完全匹配的key
  20.             // 无完全匹配的key，则把新节点插入链表的最后
  21.             // 否则覆盖原有的节点，保证hashmap中key的唯一性
  22.             for (int binCount = 0; ; ++binCount) {
  23.                 if ((e = p.next) == null) {
  24.                     p.next = newNode(hash, key, value, null);
  25.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  26.                         treeifyBin(tab, hash); // 大于等于阈值，链表转红黑树
  27.                     break;
  29.                 }
  30.                 // hash值不相等则key必然不相等，逻辑&&能够减少一定后边的计算
  31.                 // equals方法的效率会稍微比较低
  32.                 if (e.hash == hash &&
  33.                     ((k = e.key) == key || (key != null && key.equals(k)))) // key值完全匹配
  34.                     break;
  35.                 p = e;
  36.             }
  37.         }
  38.         if (e != null) { // existing mapping for key
  39.             V oldValue = e.value;
  40.             if (!onlyIfAbsent || oldValue == null)
  41.                 e.value = value;
  42.             afterNodeAccess(e);
  43.             return oldValue;
  44.         }
  45.     }
  46.     ++modCount;
  47.     if (++size > threshold) // 若添加元素后大小超过了阈值，进行拓容
  48.         resize();
  49.     afterNodeInsertion(evict);
  50.     return null;
  51. }

get

  1. final Node<K,V> getNode(int hash, Object key) {
  2.     // 找到对应的槽，遍历链表查找元素
  3.     Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  4.     if ((tab = table) != null && (n = tab.length) > 0 &&
  5.         (first = tab[(n - 1) & hash]) != null) {
  6.         if (first.hash == hash && // always check first node
  7.             ((k = first.key) == key || (key != null && key.equals(k))))
  8.             return first;
  9.         if ((e = first.next) != null) {
  10.             if (first instanceof TreeNode)
  11.                 return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  12.             do { // 遍历链表查找
  13.                 if (e.hash == hash &&
  14.                     ((k = e.key) == key || (key != null && key.equals(k))))
  15.                     return e;
  16.             } while ((e = e.next) != null);
  17.         }
  18.     }
  19.     return null;
  20. }

resize

  1. final Node<K,V>[] resize() {
  2.     Node<K,V>[] oldTab = table;
  3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  4.     int oldThr = threshold; // 阈值
  5.     int newCap, newThr = 0;
  6.     if (oldCap > 0) {
  7.         if (oldCap >= MAXIMUM_CAPACITY) {
  8.             threshold = Integer.MAX_VALUE;
  9.             return oldTab;
  10.         }
  11.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  12.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  13.             newThr = oldThr << 1; // double threshold
  14.     }
  15.     else if (oldThr > 0) // initial capacity was placed in threshold
  16.         newCap = oldThr;
  17.     else {               // zero initial threshold signifies using defaults
  18.         // 创建了HashMap之后，初始时Node数组=null
  19.         // 第一次put的时候，才给数组创建长度=16
  20.         newCap = DEFAULT_INITIAL_CAPACITY;
  21.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  22.     }
  23.     if (newThr == 0) {
  24.         float ft = (float)newCap * loadFactor;
  25.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  26.                   (int)ft : Integer.MAX_VALUE);
  27.     }
  28.     threshold = newThr;
  29.     @SuppressWarnings({"rawtypes","unchecked"})
  30.     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  31.     table = newTab; // 将原本的table指向新的newTab
  32.     if (oldTab != null) {
  33.         // 数组转移，元素的位置再根据数组的长度重新计算
  34.         // 因为下标值 index = hash & (len - 1)
  35.         for (int j = 0; j < oldCap; ++j) {
  36.             Node<K,V> e;
  37.             if ((e = oldTab[j]) != null) {
  38.                 oldTab[j] = null; // 将原本的对象引用去掉，使变成垃圾对象
  39.                 if (e.next == null) // 链表长度为 1，直接移动表头即可
  40.                     newTab[e.hash & (newCap - 1)] = e;
  41.                 else if (e instanceof TreeNode)  // 对于已经红黑树化的 hashmap，调用 split 方法
  42.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  43.                 else { // preserve order
  44.                     // 拓容之后，链表上的某些节点对应的槽可能会有所改变
  45.                     // 所以需要遍历链表一个个判断
  46.                     Node<K,V> loHead = null, loTail = null; // 下标值不改变的链表
  47.                     Node<K,V> hiHead = null, hiTail = null; // 下标值改变的链表
  48.                     // 因为拓容就是原本的1左移一位，如果原本oldCap 1的位置
  49.                     // hash是有值的，那么现在其下标值就会发生改变；
  50.                     // 否则不会改变。一共就只有两种情况，所以原本的一个链表最多拆成两个链表
  52.                     Node<K,V> next;
  53.                     do {
  54.                         next = e.next;
  55.                         // e.hash & oldCap 的作用实际上就是检查
  56.                         // 拓容后是否会改变原本的下标值
  57.                         if ((e.hash & oldCap) == 0) {
  58.                             // == 0 不会改变下标值
  59.                             // 尾插法连接链表
  60.                             if (loTail == null)
  61.                                 loHead = e;
  62.                             else
  63.                                 loTail.next = e;
  64.                             loTail = e;
  65.                         }
  66.                         else {
  67.                             // 拓容后下标值会变化，仍然是尾插法
  68.                             // 为了避免遍历链表，使用了一个链表尾指针
  69.                             if (hiTail == null)
  70.                                 hiHead = e;
  71.                             else
  72.                                 hiTail.next = e;
  73.                             hiTail = e;
  74.                         }
  75.                     } while ((e = next) != null);
  76.                     if (loTail != null) { // 下标值未改变的链表放入槽
  77.                         loTail.next = null;
  78.                         newTab[j] = loHead;
  79.                     }
  80.                     if (hiTail != null) { // 下标值更新的链表放入槽
  81.                         hiTail.next = null;
  82.                         newTab[j + oldCap] = hiHead;
  83.                     }
  84.                 }
  85.             }
  86.         }
  87.     }
  88.     return newTab;
  89. }

remove

  1. final Node<K,V> removeNode(int hash, Object key, Object value,
  2.                            boolean matchValue, boolean movable) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, index;
  4.     if ((tab = table) != null && (n = tab.length) > 0 && // 存储数组不为空
  5.         (p = tab[index = (n - 1) & hash]) != null) {    // 能够查找到该元素
  6.         Node<K,V> node = null, e; K k; V v;
  7.         if (p.hash == hash && // 优先比较hash值，相同则不需要额外比较key了
  8.             ((k = p.key) == key || (key != null && key.equals(k))))
  9.             node = p;
  10.         else if ((e = p.next) != null) {
  11.             if (p instanceof TreeNode) // 树化则调用树的方法 getTreeNode
  12.                 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
  13.             else {
  14.                 do { // 遍历链表查找key值匹配的元素
  15.                     if (e.hash == hash &&  // hash值不同，key必然不同；key相同，hash值必然相同
  16.                         ((k = e.key) == key ||  // key可能为null
  17.                          (key != null && key.equals(k)))) {
  18.                         node = e;
  19.                         break;
  20.                     }
  21.                     p = e;  // p最初为链表头节点，在遍历链表的过程中维护为e的上一个节点
  22.                 } while ((e = e.next) != null);
  23.             }
  24.         }
  25.         // 获得的匹配key的节点由node引用
  26.         // 从链表中删去节点并返回被删除的节点
  27.         if (node != null && (!matchValue || (v = node.value) == value ||
  28.                              (value != null && value.equals(v)))) {
  29.             if (node instanceof TreeNode)
  30.                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
  31.             else if (node == p)
  32.                 tab[index] = node.next;
  33.             else
  34.                 p.next = node.next;
  35.             ++modCount;
  36.             --size;
  37.             afterNodeRemoval(node);
  38.             return node;
  39.         }
  40.     }
  41.     return null;
  42. }

treeifyBin

  1. final void treeifyBin(Node<K,V>[] tab, int hash) {
  2.     int n, index; Node<K,V> e;
  3.     // table的大小在一定范围内时，仍然使用拓容来解决链表过长的问题。默认64
  4.     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
  5.         resize();
  6.     else if ((e = tab[index = (n - 1) & hash]) != null) {
  7.         TreeNode<K,V> hd = null, tl = null;
  8.         do { // 遍历链表，转化为树节点
  9.             TreeNode<K,V> p = replacementTreeNode(e, null);
  10.             if (tl == null)
  11.                 hd = p;
  12.             else {
  13.                 p.prev = tl;
  14.                 tl.next = p;
  15.             }
  16.             tl = p;
  17.         } while ((e = e.next) != null);
  18.         if ((tab[index] = hd) != null)
  19.             hd.treeify(tab);
  20.     }
  21. }

ConcurrentHashMap

主要使用了 Unsafe 类中的 CAS 操作还有 volatile 操作来进行支持并发操作，当然还使用 synchronized 锁代码块。来看看一些主要的操作。

Unsafe 类操作

  1. @SuppressWarnings("unchecked")
  2. static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
  3.     // 使用 volatile 来读取内存中的最新值
  4.     return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
  5. }
  7. static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
  8.                                     Node<K,V> c, Node<K,V> v) {
  9.     // 使用 cas 来更新某个哈希桶的值
  10.     return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
  11. }
  13. static final <K, V> void setTabAt(Node<K, V>[] tab, int i, Node<K, V> v) {
  14.     // 用 volatile 的方法来设置节点值，保证可见性
  15.     U.putObjectVolatile(tab, ((long) i << ASHIFT) + ABASE, v);
  16. }

putVal

可以发现在添加元素的时候，是以定位到的哈希槽的链表头作为锁，所以锁的粒度是一个哈希槽，粒度较小，能够减少发生竞争的概率，更好地支持高并发。

  1. // 整体的逻辑基本和 HashMap 的一致，增加了线程安全的操作
  2. final V putVal(K key, V value, boolean onlyIfAbsent) {
  3.     if (key == null || value == null) throw new NullPointerException();
  4.     int hash = spread(key.hashCode());
  5.     int binCount = 0;
  6.     for (Node<K,V>[] tab = table;;) {
  7.         Node<K,V> f; int n, i, fh;
  8.         if (tab == null || (n = tab.length) == 0)
  9.             tab = initTable();
  10.         else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
  11.             if (casTabAt(tab, i, null,
  12.                          new Node<K,V>(hash, key, value, null)))
  13.                 // 在空 bin 添加元素的时候使用 cas，不用加锁
  14.                 // 加不加锁的主要区别在于是否要切换到内核态，由操作系统管理
  15.                 break;
  16.         }
  17.         else if ((fh = f.hash) == MOVED)
  18.             tab = helpTransfer(tab, f);
  19.         else {
  20.             V oldVal = null;
  21.             // 查找并且添加元素到链表，使用 synchronized 进行线程安全保护
  22.             // synchronized 底层有 JVM 的优化，
  23.             // 偏向锁(仅仅标识对象头) -> 轻量级锁(cas) -> 重量级锁(切换到内核态)
  24.             // 以当前的哈希槽 f 作为锁
  25.             synchronized (f) {
  26.                 if (tabAt(tab, i) == f) {
  27.                     if (fh >= 0) {
  28.                         binCount = 1;
  29.                         for (Node<K,V> e = f;; ++binCount) {
  30.                             K ek;
  31.                             if (e.hash == hash &&
  32.                                 ((ek = e.key) == key ||
  33.                                  (ek != null && key.equals(ek)))) {
  34.                                 oldVal = e.val;
  35.                                 if (!onlyIfAbsent)
  36.                                     e.val = value;
  37.                                 break;
  38.                             }
  39.                             Node<K,V> pred = e;
  40.                             if ((e = e.next) == null) {
  41.                                 pred.next = new Node<K,V>(hash, key,
  42.                                                           value, null);
  43.                                 break;
  44.                             }
  45.                         }
  46.                     }
  47.                     else if (f instanceof TreeBin) {
  48.                         Node<K,V> p;
  49.                         binCount = 2;
  50.                         if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
  51.                                                               value)) != null) {
  52.                             oldVal = p.val;
  53.                             if (!onlyIfAbsent)
  54.                                 p.val = value;
  55.                         }
  56.                     }
  57.                 }
  58.             }
  59.             if (binCount != 0) {
  60.                 if (binCount >= TREEIFY_THRESHOLD)
  61.                     treeifyBin(tab, i);
  62.                 if (oldVal != null)
  63.                     return oldVal;
  64.                 break;
  65.             }
  66.         }
  67.     }
  68.     addCount(1L, binCount);
  69.     return null;
  70. }

TreeMap

HashMap 是一种空间换时间的映射表，其实现原理决定了内部的 Key 是无序的。那么在希望有序遍历 map 的场景下，jdk 还提供链了一种 SorrtedMap，其实现就是 TreeMap。
image.png
和其他有序集合的实现一样，默认情况下 TreeMap 是升序组织，若要降序需要实现一个 Comparator 接口。

  1. SortedMap<Integer, String> ascMap = new TreeMap<>();
  2. SortedMap<Integer, String> descMap = new TreeMap<>((k1, k2) -> k2 - k1);

List

集合 - 图6

ArrayList

  1. ArrayList底层是Object数组，默认初始为一个空的数组。只有在第一次添加元素之后，才会进行拓容到默认容量10。
  2. ArrayList的拓容，除了第一次初始化的时候拓容为默认大小 10，之后的拓容都是拓容到原本的倍1.5。拓容调用的是Arrays.copyOf（更往下调用的是本地方法System.arrayCopy）方法，重新获得一个新的拓容后的数组对象。
  3. 由于数组是空间连续的结构，所以支持快速地随机访问元素。但是添加、删除元素的效率比较低。

关键源码分析

基本属性

  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  3. {
  4.     private static final int DEFAULT_CAPACITY = 10; // 默认第一次大小为 10
  6.     private static final Object[] EMPTY_ELEMENTDATA = {};
  8.     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  10.     transient Object[] elementData; // non-private to simplify nested class access
  12.     private int size;
  13. }

constructor

  1. public ArrayList(int initialCapacity) {
  2.     if (initialCapacity > 0) {
  3.         // 按照用户的参数初始化数组的大小，用户指定多大就是多大
  4.         // 这里要区别HashMap，HashMap中为了方便计算哈希值，限定了容量必须为2的幂次
  5.         this.elementData = new Object[initialCapacity];
  6.     } else if (initialCapacity == 0) {    
  7.         this.elementData = EMPTY_ELEMENTDATA;
  8.     } else {
  9.         throw new IllegalArgumentException("Illegal Capacity: "+
  10.                                            initialCapacity);
  11.     }
  12. }
  14. public ArrayList() {    // 默认情况下，为长度=0的空数组
  15.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
  16. }

grow拓容

  1. private Object[] grow(int minCapacity) { // 拓容调用Arrays.copyOf方法
  2.     return elementData = Arrays.copyOf(elementData,
  3.                                        newCapacity(minCapacity));
  4. }
  6. private Object[] grow() {
  7.     return grow(size + 1);
  8. }
  10. private int newCapacity(int minCapacity) {
  11.     // overflow-conscious code
  12.     int oldCapacity = elementData.length;
  13.     int newCapacity = oldCapacity + (oldCapacity >> 1);        // 新容量 = 旧容量 * 1.5
  14.     if (newCapacity - minCapacity <= 0) {    
  15.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 初始为空数组
  16.             return Math.max(DEFAULT_CAPACITY, minCapacity);
  17.         if (minCapacity < 0) // 数值过大导致整数溢出
  18.             throw new OutOfMemoryError();
  19.         return minCapacity;
  20.     }
  21.     return (newCapacity - MAX_ARRAY_SIZE <= 0)
  22.         ? newCapacity
  23.         : hugeCapacity(minCapacity);
  24. }

add末尾添加元素

  1. // 末尾添加元素
  2. public boolean add(E e) {    
  3.     modCount++;
  4.     add(e, elementData, size);
  5.     return true;
  6. }
  8. private void add(E e, Object[] elementData, int s) {
  9.     if (s == elementData.length)    // 当前数组已满，就先拓容再添加元素
  10.         elementData = grow();
  11.     elementData[s] = e;
  12.     size = s + 1;
  13. }
  1. // 特定位置添加元素
  2. public void add(int index, E element) {
  3.     rangeCheckForAdd(index);    // 检查是否越界
  4.     modCount++;
  5.     final int s;
  6.     Object[] elementData;    // 用于获取当前的数组
  7.     if ((s = size) == (elementData = this.elementData).length)    // 数组已满先拓容
  8.         elementData = grow();
  9.     System.arraycopy(elementData, index,    // 将index之后的元素通过拷贝全部后移一位
  10.                      elementData, index + 1,
  11.                      s - index);
  12.     elementData[index] = element;    // 后移完成后，填入新元素
  13.     size = s + 1;
  14. }

remove删除元素

  1. public E remove(int index) {
  2.     Objects.checkIndex(index, size);
  3.     final Object[] es = elementData;
  5.     @SuppressWarnings("unchecked") E oldValue = (E) es[index];
  6.     fastRemove(es, index);
  8.     return oldValue;
  9. }
  11. private void fastRemove(Object[] es, int i) {
  12.     modCount++;
  13.     final int newSize;
  14.     if ((newSize = size - 1) > i) 
  15.         // 若删除的元素不是最后一个元素，通过逐个向前拷贝将其覆盖
  16.         // 仍然是调用本地方法arraycopy
  17.         System.arraycopy(es, i + 1, es, i, newSize - i);
  18.     es[size = newSize] = null;
  19. }

LinkedList

  1. 内部结构是双向链表。添加、删除元素效率比较高，但是不支持随机访问某个元素。
  2. 默认的添加删除行为的特性和队列一样，即先进先出。
  1. private static class Node<E> {
  2.     E item;
  3.     Node<E> next;
  4.     Node<E> prev;
  6.     Node(Node<E> prev, E element, Node<E> next) {
  7.         this.item = element;
  8.         this.next = next;
  9.         this.prev = prev;
  10.     }
  11. }

关键源码分析

基本属性

  1. public class LinkedList<E>
  2.     extends AbstractSequentialList<E>
  3.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable
  4. {
  5.     transient int size = 0;
  7.     transient Node<E> first;    // 指向第一个元素
  9.     transient Node<E> last;        // 指向最后一个元素
  10. }

add尾部添加元素

  1. public boolean add(E e) {
  2.     linkLast(e);
  3.     return true;
  4. }
  6. // 链表末尾添加新链接
  7. void linkLast(E e) {
  8.     final Node<E> l = last;    // 临时保存最后一个元素
  9.     final Node<E> newNode = new Node<>(l, e, null);    // 添加新节点
  10.     last = newNode;    // 尾结点更新为新添加的结点
  11.     if (l == null)    // 若原本链表就是空的，则更新头节点为新添加的结点
  12.         first = newNode;
  13.     else
  14.         l.next = newNode; // 否则将新的末尾结点链接上来
  15.     size++;    // 增加链表长度记录值
  16.     modCount++;
  17. }

addFirst首部添加元素

  1. private void linkFirst(E e) {
  2.     final Node<E> f = first;
  3.     final Node<E> newNode = new Node<>(null, e, f);    // 创建新的结点，向后指向first
  4.     first = newNode;
  5.     if (f == null)    // 若这是第一次添加元素，则last指向也更新
  6.         last = newNode;    
  7.     else
  8.         f.prev = newNode;    // 否则链接上当前的头节点
  9.     size++;
  10.     modCount++;
  11. }

remove删除首元素

  1. public E remove() {
  2.     return removeFirst();
  3. }
  5. public E removeFirst() {
  6.     final Node<E> f = first;
  7.     if (f == null)
  8.         throw new NoSuchElementException();
  9.     return unlinkFirst(f);
  10. }
  12. private E unlinkFirst(Node<E> f) {
  13.     // assert f == first && f != null;
  14.     final E element = f.item;
  15.     final Node<E> next = f.next;
  16.     f.item = null;
  17.     f.next = null; // help GC
  18.     first = next;    // 将首元素指针指向下一个元素
  19.     if (next == null)    // 若下一个元素为空，则说明当前链表没有元素，更新last
  20.         last = null;
  21.     else
  22.         next.prev = null;    // 否则，当前的首元素向前的链接去掉
  23.     size--;
  24.     modCount++;
  25.     return element;
  26. }

removeLast删除末尾元素

  1. public E removeLast() {
  2.     final Node<E> l = last;
  3.     if (l == null)
  4.         throw new NoSuchElementException();
  5.     return unlinkLast(l);
  6. }
  8. private E unlinkLast(Node<E> l) {
  9.     // assert l == last && l != null;
  10.     final E element = l.item;
  11.     final Node<E> prev = l.prev;    // 获取到最后一个元素的前驱
  12.     l.item = null;
  13.     l.prev = null; // help GC
  14.     last = prev;    // last指向向前移
  15.     if (prev == null)    // 若当前链表已经没有元素了，更新first
  16.         first = null;
  17.     else
  18.         prev.next = null;    // 否则，当前末尾的元素的向后链接去掉
  19.     size--;
  20.     modCount++;
  21.     return element;
  22. }

CopyOnWriteArrayList

读写分离

写操作在一个复制的数组上进行，读操作在原始的数组中进行。

写操作需要加锁保证数据的同步，写完后将原始数组指向新的数组。

  1. public boolean add(E e) {
  2.     final ReentrantLock lock = this.lock;
  3.     lock.lock();
  4.     try {
  5.         Object[] elements = getArray();
  6.         int len = elements.length;
  7.         Object[] newElements = Arrays.copyOf(elements, len + 1);
  8.         newElements[len] = e;
  9.         return true;
  10.     } finally {
  11.         lock.unlock();
  12.     }
  13. }
  15. final void setArray(Object[] a) {
  16.     array = a;
  17. }
  1. @SupperessWarnings("unchecked")
  2. private E get(Object[] a, int index) {
  3.     return (E) a[index];
  4. }

优缺分析

非常适合读多写少的场景，但是缺陷也很明显：

  • 内存占用：在写操作是需要复制一个新的数组。
  • 数据不一致：读操作可能获取到的数据不是最新的。

所以不适合内存敏感以及对实时性要求很高的场景。

Set

TreeSet

结构分析

底层使用 NavigableMap 来实现（大部分情况下就是 TreeMap），所以基础结构是红黑树。所以根据红黑树的性质，其元素是有序的，插入和删除的复杂度都是 O(logN)，查询的复杂度也是 O(logN)。

  1. public class TreeSet<E> extends AbstractSet<E>
  2.     implements NavigableSet<E>, Cloneable, java.io.Serializable
  3. {
  4.     // backing map 用于存储元素
  5.     private transient NavigableMap<E,Object> m;
  7.     TreeSet(NavigableMap<E, Object> m) { this.m = m; }
  9.     public TreeSet() {
  10.         // 使用TreeMap进行初始化
  11.         this(new TreeMap<>());
  12.     }
  14.     public TreeSet(Comparator<? super E> comparator) {
  15.         this(new TreeMap<>(comparator));
  16.     }
  17. }

集合使用

Set

作用 返回值
boolean add(E e) 添加元素
- true，set 没有包含元素 e
- false，set 中已经包含元素 e
boolean remove(Object o) 删除元素
- true，set 中包含 o
- false，set 中不包含 o
boolean contains(Object o) 判断是否包含元素 o
boolean isEmpty()
int size()

TreeSet

可以当作 Java 内置的平衡二叉树使用（虽然红黑树不是严格的平衡二叉树）

方法 介绍
public E first() 返回最小的元素
public E last() 返回最大的元素
public E lower(E e) 返回 < e 的最大元素
public E higher(E e) 返回 > e 的最小元素
public E floor(E e) 返回 <= e 的最大元素
public E ceiling(E e) 返回 >= e 的最小元素
public E pollFirst() 弹出最小元素
public E pollLast() 弹出最大元素

List

  • add(E e) add(int index, E e)
  • remove(E e) remove(int index)
  • indexOf(Object o) lastIndexOf(Object o)
  • contains(Object o)

Deque

单线程环境下用于用于替代 Stack，同时也可以作为 Queue 使用，非常灵活。

  • void push(E e), E pop() 栈顶在第一个元素的栈操作
  • offer(E e), E poll() 队首在第一个元素，队尾在最后一个元素
  • addFirst(E e) addLast(E e)
  • offerFirst(E e), offerLast(E e) 压入元素，返回成功与否的 boolean
  • pollLast() pollFirst() 弹出元素，失败返回 null
  • peekLast() peekFirst() 读取元素，失败返回 null

Queue

  • boolean offer(E e)，E poll() 队列的操作，尾部添加、头部删除

PriorityQueue

默认为小根堆，可以在构造的时候指定 Comparator

  1. // 构造一个降序排序
  2. PriorityQueue<Integer> q = new PriorityQueue<>((i1, i2) -> {
  3.     return -i1.compareTo(i2)
  4. });
  6. q.offer(e);
  7. e = q.poll();

Map

  • isEmpty() size()
  • containsKey(Object key)
  • V get(Object key) V put(K key, V value) 返回 key 之前对应的值或 null
  • V remove(Object key)

遍历

  1. for (K key: map.KeySet()) {   
  2. }
  4. for (Map.Entry<K, V> e: map.entrySet()) {
  5. }
  7. map.forEach((k, v) -> {
  8. });

常用技巧

基本类型的数组，转换成为 List

  1. int[] arr = { 4, 3, 2, 5, 12, 2, 22, 13, 34, 50, 9 };
  2. List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

List 转换成基本类型数组

  1. List<Integer> list; 
  2. int[] arr = list.stream().mapToInt(Integer::intValue).toArray();

List 普通转换成数组

  1. List<String> list;
  2. String[] arr = list.toArray(new String[list.size()]);

数字与 String 的转换

  1. // 不同数字的包装类含有对应的 toString 方法，例如 Integer
  2. String s = Integer.toString(12);
  4. // 数字的包装类同样有 parse 方法，例如 Integer
  5. int v = Integer.parseInt("123");