写点什么

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

用户头像
关注
发布于: 1 小时前

集合框架类图


对比分析

类分析

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

发布于: 1 小时前阅读数: 3
用户头像

关注

还未添加个人签名 2018.08.08 加入

还未添加个人简介

评论

发布
暂无评论
Java集合源码-技术本质分析