集合

集合

Collection

List有序，可重复

ArrayList

和LinkedList相比，它的查找和访问元素的速度较快，但新增，删除的速度较慢。

特点：ArrayList底层是用数组实现的存储，查询效率高，增删效率低，线程不安全。使用频率很高

初始化大小

扩容

新增

在这之前他会有一步校验长度的判断ensureCapacityInternal，就是说如果长度不够，是需要扩容的

在扩容的时候，老版本的jdk和8以后的版本是有区别的，8之后的效率更高了，采用了位运算，右移一位，其实就是除以2这个操作。

删除

删除其实跟新增是一样的，不过叫是叫删除，但是在代码里面我们发现，他还是在copy一个数组。

线程不安全

Vector 已废弃

Collections.synchronizedList

juc 包下的CopyOnWriteArrayList

ArrayList不适合做队列，数组适合用来做队列

遍历

论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

LinkedList

底层是双向链表，只能从头开始逐个遍历

Vector

List 的实现方式有 LinkedList 和 ArrayList 两种，那面试时最常问的就是这两个数据结构如何选择。

一是考虑数据结构是否能完成需要的功能；如果都能完成，二是考虑哪种更高效。

Vector 和 ArrayList 的区别是什么

线程安全

默认情况下它是扩容两倍。

Set无序，不重复

HashSet

采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

LinkedHashSet

HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

SortedSet

TreeSet

采用红黑树结构，特点是可以有序，可以用自然排序或者自定义比较器来排序；缺点就是查询速度没有 HashSet 快。

Queue队列，先进先出

实现「普通队列 - 先进先出」的语义

Deque

ArrayDeque

实现「普通队列 - 先进先出」和栈 的语义

PriorityQueue（特殊，heap）

实现「优先队列」的语义

基本API

如何选择用 LinkedList 还是 ArrayDeque 呢？

总结来说就是推荐使用 ArrayDeque，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）。

那 ArrayDeque 和 LinkedList 的区别有哪些呢？

ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；ArrayDeque 在内存使用方面更高效。所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！

Map

HashMap与 HashSet 对应，也是无序的，O(1)。

我们都知道数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就是”帅丙“和”丙帅“我们都去hash有一定的概率会一样，就像上面的情况我再次哈希”丙帅“极端情况也会hash到一个值上，那就形成了链表。

每一个节点都会保存自身的hash、key、value、以及下个节点

新的Entry节点在插入链表的时候，插入方式

jdk 8之前是头插法

同一位置上新元素总会被放在链表的头部位置，会改变链表的上的顺序。在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。会造成无限循环的问题

jdk8之后是尾插法

在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

扩容机制数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。

因素

Capacity：HashMap当前长度。LoadFactor：负载因子，默认值0.75f。

分为两步扩容：创建一个新的Entry空数组，长度是原数组的2倍。ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组

为什么要重新哈希？因为长度扩大以后，Hash的规则也随之改变。Hash的公式---> index = HashCode（Key） & （Length - 1）

初始化大小为16

为了位运算的方便，位与运算比算数计算的效率高了很多

实现均匀分布。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

链表有红黑树

二叉树

1.左子树上所有结点的值均小于或等于它的根结点的值。2.右子树上所有结点的值均大于或等于它的根结点的值。3.左、右子树也分别为二叉排序树。

当二叉树多次插入新的节点，导致的不平衡，红黑树应用而生。

1.节点是红色或黑色。2.根节点是黑色。3.每个叶子节点都是黑色的空节点（NIL节点）。4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

如何保证红黑树始终是红黑树

变色

旋转

为啥我们重写equals方法的时候需要重写hashCode方法呢？

在java中，所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样对于值对象，==比较的是两个对象的值对于引用对象，比较的是两个对象的地址

大家是否还记得我说的HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在一个链表上的。我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还是”丙帅“呢？equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

线程不安全，线程安全需使用

HashTable

适合在多线程的情况下使用，但是效率可不太乐观。对数据操作的时候都会上锁，所以效率比较低下。

CurrentHashMap

Collections.synchronizedMap(Map)

两个构造器如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象

Hashtable 跟HashMap不一样

Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。

Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据。

实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。

初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。

扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。

迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。

总结：当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。

快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。Tip：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

LinkedHashMap这是一个「HashMap + 双向链表」的结构，落脚点是 HashMap，所以既拥有 HashMap 的所有特性还能有顺序。

TreeMap是有序的，本质是用二叉搜索树来实现的。

ConcurrentHashMap

是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

HashEntry跟HashMap差不多的，但是不同点是，使用volatile去修饰了他的数据Value还有下一个节点next。

保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（实现可见性）禁止进行指令重排序。（实现有序性）volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性

并发度高的原因

jdk1.7ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

jdk1.8其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）

jdk1.8 put操作

CAS

CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。

ABA 问题

一个线程把值改回了B，又来了一个线程把值又改回了A，对于这个时候判断的线程，就发现他的值还是A，所以他就不知道这个值到底有没有被人改过

(1) 版本号去保证就好了，就比如说，我在修改前去查询他原来的值的时候再带一个版本号，每次判断就连值和版本号一起判断，判断成功就给版本号加1。(2) 时间戳也可以，查询的时候把时间戳一起查出来，对的上才修改并且更新值的时候一起修改更新时间

synchronized性能可不咋地，为啥jdk1.8升级之后反而多了synchronized？

synchronized之前一直都是重量级的锁，但是后来官方是对他进行过升级的，他现在采用的是锁升级的方式去做的。针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁

Jdk1.8 get 操作

根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。如果是红黑树那就按照树的方式获取值。就不满足那就按照链表的方式遍历获取值。

学习目标

明确每个接口和类的对应关系；对每个接口和类，熟悉常用的 API；对不同的场景，能够选择合适的数据结构并分析优缺点；学习源码的设计，面试要会答啊。