摘要：前置知识基础集合类基础字典该接口不基于比较继承父接口父类数据存储底层结构数组链表红黑树同双向链表红黑树复杂度插入同删除同查找同有序性迭代顺序插入顺序访问顺序自然序自定义支持否同是哈希哈希函数基于高低位同桶定位法位运算同冲突处理转换成链表红黑
前置知识: Java基础 集合类基础(jdk1.8)
Map(字典)该接口不基于Collection
HashMap/LinkedHashMap/TreeMap比较| HashMap | LinkedHashMap | TreeMap | ||
|---|---|---|---|---|
| 继承 | 父接口 | Map | Map | NavigableMap1 |
| 父类 | AbstractMap | HashMap | AbstractMap | |
| 数据存储 | 底层结构 | 数组+(链表/红黑树) | 同HashMap+双向链表 | 红黑树 |
| 复杂度 | 插入 | O(1) | 同HashMap | O(lgN) |
| 删除 | O(1) | 同HashMap | O(lgN) | |
| 查找 | O(1) | 同HashMap | O(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 | / |
| transient9 | size/modCount10; table/entrySet; | 同HashMap; head/tail8; | size/modCount; root11; | |
| 同步 | 线程安全 | 否 | 同HashMap | 否 |
| final | Entry.hash/key | 同HashMap | 无 |
该接口基于Collection
HashSet/LinkedHashSet/TreeSet比较Set实现内部使用了Map实现,所以其特性和Map对应项类似
List(列表)该接口基于Collection
ArrayList/LinkedList/Vector比较| ArrayList | LinkedList | Vector | ||
|---|---|---|---|---|
| 继承 | 父接口 | List/RandonAccess | List/Deque | List/RandonAccess |
| 父类 | AbstractList | AbstractSequentialList | AbstractList | |
| 数据存储 | 底层结构 | 数组 | 双向链表12 | 数组 |
| 复杂度 | 插入 | O(N) | O(1) | O(N) |
| 删除 | O(N) | O(1) | O(N) | |
| 查询 | O(1) | O(N) | O(1) | |
| 容量 | 初始容量 | 10 | 0 | 10 |
| 最大容量 | Integer.Max | Integer.Max | Integer.Max | |
| 扩容 | 时间点 | 插入前 | / | 插入前 |
| 策略 | 1.5倍 | / | 默认为2倍 | |
| 主要耗时点 | 拷贝数组13 | / | 拷贝数组 | |
| 同步 | 线程安全 | 无 | 无 | 是(synchronized) |
| 序列化 | 优化策略 | 跳过数组空白的尾部 | / | 无 |
| transient | elementData; | size; first/last; | 无14 |
该接口基于Collection
LinkedList/PriorityQueue/ArrayDeque比较| LinkedList | PriorityQueue | ArrayDeque | ||
|---|---|---|---|---|
| 继承 | 父接口 | List/Deque | Queue | Deque |
| 父类 | AbstractSequentialList | AbstractQueue | AbstractCollection | |
| 数据存储 | 数据结构 | 列表/双端队列 | 优先队列 | 双端队列 |
| 底层结构 | 双向链表 | 最小堆/最大堆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 |
| 最小容量 | / | 218 | 8 | |
| 时间点 | / | 插入前 | 插入后 | |
| 判断条件 | / | index >= queue.length | head==tail | |
| 策略 | / | 新容量<=64为2倍,否则为1.5倍 | 2倍 | |
| 序列化 | 优化策略 | / | 删除空白位置,但size不小于2 | 删除空白位置 |
| transient | size; first/last; | queue; modCount; | elements; head/tail; | |
| 同步 | 线程安全 | 否 | 否 | 否 |
Java 8系列之重新认识HashMap
深入理解哈希表
Java 核心技术点之集合框架
LinkedHashMap
List 总结
【集合框架】JDK1.8源码分析HashSet && LinkedHashSet（八）
JDK中优先级队列PriorityQueue实现分析
通过NavigableMap(扩展自SortedMap)接口,程序可以通过Entry之间的大小顺序,访问某个Entry相邻的Entry ↩
一共两次哈希:第一次:Object.hashCode()返回32位整数;地二次:对第一次哈希值的低位和高位做乘方运算,保证所有数字都参与计算,防止Hash聚集现象 ↩
定位元素位于哪个bucket中一般使用求模运算index = hash % length,HashMap中使用较之更快的等效位运算index = hash & (length - 1),条件是数组length必须满足2^n .受影响参数包括初始容量/最大容量/扩容策略.使用位运算的代价是:如果length为素数,HashMap不容易产生Hash冲突,但这是一个trade-off ↩
since jdk1.8,当元素过于集中在一个bucket时,由链表转成红黑树;反之由红黑树转成链表 ↩
loadFactor>0即可;负载因子越大,同样内存HashMap能容纳元素越多,Hash冲突可能性越大,各个操作的复杂度越大 ↩
插入后检测扩容比插入前要差,无法避免无谓的扩容(即之后不在put元素的场景) ↩
由于resize后各个元素的hash值可能发生变化,所以无法保证迭代器遍历的顺序,主要体现在在原数组中靠前的元素在新数组中靠后,而且如果假设hash函数是平均分布的话,该种情况出现的概率为50%(eg.元素hash=31,old_array.length=16,new_array.length=32,元素位置从15变成31).有趣的是,jdk1.8的HashMap利用了这种现象来降低resize时重新计算元素位置的开销 ↩
head/tail为双向链表的头结点和尾节点,由于使用其父类的序列化方法,因此反序列之后需要重新生成双向链表,这是在新建节点的newNode()中实现的;访问/插入/删除方法中对双向链表的操作会通过Override父类的Hook方法实现 ↩
transient修饰的变量不会被Java默认的序列化器处理,需要程序自己OverloadwriteObject()和readObject()方法 ↩
modCount记录结构变化的次数(eg.插入新元素/删除老元素) ↩
红黑树的根节点 ↩
讲道理是可以用单向链表的,但是由于该类被官方推荐来模拟Stack/Queue/Deque,因此使用了双向链表,该类能够毫不费力的兼容这些数据结构 ↩
执行拷贝数组的方法是Arrays.copy(),底层native方法是arraycopy(),对数组元素的拷贝都是浅拷贝.可以用简单的实验表明:当原数组的元素数量超过10^6 时,耗时超过1ms;当原数组元素数量超过10^7 时,耗时超过5ms ↩
由于历史原因Vector(since jdk1.0)没有对序列化做优化,数组尾部的空白片段依然会被保留,官方也推荐使用更新的集合类(since jdk1.2)来代替它 ↩
默认是二叉最小堆(默认的comparator来自于SortedSet) ↩
null元素是被删除的元素留下的空位置/还没有添加元素的空位置,是个重要的remove()判断条件,所以不能插入null元素 ↩
原因类似PriorityQueue,循环数组中中间有一段是null的,null是数组中的空位置 ↩
该最小容量是由序列化writeObject()方法保证,保证树二叉堆至少有两层 ↩
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/67279.html
摘要：整个包，按照功能可以大致划分如下锁框架原子类框架同步器框架集合框架执行器框架本系列将按上述顺序分析，分析所基于的源码为。后，根据一系列常见的多线程设计模式，设计了并发包，其中包下提供了一系列基础的锁工具，用以对等进行补充增强。 showImg(https://segmentfault.com/img/remote/1460000016012623); 本文首发于一世流云专栏：https...
摘要：而在集合中，值仅仅是一个对象罢了该对象对本身而言是无用的。将这篇文章作为集合的总结篇，但觉得没什么好写就回答一些面试题去了，找了一会面试题又觉得不够系统。 前言 声明，本文用的是jdk1.8 花了一个星期，把Java容器核心的知识过了一遍，感觉集合已经无所畏惧了！！(哈哈哈....)，现在来总结一下吧~~ 回顾目录： Collection总览 List集合就这么简单【源码剖析】 Ma...
摘要：说一说迭代器通过集合对象获取其对应的对象判断是否存在下一个元素取出该元素并将迭代器对象指向下一个元素取出元素的方式迭代器。对于使用容器者而言，具体的实现不重要，只要通过容器获取到该实现的迭代器的对象即可，也就是方法。 前言 欢迎关注微信公众号：Coder编程获取最新原创技术文章和相关免费学习资料，随时随地学习技术知识！** 本章主要介绍Collection集合相关知识，结合面试中会提到...
摘要：引用特定类型的方法特定类普通方法引用构造方法类名称引用构造方法内建函数式接口方法引用操作可能出现的函数式接口有四类有参数有返回值有参数无返回值无参数有返回值判断真假。 可变参数 在java程序中调用方法时，必须严格按照方法定义的变量进行参数传递。但是在开发过程中可能会出现一种情况：不确定要传递的参数个数。解决这个问题的思路是将多个参数封装为数组。这是一个打折扣的方法，因为数组并不代表任...
阅读 2157·2021-11-15 11:36
阅读 1479·2021-09-23 11:55
阅读 2489·2021-09-22 15:16
阅读 2030·2019-08-30 15:45
阅读 1866·2019-08-29 11:10
阅读 1029·2019-08-26 13:40
阅读 919·2019-08-26 10:44
阅读 3172·2019-08-23 14:55
