基础八股知识
Collection
List-----有序可重复列表
Set------不可重复链表
Queue/Deque
BlockQueue
Map
HashMap
ConcrrrntHashMap
TreeMap,LinkedHashMap,HashTable
Iterator迭代器
面试八股真题
1、简述ArrayList和LinkedList的区别
2、HashMap和HashTable的区别
3、Collection包结构，与Collections的区别
4、有没有可能两个不相等的对象有相同的hashcode
5、说说List,Set,Map三者的区别？
6、HashMap 中的 key 我们可以使用任何类作为 key 吗？
7、HashMap 的长度为什么是 2 的 N 次方呢？
8、HashMap 与 ConcurrentHashMap 的异同
9、红黑树有哪几个特征？
1.1 List——有序可重复列表
1.底层是由数组实现的，重要的成员有元素数组/数组中元素数size/modeCount修改子树
2.进行add添加时，若没有指定添加位置，就会根据size确定添加的新元素在数组中的下标进行添加，若size>=数组长度，则需要扩容
3.在进行扩容时，会将 modCount++，并且会将原数组中的元素，拷贝至新数组中，新数组的大小是原数组的 1.5 倍，默认的初始容量是 0，且在第一次添加元素时，设置数组大小为 10
4. 若指定 i 为添加元素的位置，会调用 System.ArrayCopy 方法对 i 下标以后的元素进行拷贝，拷贝完成后再把添加的元素放在 i 位置
5.调用 get 方法时，由于ArrayList 底层基于数组，因此实现了一个 RandomAccess 标识接口，表示按下标读取数据速度很快，主要是由于数组在内存中是连续存储，可以通过第一个元素的存储地址和偏移量offset直接计算得到访问的元素的存储地址
5. 若 contains 方法是通过元素的值进行查找，则需要遍历数组
LinkedList是基于链表存储的，链表中结点Node主要包含存储的元素的引用E，指向前驱节点指针prev和指向后继结点的指针next,LinkedList中重要成员主要有size/头结点，first/尾结点last
LinkedList 由于 Node 在内存中是分散存储的，因此没有对 size 限制，在执行 add 方法时，默认添加在链表的尾部
若指定添加元素在链表中的位置，LinkedList 需要调用 node 方法，传入参数 Index 找到对应的节点，在查找对应的节点时，若 Index < size / 2，从头节点向后遍历，若 Index > size / 2，从尾节点向前遍历，因此即使添加元素只需要改变节点的指针，但查找添加的位置的耗时仍然不小，开销不比 ArrayList 少
调用 get 方法时，若按下标查找，也需要进行同样的遍历，性能比 ArrayList 差很多，按 contains 进行查找时，也需要进行遍历，与 ArrayList 相比半斤八两
链表节点除了元素值，还需要维护两个指针，导致 LinkedList 存储的内存开销远大于 ArrayList
Vector 也是基于数组进行存储，其原理与 ArrayList 类似，区别在于，Vector 中会维护一个 CapacityIncrement变量，每一次进行扩容时，只增加一个 CapacityIncrement 变量的大小，若没有指定 CapacityInc，默认为 0，且在扩容时，若 CapacityInc 为 0，则将数组大小翻倍；
Vector 中的所有增删改查方法，包括 get 方法，都通过在方法上加 Sychronized 锁方式锁住 Vector 对象，实现线程安全，性能较差。
1.2 Set——不可重复列表
HashSet
内部有一个成员变量的 HashMap，实际上就是使用的 HashMap 的方法
TreeSet
内部有一个成员变量的 TreeMap，底层就是 TreeMap
LinkedHashSet
底层调用的 HashSet 的方法，HashSet 中的 HashMap 也可以是 LinkedHashMap，因此实际是由 LinkedHashMap 实现
1.3 Queue / Dequeue
LinkedList 实现 Queue 和 Deque
LinkedList 中使用 first 和 last 两个节点的指针用来标记链表的头/尾节点，根据源码，pop应该返回first节点，pop和poll对返回节点为空处理不同，poll直接返回null，pop抛出异常
ArrayDeque
数组的方式实现了双端队列，主要是使用 head 和 tail 两个指针来标记 队列头/栈底 和 队列尾/栈顶
PriorityQueue
① 使用数组的方式实现了优先队列，内部其实是一个二叉堆结构（小顶堆），原理逻辑与堆排序一致
② 重要属性有 size，用来标记数组中元素的个数，即新添加的元素的下标
③ 执行 offer 方法时，先确认 size 是否大于等于数组长度，若大于等于则进行扩容，执行 siftup 方法
④ siftup 方法中，若制定了 Comparator，按照 Comparator 的 compare 方法与父节点比较，也就是 (size - 1) >>> 1 下标对应的元素进行堆的插入，若没有指定，按元素实现的 Comparable 接口的 compareTo 方法进行比较
⑤ 执行 poll() 方法时，若 size 为 0，返回空值，否则返回数组中下标为 0 的堆顶元素，将数组下标 0 位置替换为 size - 1 位置的元素，并减小 size，调用 siftdown 方法整理堆
⑥ siftdown 方法同样也分为根据 Comparator 和 Comparable 两种比较，主要是对 0 位置新换上来的元素与子节点进行比较，将其与最大的并大于 0 位置的子节点进行交换，并循环直到将其放到合适的位置
BlockQueue——阻塞队列，详见并发
2 MAP
2.1 HashMap
重要成员变量
① 负载因子：默认为 0.75，表示 HashMap 存储的元素数到达 HashMap 散列数组长度的 0.75 时就进行扩容
负载因子越大，散列数组的内存利用率越高，但哈希冲突概率也越高，查询效率相对降低；
负载因子越小，散列数组的内存利用率越低，但哈希冲突概率越低，查询效率相对较高
② 散列数组：HashMap 通过分离链表法解决哈希冲突的问题，在散列数组中存储的就是链表中的一个个头节点
③ K-V 键值对：K-V 键值对以 Node 节点的方式进行存储，Node 继承自 Map.Entry，包含 Next 指针，Key，Value 和 hash
④ threshold 门限，就是 负载因子 * 数组容量
⑤ size：HashMap 中当前存储的节点数
put方法流程：
① 再哈希：首先通过key获取到hashCode值，再对hashCode值右移16位，最后再与原hashCode值做异或运算。
#目的：在对散列数组长度取余时，高位通常不参与运算，再哈希让高位参与哈希运算，让低位尽量不同，使哈希分布更均匀
② 检查散列数组是否为空，若为空，初始化散列数组，数组容量将会初始化为16
③ 若 Key 的 HashCode 对应的散列数组位置上节点为空，则直接将新节点加入
④ 若不为空，比较链表的头节点 Key 与 put Key 是否相等，先比较 hashcode，再比较（== || equals），若相等，进行更新，若不相等，顺着链表按同样的逻辑进行比较
⑤ 若是 1.8 的HashMap，会先判断链表的头节点是否是 TreeNode，若是，则按照红黑树的逻辑进行插入
⑥ 1.7 的 HashMap 中，若遍历完链表仍未找到 Key 相同的节点，则将新节点加入到链表头，会造成并发扩容的死链问题，1.8 中，将头插法改为了尾插法，解决了死链问题，但并发环境下的其他基本问题，如更新丢失等，仍然没有解决
⑦ 若添加后 size >= threshold，就会进行扩容
扩容流程
① 首先 HashMap 的初始容量是 16，并且每次对原数组长度 * 2 进行扩容，当 size > threshold 时就会进行扩容
② 创建新的散列数组，并将旧的散列数组中的链表的头节点拷贝至新数组中，在移动时，节点的 hash 与 oldCap进行 & 运算，若结果为 0，表示在新数组中位置不变，若不为 0，表示在新数组中位置为 i + oldCap
③ 在移动节点时，会使用一个 loHead/loTail 和 hiHead/hiTail 分别指向新数组中位置 i 和 i + oldCap 的链表的头尾节点，用一个 next 指针指向当前正在移动节点的下一个节点，在 1.8 中，由于使用尾插法，每一次移动节点都会添加至 loTail/hiTail之后，不会发生死链问题，而在 1.7 中，由于使用头插法，每一次移动节点都会添加至 head 之前，会发生扩容死链问题
④ 1.7 扩容死链问题：t1 线程正在移动 A 节点，next 节点指向 A 节点的下一个节点 B，即 A -> B，此时 t2 线程完成了 A 和 B 的移动，此时 B.next = A，在 t1 移动 A 到新数组中后，当前正在移动节点 e 指向 B，next 指向 B.next = A，此时就形成了链表中的环，最终导致程序崩溃
1.8 红黑树
① 与AVL树比较
增删性能，红黑树较好； AVL 树通过节点的左右子树高度差是否大于 1 判断是否平衡，若不平衡，需要通过单/双旋转恢复平衡，而红黑树主要根据节点颜色和节点到子孙节点路径上黑节点数量判断平衡，可以通过改变节点颜色或者旋转恢复平衡，开销较小
查询性能，AVL 树较好；AVL 树的最大高度为 1.44 * log(N + 2)，一般情况只比 log(N) 稍大，红黑树由于平衡判断更加宽松，由着色法则得到的最大高度为 2 * log(N + 1)，因此性能会稍微差于 AVL 树
内存空间消耗，红黑树稍大；
为什么不用跳表； ① 跳表的实现更加灵活简单，并且在范围查找上非常方便，Redis 中 ZSet 就使用跳表 + 散列的结构 ② 红黑树在空间复杂度上更胜一筹，通常发生了红黑树化的情况，都是数据量非常非常大时，此时红黑树空间占用小的优点将更加明显，并且 HashMap 的元素本身是无序的，即用不到跳表范围查找的优势
② 特点
每个节点不是黑色就是红色，根节点是黑色
红色节点的子节点必须是黑色
从一个节点到每一个子孙节点的路径上的黑色节点数必须相同
③ HashMap 中什么时候树化/树退化
当链表长度达到 8 时进行树化；在 HashMap 源码注解中有解释为什么是 8，大概意思是，红黑树的节点大小大约是正常节点大小的两倍，并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记，在理想情况下，使用 0.75 作为负载因子，采用随机哈希算法，树化阈值与树化概率遵循泊松分布，选择 8 的概率是千万分之 6，7 的概率约是十万分之 1
当扩容后链表长度小于等于 6 进行树的退化；红黑树的节点大小大约是正常节点大小的两倍，并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记，并且在插入和删除时维护红黑树的平衡性需要额外的开销
2.2 ConcurrentHashMap
1.7之前
① 通过分段锁 Segment 保证线程安全，Segment 继承自 ReentrantLock，每一个 Segment 中都包含一个 volatile 的 HashEntry 数组，一个 volatile 的 count 表示当前 Segment 中存储的 K-V 节点数，一个 Threshold 表示扩容阈值
② HashEntry 是基本存储单位，与 HashMap 中的Entry 基本一样，包含 Key，Value，next，hash，区别在于 HashEntry 的 Value 是 volatile 的，因此对 value 的修改对所有线程可见，并且 next 指针是 final 修饰，防止扩容时发生死链
③ ConcurrentHashMap 默认有一个长度为 16 的 Segment 数组，在进行增删改查时，会根据 Key 对 16 取余得到具体处于哪个 Segment，对于 get 操作不加锁执行，对于 put 等修改操作，调用 Segment 的 lock 方法锁住当前段进行修改，不影响其他段的并发操作，在进行扩容时，也仅是对单个 Segment 进行扩容
1.8
④ 1.8 的 ConcurrentHashMap 摒弃了 Segment，采用 CAS 和类似于分段锁的方式保证线程安全；
⑤ 大体结构与 HashMap 一样，在 put 操作时，若 Node 数组对应下标处为空，使用 CAS 的方式不加锁添加节点，若数组中当前位置链表头节点不为空，则对链表头节点加锁，在 Sychronized 同步代码块中执行与 HashMap 同样的逻辑；
⑥ ConcurrentHashMap 在扩容时的移动原数组节点到新数组的操作，可以由多个线程并发完成，从而大大提高效率，在进行移动时，会将当前线程正在移动的头节点包装为一个 ForwardNode，用来标识当前位置正在移动，当其他线程遍历到数组中的 ForwardNode节点时，就会忽略并继续遍历，从而保证线程安全，并且在扩容时，仍然可以执行增删改查操作，这些操作通过头节点的 hash 判断是否是一个 ForwardNode 节点，若是，则调用 helpTransfer 方法，并发的帮助完成扩容动作，完成后再回到循环中执行 put；
⑦ get 方法也是通过 Unsafe 的 getObjectVolatile 进行读取，不加锁
2.3 TreeMap
底层是红黑树，不展开讲解
2.4 LinkedHashMap
采用 HashMap 来存储节点，用一个双向链表存储 HashMap 的 Node 节点使其有序
2.5 HashTable
使用 Sychronized 锁住方法来保证线程安全，并且默认初始容量为 11，每一次扩容为 oldCap * 2 + 1
② Iterator 接口中主要包含三个基本方法，hasNext 判断是否还有下一个元素，next 表示遍历获取下一个元素，remove 表示删除元素；
③ 常见的三种遍历方式
fori，foreach，Iterator
其中 fori 只能用于知道集合中具体元素数量时，fori 和 foreach 只能用于知道集合中元素具体类型时，foreach 底层就是 Iterator 的方式遍历
④ 三种遍历方式的删除
fori：在 fori 进行删除时，问题在于删除当前下标会导致之后的元素前移，比如 “A，B，B，C，C”，在 fori 中判断若元素等于 B 就删除，则会导致 i = 1 时，进行删除后，i = 2 位置的 B 到达 1 的位置，即 “A，B，C，C”，而此时 i 已经到达 2 的位置，即 i 指向 C，从而造成漏删，可以通过删除后让 i - 1，或者反向遍历删除解决
foreach：对于 ArrayList 等迭代器是 fail-fast 的集合，在遍历时底层是使用迭代器进行遍历，但在删除元素时，由于没有显式的获取迭代器，因此调用的是 List 的 remove 方***触发迭代器的 fail-fast 机制，抛出异常中断程序
Iterator：没有任何问题
⑤ fail-fast：
迭代器实现了 fail-fast 机制的集合，在集合中都会维护一个 modCount 成员变量，用来表示对集合的修改次数，在获取迭代器时，在迭代器中会为一个 ExpectedModCount 变量赋值为当前的 modCount，在执行 next，remove，hasnext方法之前，会先对迭代器的 ExpectedModCount 与集合的 modCount 进行比较，若不相等直接抛出异常
⑥ fail-safe：
Java 中实现 fail-safe 迭代器的集合主要都是通过 Copy-On-Write 方法实现的，例如 CopyOnWriteList，其内部有一个 ReentrantLock 锁对象，在进行增删改操作时，先加锁，将原有的数组拷贝一份，在新的数组上进行修改，而获取迭代器时，会用一个 final 变量指向当前的数组，在旧的数组上进行遍历
二、面试八股真题🎈🎈🎈
1、简述ArrayList和LinkedList的区别
① Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。
Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据, (因为删除数据以后, 需要把后面所有的数据前移)
缺点: 数组初始化必须指定初始化的长度, 否则报错
例如
1
2
3
int[] a = new int[4]; //推荐使用int[] 这种方式进行初始化
int c[] = {12,34,56,78}; //长度：4，索引范围：[0,3]
② List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承Collection。List有两个重要的实现类：ArrayList 和 LinkedList
ArrayList: 可以看作是能够自动增长容量的数组
ArrayList的toArray方法返回一个数组
ArrayList的asList方法返回一个列表
ArrayList底层的实现是Array, 数组扩容实现
LinkedList 是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于 ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。
③ 区别
ArrayList
优点：ArrayList 是实现了基于动态数组的数据结构，因为地址连续，一旦数据存储好了，查询 操作效率会比较高（在内存里是连着放的）。
缺点：因为地址连续，ArrayList 要移动数据，所以插入和删除操作效率比较低。
LinkedList
优点：LinkedList 基于链表的数据结构，地址是任意的，所以在开辟内存空间的时候不需要等 一个连续的地址。对于新增和删除操作，LinkedList 比较占优势。LinkedList 适用于要头尾操 作或插入指定位置的场景。
缺点：因为 LinkedList 要移动指针，所以查询操作性能比较低。
④ 适用场景分析：
当需要对数据进行对随机访问的时候，选用 ArrayList。
当需要对数据进行多次增加删除修改时，采用 LinkedList。
2、HashMap和HashTable的区别
① 两者父类不同
HashMap是继承自AbstractMap类，
Hashtable是继承自Dictionary类。
不过它们都实现了同时 实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。
② 对外提供的接口不同
Hashtable比HashMap多提供了elments() 和contains() 两个方法。
elments() 方法继承自ashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。
③ 对null的支持不同
Hashtable：key和value都不能为null。
HashMap：key可以为null，但是这样的key只能有一个，因为必须保证key的唯一性；可以有多个key值对应的value为null。
④ 安全性不同
HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题，因此需要开发人员自 己处理多线程的安全问题。
Hashtable是线程安全的，它的每个方法上都有synchronized 关键字，因此可直接用于多线程中。
虽然HashMap是线程不安全的，但是它的效率远远高于Hashtable，这样设计是合理的，因为大部 分的使用场景都是单线程。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。
ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。
⑤ 初始容量大小和每次扩充容量大小不同
⑥ 计算hash值的方法不同
3、Collection包结构，与Collections的区别
Collection是集合类的上级接口，子接口有 Set、List、LinkedList、ArrayList、Vector、Stack、 Set；
Collections是集合类的一个帮助类， 它包含有各种有关集合操作的静态多态方法，用于实现对各种 集合的搜索、排序、线程安全化等操作。此类不能实例化，就像一个工具类，服务于Java的 Collection框架。
4、有没有可能两个不相等的对象有相同的hashcode
有可能
在产生hash冲突时,两个不相等的对象就会有相同的 hashcode 值.当hash冲突产生时,一般 有以下几种方式来处理：
拉链法：每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链
表，被分配到同一个索引上的多个节点可以用这个单向链表进行存储。
开放定址法：一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总 能找到,并将记录存入 List iniData = new ArrayList<>()
再哈希：又叫双哈希法,有多个不同的Hash函数.当发生冲突时,使用第二个,第三个….等哈希函数 计算地址,直到无冲突。
5、说说List,Set,Map三者的区别？
List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序 的对象
Set(注重独一无二的性质)： 不允许重复的集合。不会有多个元素引用相同的对象。
Map(用Key来搜索的专家)： 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引 用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。
6、HashMap 中的 key 我们可以使用任何类作为 key 吗？
平时可能大家使用的最多的就是使用 String 作为 HashMap 的 key，但是现在我们想使用某个自定 义类作为 HashMap 的 key，那就需要注意以下几点：
如果类重写了 equals 方法，它也应该重写 hashCode 方法。
类的所有实例需要遵循与 equals 和 hashCode 相关的规则。
如果一个类没有使用 equals，你不应该在 hashCode 中使用它。
咱们自定义 key 类的最佳实践是使之为不可变的，这样，hashCode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode 和 equals 在未来不会改变，这样就会解决与 可变相关的问题了。
7、HashMap 的长度为什么是 2 的 N 次方呢？
为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现
取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说 hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进 制位操作 & ，相对于 % 能够提高运算效率。
8、HashMap 与 ConcurrentHashMap 的异同
① 都是 key-value 形式的存储数据；
② HashMap 是线程不安全的，ConcurrentHashMap 是 JUC 下的线程安全的；
③ HashMap 底层数据结构是数组 + 链表（JDK 1.8 之前）。JDK 1.8 之后是数组 + 链表 + 红黑 树。当链表中元素个数达到 8 的时候，链表的查询速度不如红黑树快，链表会转为红黑树，红 黑树查询速度快；
④ HashMap 初始数组大小为 16（默认），当出现扩容的时候，以 0.75 * 数组大小的方式进行扩 容；
⑤ ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry， Segment 数组大小默认是 16，2 的 n 次方；JDK 1.8 之后，采用 Node + CAS + Synchronized 来保证并发安全进行实现。
9、红黑树有哪几个特征？
每个节点都是黑色或者红色
根节点是黑色
每个叶子节点都是黑色（指向空的叶子节点）
如果一个叶子节点是红色，那么其子节点必须都是黑色的
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点