Java 集合源码 - 技术本质分析

集合框架类图

对比分析

类分析

Collection 接口

• 基本的集合操作

• default 函数：默认实现 stream、parallelSteam

AbstractList 类

实现了一些接口，这些接口实现只依赖 Collection 和 List 定义的接口

• 数据结构

• modCount，记录变更次数，多线程并发控制（fail-fast 机制）

ArrayList 类

• 数据结构：数组

• Object[] elementData

• int size，默认 10

• 特性

• 非线程安全：fast-fail 机制

• 扩容：elementData.length+ (elementData.length>> 1);

• 各种访问方式速度对比

iteratorThroughRandomAccess：3 msiteratorThroughIterator：8 msiteratorThroughFor2：5 ms

LinkedList 类

• 数据结构：双向链表

• Node<E> first：双向列表节点

• E item;

  Node<E> next;

  Node<E> prev

• Node<E> last：同上

• int size

• 各种访问方式速度对比

iteratorLinkedListThruIterator：8 msiteratorLinkedListThruForeach：3724 msiteratorThroughFor2：5 msiteratorThroughPollFirst：8 msiteratorThroughPollLast：6 msiteratorThroughRemoveFirst：2 msiteratorThroughRemoveLast：2 ms

Vector 类

• 数据结构：数组

• Object[] elementData

• int elementCount，默认 10

• int capacityIncrement，单次扩容数量，默认和当时的 elementCount 一致

• 特性

• 线程安全：synchronized 关键字

• 扩容：elementData.length+ ((capacityIncrement > 0) ? capacityIncrement : elementData.length)

• 各种访问方式速度对比

iteratorThroughRandomAccess：6 msiteratorThroughIterator：9 msiteratorThroughFor2：8 msiteratorThroughEnumeration：7 ms

Stack 类

继承 Vector，新增了几个关于栈结构的方法，其他和 Vector 一样

TreeMap 类

• 数据结构

• Comparator<? super K> comparator

• Entry<K,V> root：红黑树节点

• K key

• V value

• Entry<K,V> left

  Entry<K,V> right

  Entry<K,V> parent

  boolean color = BLACK

• int size

• int modCount

• 特性

• key 不允许为 null

• 节点通过 key 组织成红黑树结构

• 非线程安全，fast-fail 机制

• 所有基于 key 的查找比较，都是红黑树算法

HashMap 类

• 数据结构：数组+链表

• Node<K,V>[] table;

• final int hash;

  final K key;

  V value;

  Node<K,V> next;

• Set<Map.Entry<K,V>> entrySet;

• int size，默认是 16

• int modCount;

• int threshold;

• final float loadFactor，默认是 0.75，超过装载因子会扩容

• 特性

• hashcode 算法：

• hash 位置：key.hashCode() ^ (key.hashCode() >>> 16)

• 元素位置：(table.length - 1) & hash 位置

HashTable 类

• 数据结构：数组+链表

• Entry<?,?>[] table

• final int hash

  final K key

  V value

  Entry<K,V> next

• int count，默认是 11

• int threshold

• float loadFactor，默认是 0.75

• int modCount = 0

• 特性

• hashcode 算法：(key.hashCode() & 0x7FFFFFFF) % tab.length

• 线程安全：synchronized

WeakHashMap 类

• 数据结构

• Entry<K,V>[] table

• V value

  final int hash

  Entry<K,V> next

  int size

  int threshold

  final float loadFactor

  final ReferenceQueue<Object> queue

  int modCount

• 特性

• 非线程安全：fast-fail

• hashcode 算法：没看明白

• 弱键原理：通过 WeakReference 和 ReferenceQueue 实现，WeakHashMap 的 key 是“弱键”，即是 WeakReference 类型的；ReferenceQueue 是一个队列，它会保存被 GC 回收的“弱键”；

这个也不是很明白，有机会再深入研究下

• 不支持序列化

HashSet 类

• 数据结构

• HashMap<E,Object> map，map 的 key 就是 hashset 中的元素

• 特性

• 集合里面的元素都不重复，判重依据：hashcode、equals

• 非线程安全，fast-fail 机制

TreeSet 类

• 数据结构

• NavigableMap<E,Object> m，接口类，具体实现是 TreeMap

• 特性

• 非线程安全

• 集合中元素都不重复

• 基于 TreeMap 红黑树实现有序结构，查询复杂度 lg(n)

附录

《Java 集合系列目录》

https://www.cnblogs.com/skywang12345/p/3323085.html

《Java 中 Serializable 和 Externalizable 接口浅析》

https://blog.csdn.net/qq_32252957/article/details/82856128