Java集合精选常见面试题( 七 ) _生活百科

LinkedList 则通过链表来实现。

ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

ArrayDeque 插入时可能存在扩容过程，不过均摊后的插入操作依然为 O(1) 。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈
说一说 PriorityQueuePriorityQueue 是在 JDK1.5 中被引入的，其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
这里列举其相关的一些要点：

PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第K大的数、带权图的遍历等，所以需要会熟练使用才行
Map 接口（重要）要求

掌握 HashMap 的基本数据结构
掌握树化、退化时机
理解索引计算方法、二次 hash 的意义、容量对索引计算的影响
掌握 put 流程、扩容、扩容因子
理解并发使用 HashMap 可能导致的问题
理解 key 的设计

HashMapHashMap 的基本数据结构

1.7：数组 + 链表

1.8：数组 + （链表 | 红黑树）

树化与退化

树化规则：当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果此时数组容量大于 64 才会进行树化

树化的意义

红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略
hash 表的查找、更新的时间复杂度是 O(1)，而红黑树的查找、更新的时间复杂度是 O(log_2?n )，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表
hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

退化规则

情况1：在扩容时会拆分树，当树元素个数小于6则会退化成链表
情况2：删除树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

索引计算索引计算方法

首先，计算对象的 hashCode()
再调用 HashMap 的 hash() 方法进行二次哈希：二次 hash() 是为了让哈希分布更为均匀
最后 & (capacity – 1) 得到索引

数组容量为何是 2 的 n 次幂

计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置，否则新位置 = 旧位置 + oldCap

注意

二次 hash 是为了配合容量是 2 的 n 次幂这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
容量是 2 的 n 次幂这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

put 与扩容put 流程

HashMap 是懒惰创建数组的，首次使用才创建数组
计算索引（桶下标）
如果桶下标还没人占用，创建 Node 占位返回
如果桶下标已经有人占用
1. 已经是 TreeNode 走红黑树的添加或更新逻辑
2. 是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
返回前检查容量是否超过阈值，一旦超过进行扩容

1.7 与 1.8 的区别