jdk1.8集合类特性综述和对比

摘要

jdk1.8集合类特性和性能对比

Map(字典)

该接口基于Collection

HashMap/LinkedHashMap/TreeMap比较



HashMapLinkedHashMapTreeMap
继承父接口MapMapNavigableMap1

父类AbstractMapHashMapAbstractMap
数据存储底层结构数组+(链表/红黑树)同HashMap+双向链表红黑树
复杂度插入O(1)同HashMapO(lgN)

删除O(1)同HashMapO(lgN)

查找O(1)同HashMapO(lgN)
有序性迭代顺序/插入顺序/访问顺序自然序/自定义

支持Navigate同HashMap
哈希哈希函数基于HashCode()高/低位2同HashMap/

桶定位法位运算3同HashMap/

冲突处理转换成链表/红黑树4同HashMap/
扩容机制初始容量163同HashMap/

最大容量1 << 30(2^31 )同HashMap/

负载因子0.755同HashMap/

扩容策略2倍3同HashMap/

扩容时机插入后6同HashMap/

具体操作在新数组中重排所有元素同HashMap/

保持迭代顺序7同HashMap/
序列化典型优化跳过数组null位置同HashMap8/

transient9size/modCount10; table/entrySet;同HashMap; head/tail8;size/modCount; root11;
同步线程安全同HashMap

finalEntry.hash/key同HashMap

Set(集合)

该接口基于Collection

HashSet/LinkedHashSet/TreeSet比较

Set实现内部使用了Map实现,所以其特性和Map对应项类似

List(列表)

该接口基于Collection

ArrayList/LinkedList/Vector比较



ArrayListLinkedListVector
继承父接口List/RandonAccessList/DequeList/RandonAccess

父类AbstractListAbstractSequentialListAbstractList
数据存储底层结构数组双向链表12数组
复杂度插入O(N)O(1)O(N)

删除O(N)O(1)O(N)

查询O(1)O(N)O(1)
容量初始容量10010

最大容量Integer.MaxInteger.MaxInteger.Max
扩容时间点插入前/插入前

策略1.5倍/默认为2倍

主要耗时点拷贝数组13/拷贝数组
同步线程安全是(synchronized)
序列化优化策略跳过数组空白的尾部/

transientelementData;size; first/last;14

Queue/Deque(队列/双端队列)

该接口基于Collection

LinkedList/PriorityQueue/ArrayDeque比较



LinkedListPriorityQueueArrayDeque
继承父接口List/DequeQueueDeque

父类AbstractSequentialListAbstractQueueAbstractCollection
数据存储数据结构列表/双端队列优先队列双端队列

底层结构双向链表最小堆/最大堆15(数组)循环数组
Usage插入null元素支持不支持16不支持17
有序性出队有序性/自然序/自定义/

迭代有序性//
复杂度插入O(1)O(lgN)O(N)

删除O(1)O(lgN)O(N)

查询O(N)O(lgN)O(1)

入队O(1)O(lgN)O(1)

出队O(1)O(lgN)O(1)
扩容初始容量/11(1+2+4+4)8

最小容量/2188

时间点/插入前插入后

判断条件/index >= queue.lengthhead==tail

策略/新容量<=64为2倍,否则为1.5倍2倍
序列化优化策略/删除空白位置,但size不小于2删除空白位置

transientsize; first/last;queue; modCount;elements; head/tail;
同步线程安全

Reference

  1. Java 8系列之重新认识HashMap

  2. 深入理解哈希表

  3. Java 核心技术点之集合框架

  4. LinkedHashMap

  5. List 总结

  6. 【集合框架】JDK1.8源码分析HashSet && LinkedHashSet(八)

  7. JDK中优先级队列PriorityQueue实现分析


  1. 通过NavigableMap(扩展自SortedMap)接口,程序可以通过Entry之间的大小顺序,访问某个Entry相邻的Entry 

  2. 一共两次哈希:第一次:Object.hashCode()返回32位整数;地二次:对第一次哈希值的低位和高位做乘方运算,保证所有数字都参与计算,防止Hash聚集现象 

  3. 定位元素位于哪个bucket中一般使用求模运算index = hash % length,HashMap中使用较之更快的等效位运算index = hash & (length - 1),条件是数组length必须满足2^n .受影响参数包括初始容量/最大容量/扩容策略.使用位运算的代价是:如果length为素数,HashMap不容易产生Hash冲突,但这是一个trade-off 

  4. since jdk1.8,当元素过于集中在一个bucket时,由链表转成红黑树;反之由红黑树转成链表 

  5. loadFactor>0即可;负载因子越大,同样内存HashMap能容纳元素越多,Hash冲突可能性越大,各个操作的复杂度越大 

  6. 插入后检测扩容比插入前要差,无法避免无谓的扩容(即之后不在put元素的场景) 

  7. 由于resize后各个元素的hash值可能发生变化,所以无法保证迭代器遍历的顺序,主要体现在在原数组中靠前的元素在新数组中靠后,而且如果假设hash函数是平均分布的话,该种情况出现的概率为50%(eg.元素hash=31,old_array.length=16,new_array.length=32,元素位置从15变成31).有趣的是,jdk1.8的HashMap利用了这种现象来降低resize时重新计算元素位置的开销 

  8. head/tail为双向链表的头结点和尾节点,由于使用其父类的序列化方法,因此反序列之后需要重新生成双向链表,这是在新建节点的newNode()中实现的;访问/插入/删除方法中对双向链表的操作会通过Override父类的Hook方法实现 

  9. transient修饰的变量不会被Java默认的序列化器处理,需要程序自己OverloadwriteObject()readObject()方法 

  10. modCount记录结构变化的次数(eg.插入新元素/删除老元素) 

  11. 红黑树的根节点 

  12. 讲道理是可以用单向链表的,但是由于该类被官方推荐来模拟Stack/Queue/Deque,因此使用了双向链表,该类能够毫不费力的兼容这些数据结构 

  13. 执行拷贝数组的方法是Arrays.copy(),底层native方法是arraycopy(),对数组元素的拷贝都是浅拷贝.可以用简单的实验表明:当原数组的元素数量超过10^6 时,耗时超过1ms;当原数组元素数量超过10^7 时,耗时超过5ms 

  14. 由于历史原因Vector(since jdk1.0)没有对序列化做优化,数组尾部的空白片段依然会被保留,官方也推荐使用更新的集合类(since jdk1.2)来代替它 

  15. 默认是二叉最小堆(默认的comparator来自于SortedSet

  16. null元素是被删除的元素留下的空位置/还没有添加元素的空位置,是个重要的remove()判断条件,所以不能插入null元素 

  17. 原因类似PriorityQueue,循环数组中中间有一段是null的,null是数组中的空位置 

  18. 该最小容量是由序列化writeObject()方法保证,保证树二叉堆至少有两层 


IT家园
IT家园

网友最新评论 (0)

发表我的评论
取消评论
表情