Collection 类关系图 | Java 全栈知识体系1. Java集合框架图更详细版Java集合主要有3种重要的类型List是一个有序集合可以放重复的数据ArrayList基于可变数组LinkedList基于链表数据结构Set是一个无序集合不允许放重复的数据HashSet无序的不可重复的TreeSet可以对Set集合进行排序默认自然排序即升序LinkedHashSet基于哈希表和链接列表Map是一个无序集合集合中包含一个键对象一个值对象键对象不允许重复值对象可以重复身份证号—姓名HashMapHashTableTreeMapLinkedHashMap2 List2.1 ArrayList2.1.1 set/** * Replaces the element at the specified position in this list with * the specified element. * 用指定的元素替代此列表中指定位置上的元素 */ public E set(int index, E element) { Objects.checkIndex(index, size);//检查index是否合法 E oldValue elementData(index); elementData[index] element;//赋值 return oldValue; }2.1.2 add//将指定的元素添加到列表的尾部 public boolean add(E e){ ensureCapacity(size1);确保容量满足 elementData[size] e; return true; }元素往后移动会出现要扩容的情况2.1.3 remove2.2 LinkedList2.2.1 数据结构2.2.2 根据序号获取Entry对象2.2.3 添加元素2.2.4 删除元素2.3 CopyOnWriteArrayList2.3.1 没有 CopyOnWriteArrayList 的日子其实在 CopyOnWriteArrayList 出现之前我们已经有了 ArrayList 和 LinkedList 作为 List 的数组和链表的实现而且也有了线程安全的 Vector 和 Collections.synchronizedList() 可以使用。1ArrayList 和 LinkedList线程不安全在多线程的情况下插入数据的时候会造成数据丢失不可编辑在迭代期间进行添加或删除元素等操作会抛出 ConcurrentModificationException 异常。在 ArrayList 源码里的 ListItr 的 next 方法中有一个 checkForComodification 方法代码如下final void checkForComodification() { if (modCount ! expectedModCount) throw new ConcurrentModificationException(); }modCount 用来保存修改次数每次我们调用 add、remove 或 trimToSize 等方法时它会增加expectedModCount 是迭代器的变量当我们创建迭代器时会初始化并记录当时的 modCount。后面迭代期间如果发现 modCount 和 expectedModCount 不一致就说明有人修改了集合的内容就会抛出异常。2Vectorpublic synchronized int size() { return elementCount; } public synchronized E get(int index) { if (index elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); }Vector 内部是使用 synchronized 来保证线程安全的并且都是方法级别的锁粒度比较大在并发量高的时候很容易发生竞争并发效率相对比较低。2.3.2 CopyOnWriteCopyOnWriteArrayList 基于CopyOnWrite 机制实现。当容器需要被修改的时候不直接修改当前容器而是先将当前容器进行 Copy复制出一个新的容器然后修改新的容器完成修改之后再将原容器的引用指向新的容器。这样就完成了整个修改过程。因为容器每次修改都是创建新副本所以对于旧容器来说其实是不可变的也是线程安全的无需进一步的同步操作。我们可以对 CopyOnWrite 容器进行并发的读而不需要加锁但进行并发写需要加锁。CopyOnWriteArrayList 的所有修改操作addset等都是通过创建底层数组的新副本来实现的所以 CopyOnWrite 容器也是一种读写分离的思想体现读和写使用不同的容器。2.3.4 缺点这些缺点不仅是针对 CopyOnWriteArrayList其实同样也适用于其他的 CopyOnWrite 容器内存占用问题因为 CopyOnWrite 的写时复制机制所以在进行写操作的时候内存里会同时驻扎两个对象的内存这一点会占用额外的内存空间。在元素较多或者复杂的情况下复制的开销很大复制过程不仅会占用双倍内存还需要消耗 CPU 等资源会降低整体性能。数据一致性问题由于 CopyOnWrite 容器的修改是先修改副本所以这次修改对于其他线程来说并不是实时能看到的只有在修改完之后才能体现出来。如果你希望写入的的数据马上能被其他线程看到CopyOnWrite 容器是不适用的2.3.5 适用场景读操作可以尽可能的快而写即使慢一些也没关系在很多应用场景中读操作可能会远远多于写操作。比如有些系统级别的信息往往只需要加载或者修改很少的次数但是会被系统内所有模块频繁的访问。对于这种场景我们最希望看到的就是读操作可以尽可能的快而写即使慢一些也没关系。读多写少黑名单是最典型的场景假如我们有一个搜索网站用户在这个网站的搜索框中输入关键字搜索内容但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单中黑名单并不需要实时更新可能每天晚上更新一次就可以了。当用户搜索时会检查当前关键字在不在黑名单中如果在则提示不能搜索。这种读多写少的场景也很适合使用 CopyOnWrite 集合。2.3.6 源码1add添加的时候首先上锁并复制一个新数组增加操作在新数组上完成然后将 array 指向到新数组最后解锁。public boolean add(E e) { // 加锁 final ReentrantLock lock this.lock; lock.lock(); try { // 得到原数组的长度和元素 Object[] elements getArray(); int len elements.length; // 复制出一个新数组 Object[] newElements Arrays.copyOf(elements, len 1); // 添加时将新元素添加到新数组中 newElements[len] e; // 将volatile Object[] array 的指向替换成新数组 setArray(newElements); return true; } finally { lock.unlock(); } }2getpublic E get(int index) { return get(getArray(), index); } final Object[] getArray() { return array; } private E get(Object[] a, int index) { return (E) a[index]; }3 Map3.1 HashMap3.1.1 数据结构1JDK 7 数据链表2JDK 8 数据链表红黑树当链表长度 阈值默认为8时容量 MIN_TERRIFY_CAPACITY默认为64时就会把链表转为红黑树。当节点 6 后又会恢复到链表形态。MIN_TREEIFY_CAPACITY 64指的是整个 HashMap 底层数组table的容量。为什么还要求容量 64因为如果数组本身还很小例如table.length 16 某个桶 A → B → C → D → E → F → G → H出现 8 个节点可能只是因为HashMap 容量太小。这时候 HashMap 不会急着树化而是优先进行resize 扩容16 → 32 → 64扩容以后这 8 个节点可能会被重新分散到不同的桶里链表自然就变短了。//检查是否满足条件并把链表转换为红黑树的形式默认的 TREEIFY_THRESHOLD 阈值是 8 if (binCount TREEIFY_THRESHOLD) { treeifyBin(tab, i); }为什么要引入红黑树红黑树是每个节点都带有颜色属性的二叉查找树颜色为红色或黑色。红黑树会自动平衡从而防止极端不平衡从而影响查找效率的情况发生即其左右子树高度几乎一致查找性能近似于二分查找时间复杂度是 O(log(n)) 级别而链表的时间复杂度为 O(n)远远大于红黑树的 O(log(n))尤其是在节点越来越多的情况下O(log(n)) 体现出的优势会更加明显。红黑树的一些其他特点根节点永远是黑色的红色节点不能连续也就是说红色节点的子和父都不能是红色的从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点。正是由于这些规则和要求的限制红黑树保证了较高的查找效率引入红黑树的好处就是避免在极端的情况下冲突链表变得很长查询变慢。而红黑树具有自平衡的特点即便是极端情况下也可以保证查询效率在 O(log(n))。为什么 Map 桶中超过 8 个才转为红黑树n 8 时O(n) 与 O(logn) 区别不大n 8 时O(n) 与 O(logn) 区别越来越大。为什么不一开始就采用红黑树1树节点占用的空间是普通节点的 2 倍Because TreeNodes are about twice the size of regular nodes, use them only when bins contain enough nodes to warrant use(see TREEIFY_THRESHOLD). And when they become too small (due removal or resizing) they are converted back to plain bins.单个 TreeNode 需要占用的空间大约是普通 Node 的两倍所以只有当包含足够多的 Nodes 时才会转成 TreeNodes而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后又会变回普通的链表的形式以便节省空间。2链表长度为 8 的概率很小链表长度达到 8 的概率相当低除非 hash 攻击 或 hashCode 分布不均 或 hashMap 容量过大。事实上链表长度超过 8 就转为红黑树的设计更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长从而导致查询效率低而此时转为红黑树更多的是一种保底策略用来保证极端情况下查询的效率。通常如果 hash 算法正常的话那么链表的长度也不会很长那么红黑树也不会带来明显的查询时间上的优势反而会增加空间负担。所以通常情况下并没有必要转为红黑树所以就选择了概率非常小小于千万分之一概率也就是长度为 8 的概率把长度 8 作为转化的默认阈值。如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构这时往往说明我们的哈希算法有问题需要进行改进减少冲突。3.1.2 插入元素1JDK 7 将新来的节点插到链表头public V put(K key, V value) { ... // 计算key的hash值 int hash hash(key); // 计算key在Entry数组中的位置相当于对数组长度求余 int i indexFor(hash, table.length); // 遍历该位置上的链表 for (EntryK,V e table[i]; e ! null; e e.next) { Object k; // 找到了就覆盖旧值并返回 if (e.hash hash ((k e.key) key || key.equals(k))) { V oldValue e.value; e.value value; return oldValue; } } modCount; // 没找到就添加里面有扩容代码 addEntry(hash, key, value, i); return null; } // 创建元素放在头节点 void createEntry(int hash, K key, V value, int bucketIndex) { EntryK,V e table[bucketIndex]; table[bucketIndex] new Entry(hash, key, value, e); size; }2JDK 8 将新来的节点插到链表尾//到了链表的尾部也没有发现该 key说明之前不存在就把新值添加到链表的最后 if ((e e.next) null) { pred.next new NodeK, V(hash, key,value, null); break; }为什么要改成尾插呢参考老生常谈HashMap的死循环并发环境下头插法在扩容期间会产生循环链表在执行get() 会触发死循环造成 CPU 100% 的惨案。插入第 4 个节点时发生 rehash假设现在有两个线程同时进行线程 1 和线程 2两个线程都会新建新的数组。然后开始并发执行线程 1 先被分配了时间片开始插入 abc然后时间片用完了开始执行线程 2成环后 get() 时就会陷入死循环。3.1.3 Hash 算法1JDK 1.7final int hash(Object k) { int h hashSeed; if (0 ! h k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } // 异或相同为0不同为1 h ^ k.hashCode(); // 右移 20 位右移 12 位 h ^ (h 20) ^ (h 12); // 进行了 4 次 hash 扰动 return h ^ (h 7) ^ (h 4); }2JDK1.8// 计算出来的 hash值 只可能是一个所以用 final 修饰 static final int hash(Object key) { int h; // 只进行 1 次 hash 扰动将高 16 位 和 低 16 位 进行异或 // 通过混合原始哈希码的高位和低位以此来加大低位的随机性减少碰撞 // 而且混合后的低位掺杂了高位的部分特征这样高位的信息也被变相保留下来 return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }例vin.hashCode() 1167633.1.4 扩容机制初始容量为 16。数组的大小初始化后是不可改变的因为数组需要占用地址连续的存储空间基于原数组去扩展不一定能找到紧挨着的连续空间了。1JDK 1.7扩容容量为原数组的 2 倍对 key 值重新进行 hash算出其在新数组的位置。void addEntry(int hash, K key, V value, int bucketIndex) { //1、判断当前个数是否大于等于阈值 //2、当前存放是否发生哈希碰撞 if ((size threshold) (null ! table[bucketIndex])) { //扩容扩大容量为原数组的 2 倍 resize(2 * table.length); hash (null ! key) ? hash(key) : 0; bucketIndex indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void resize(int newCapacity) { Entry[] oldTable table; int oldCapacity oldTable.length; //判断是否有超出扩容的最大值如果达到最大值则不进行扩容操作 if (oldCapacity MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return; } Entry[] newTable new Entry[newCapacity]; // transfer()方法把原数组中的值放到新数组中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); //设置 hashmap 扩容后为新的数组引用 table newTable; //设置 hashmap 扩容新的阈值 threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity newTable.length; for (EntryK,V e : table) { while(null ! e) { EntryK,V next e.next; if (rehash) { e.hash null e.key ? 0 : hash(e.key); } // 重新计算 key 的 hash 值算出其在新数组的存放位置 int i indexFor(e.hash, newCapacity); e.next newTable[i]; newTable[i] e; e next; } } }2JDK 1.8扩容容量为原数组的 2 倍对 key 的 hash 值与旧数组的长度进行按位与运算算出其在新数组的位置不需重新 hash。//将key的hash值与旧数组长度与操作 if ((e.hash oldCap) 0) { //放在原索引位置 if (loTail null) loHead e; else loTail.next e; loTail e; } else { //放在新索引位置 if (hiTail null) hiHead e; else hiTail.next e; hiTail e; }3.1.5 线程不安全先瞅瞅 put() 方法的源码看到那个 modCount 了吗其实这一行代码隐藏了三步操作每一步之间都有可能被打断读取 modCount 增加 modCount 保存 modCount假设现有 modCount 1有两个线程分别对它进行 操预期结果 modCount 3但是会出现 modCount2 的情况为毛捏看下图由此可猜测多个线程同时调用 put() 方法时有可能导致 modCount 的值计算错误。1扩容期间取到 null 值HashMap 本身默认的的容量不是很大如果不停地往 map 中添加数据它会在在合适的时间进行扩容。在扩容期间它会新建一个新的空数组并且用旧的项填充到这个新的数组中去。在填充的过程中如果有有线程去新数组中获取值很有可能会取到 null 值。2同时 put 碰撞导致数据丢失比如有两个线程同时使用 put 来添加元素且两个 key 的 hashcode 一样它们发生了碰撞并且两个线程又同时判断该位置是空的可以写入所以这两个线程的两个不同的 value 便会添加到数组的同一个位置这样最终就只会保留一个数据丢失一个数据。3可见性问题无法保证如果线程 1 给某个 key 放入了一个新值那么线程 2 在获取对应的 key 的值时它的可见性是无法保证的也就是说线程 2 可能可以看到这一次的更改但也有可能看不到。3.2 HashTableHashtable 和 HashMap 采用相同的存储机制但 Hashtable 是线程安全的其内部方法几乎都被 synchronized 修饰粒度比较大public synchronized V get(Object key) { Entry?,? tab[] table; int hash key.hashCode(); int index (hash 0x7FFFFFFF) % tab.length; for (Entry?,? e tab[index] ; e ! null ; e e.next) { if ((e.hash hash) e.key.equals(key)) { return (V)e.value; } } return null; } public synchronized int size() { return count; }Hashtable 的 size() 方法中明明只有一条语句 ”return count” 为什么还要做同步由于非同步方法可以多个线程同时访问如果其他线程正在对 hashtable 进行添加或者删除操作当已经添加或者删除后还没有对 size 进行修改这时获得的 size 值就不正确所以需要进行同步。3.3 TreeMap3.3.1 数据结构基于红黑树红黑树是自平衡二叉查找树在进行插入和删除操作时通过特定的操作能保持二叉查找树的平衡从而获得较高的查找性能。static final class EntryK,V implements Map.EntryK,V { K key; V value; EntryK,V left; EntryK,V right; EntryK,V parent; boolean color BLACK; ...... }3.3.2 TreeMap的优势3.4 LinkedHashMapHashMap第一级结构是一个数组第二级结构是一个单向链表LinkedHashMap第一级结构是一个数组第二级结构是一个双向链表Map 综述二彻头彻尾理解 LinkedHashMappublic V get(Object key) { NodeK,V e; if ((e getNode(hash(key), key)) null) return null; if (accessOrder) afterNodeAccess(e); return e.value; }3.5 ConcurrentHashMap3.5.1 数据结构1JDK 1.7每个 Segment 独立加锁采用可重入锁 ReentrantLock最大并发数就是 Segment 的个数默认为 16。Segment 的个数一旦确认初始化后不可扩容。2JDK 1.8最大并发数为数组元素的个数采用 Node CASCompare And Swap synchronized 保证线程安全。因为 synchronized 在 1.8 进行了很多优化比如自适应自旋、锁消除、锁粗化、轻量级锁、偏向锁等所以后期的 Java 版本里的 synchronized 的性能并不比 Lock 差从导致 ConcurrentHashMap 到了 Java 8 中锁粒度更细理想情况下 table 数组元素的个数也就是数组长度就是其支持并发的最大个数并发度比之前有提高。插入知识点CAS 有三个操作数 - 内存值 V预期值 A要修改的值 B。仅当预期值 A 和当前的内存值 V 相同时才将内存值修改为 Bfinal V putVal(K key, V value, boolean onlyIfAbsent) { ... //计算 hash 值 int hash spread(key.hashCode()); int binCount 0; for (NodeK, V[] tab table; ; ) { NodeK, V f; int n, i, fh; //如果数组是空的就进行初始化 if (tab null || (n tab.length) 0) { tab initTable(); } // 找该 hash 值对应的数组下标 else if ((f tabAt(tab, i (n - 1) hash)) null) { //如果该位置是空的就用 CAS 的方式放入新值 if (casTabAt(tab, i, null, new NodeK, V(hash, key, value, null))) { break; } } //hash值等于 MOVED 代表在扩容 else if ((fh f.hash) MOVED) { tab helpTransfer(tab, f); } //槽点上是有值的情况 else { V oldVal null; //用 synchronized 锁住当前槽点保证并发安全 synchronized (f) { if (tabAt(tab, i) f) { //如果是链表的形式 if (fh 0) { binCount 1; //遍历链表 for (NodeK, 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; } NodeK, V pred e; //到了链表的尾部也没有发现该 key说明之前不存在就把新值添加到链表的最后 if ((e e.next) null) { pred.next new NodeK, V(hash, key, value, null); break; } } } //如果是红黑树的形式 else if (f instanceof TreeBin) { NodeK, V p; binCount 2; //调用 putTreeVal 方法往红黑树里增加数据 if ((p ((TreeBinK, V) f).putTreeVal(hash, key, value)) ! null) { oldVal p.val; if (!onlyIfAbsent) { p.val value; } } } } } if (binCount ! 0) { //检查是否满足条件并把链表转换为红黑树的形式默认的 TREEIFY_THRESHOLD 阈值是 8 if (binCount TREEIFY_THRESHOLD) { treeifyBin(tab, i); } //putVal 的返回是添加前的旧值所以返回 oldVal if (oldVal ! null) { return oldVal; } break; } } } addCount(1L, binCount); return null; }3.5.2 size () 方法计算方式1JDK 1.7static final int RETRIES_BEFORE_LOCK 2; public int size() { final SegmentK,V[] segments this.segments; int size; boolean overflow; long sum; // sum of modCounts long last 0L; // previous sum int retries -1; // first iteration isnt retry try { // 最多循环计算 3 次 for (;;) { // if (retries RETRIES_BEFORE_LOCK) { for (int j 0; j segments.length; j) ensureSegment(j).lock(); // force creation } sum 0L; size 0; overflow false; // 将每个 segment 的 count 加起来作为整个 hashMap 的 size for (int j 0; j segments.length; j) { SegmentK,V seg segmentAt(segments, j); if (seg ! null) { sum seg.modCount; int c seg.count; if (c 0 || (size c) 0) overflow true; } } // 比较前后两次计算的结果结果一致就认为当前没有元素加入计算的结果是准确的 if (sum last) break; last sum; } } finally { if (retries RETRIES_BEFORE_LOCK) { for (int j 0; j segments.length; j) segmentAt(segments, j).unlock(); } } return overflow ? Integer.MAX_VALUE : size; }2JDK 1.8// put 和 delete 末尾都会调 addCount private final void addCount(long x, int check) { CounterCell[] as; long b, s; if ((as counterCells) ! null || !U.compareAndSwapLong(this, BASECOUNT, b baseCount, s b x)) { CounterCell a; long v; int m; boolean uncontended true; if (as null || (m as.length - 1) 0 || (a as[ThreadLocalRandom.getProbe() m]) null || !(uncontended U.compareAndSwapLong(a, CELLVALUE, v a.value, v x))) { fullAddCount(x, uncontended); return; } if (check 1) return; s sumCount(); } if (check 0) { NodeK,V[] tab, nt; int n, sc; while (s (long)(sc sizeCtl) (tab table) ! null (n tab.length) MAXIMUM_CAPACITY) { int rs resizeStamp(n); if (sc 0) { 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); s sumCount(); } } } public int size() { long n sumCount(); return ((n 0L) ? 0 : (n (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } // 推荐使用返回值是 long 类型不会因为 size 方法是 int 类型限制最大值 public long mappingCount() { long n sumCount(); return (n 0L) ? 0L : n; // ignore transient negative values } final long sumCount() { CounterCell[] as counterCells; CounterCell a; long sum baseCount; if (as ! null) { // 通过对 baseCount 和 counterCell 进行 CAS 计算最终通过 baseCount 和 遍历 CounterCell 数组得出 size for (int i 0; i as.length; i) { if ((a as[i]) ! null) sum a.value; } } return sum; }3.6 Map的适用范围4 Set4.1 HashSet//底层使用HashMap来保存HashSet中所有元素 private transient HashMapE,Object map; //定义一个虚拟的Object对象作为HashMap的value private static final Object PRESENT new Object(); //借助HashMap的put方法来添加 public boolean add(E e) { return map.put(e, PRESENT)null; } //借助HashMap的方法来查找 public boolean contains(Object o) { return map.containsKey(o); }4.2 LinkedHashSet具有 HashSet 的查找效率且内部使用双向链表维护元素的插入顺序。4.3 TreeSet基于红黑树实现支持有序性操作例如根据一个范围查找元素的操作。但是查找效率不如 HashSetHashSet 查找的时间复杂度为 O(1)TreeSet 则为 O(logN)。4.4 Set 集合如何保证元素不重复HashSet 底层使用 HashMap 来保存对象会调对象的 hash() 方法来计算对象的 hash 值对应于内存地址。若 hash 表中不存在该 hash 值则对象添加成功。若 hash 表中存在该 hash 值会调用对象的 equals 方法比较对象的 field如果 field 也相同则是重复的对象该对象添加失败。好累喝一杯香芋波波补补元气。本文学习自学堂在线-清华大学-许斌《JAVA程序设计进阶》