注意：所有文章除特别说明外，转载请注明出处.
Java集合框架 - 面试
[TOC]
数据结构与算法 - 考试
1.数据结构
1.数组和链表的区别
2.链表的操作：翻转、链表环路检测、双向链表、循环链表等相关操作
3.队列和栈的应用
4.二叉树的遍历方式及其递归和非递归的实现
5.红黑树的旋转（难）
2.算法
1.内部排序：递归、交换（冒泡、快排）、选择、插入等
2.外部排序：利用有限内幕才能配合海量的外部存储来处理超大数据集
Java集合 - List | Set
1.Collection
1.List
1.特点
1.有序
2.可重复
3.通过索引操作元素
2.分类
1.底层是数组，查询快，增删慢
1.ArrayList 线程不安全，效率高
2.Vector 线程安全，效率低
2.底层是链表，查询慢，增删快
1.LinkedList 线程不安全，效率高
2.Set
1.特点
1.无序
2.元素唯一
2.分类
1.底层是哈希表
HashSet 保证元素唯一性
2.底层是二叉树
TreeSet 保证元素排序，自然顺序，让对象所属的类去实现Comparable接口，无参构造。比较接口Comparator，带参构造
Java集合 - Map
1.HashMap | HashTable | ConccurentHashMap 区别
1.HashMap
1.在Java8之前采用 数组+链表 的方式实现HashMap，利用他们各自的优势实现
2.在Java8之后采用 数组+链表+红黑树 的方式实现HashMap
3.HashMap.put()方法逻辑（Java 8之后）
1.如果HashMap未被初始化过，则初始化
2.对key求hash值，然后再计算下标
3.如果没有碰撞，直接放入桶中
4.如果碰撞了，以链表的方式链接到后面
5.如果链表长度超过阈值，就将链表转换成红黑树
6.如果链表长度低于6，就将红黑树转回链表
7.如果节点已经存在就替换旧值
8.如果桶满了（容量16*加载因子0.75），就需要resize（扩容2倍后重排）
4.减少碰撞
1.扰动函数：促使元素位置分布均匀，减少碰撞几率
2.使用final对象，并采用合适的equals和hashcode方法
5.扩容问题
1.多线程环境下，调整大小会存在条件竞争，容易造成死锁
2.rehashing是比较耗时的过程
2.线程安全的HashMap
通过调用synchronizedMap(hashMap)方法让HashMap变成线程安全。
3.如何优化Hashtable
1.通过琐细粒度化，将整锁拆解成多个锁进行优化
4.ConcurrentHashMap.put()方法逻辑
1.判断Node[]数组是否初始化，没有则进行初始化操作
2.通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加（链表的头节点），添加失败则进入下一次循环。
3.检查到内部正在扩容，将帮助其一起扩容
4.如果f!=null，则使用synchronized锁住f元素（链表/红黑二叉树的头元素）
如果是Node（链表结构）则执行链表的添加操作
如果是TreeNode（树型结构）则执行树添加操作
5.判断链表长度已经达到临界值8（8是默认值），当节点数超过这个值需要将链表转换成树结构
总结：比起Segment，锁的拆分更细
1.首先使用无锁操作CAS插入头节点，失败则循环重试
2.如果头节点已经存在，则尝试获取头节点的同步锁，再进行操作
5.总结：三者的区别
1.HashMap 线程不安全，底层是通过 数组+链表+红黑树实现
2.Hashtable 线程安全，底层是通过锁住整个对象，然后由数组+链表实现
3.ConccurentHashMap 线程安全，CAS+同步锁，数组+链表+红黑树
4.HashMap的key、value均可为null，而其它两个类不支持
HashMap | Hashtable 区别
1. 线程是否安全
HashMap是非线程安全的，Hashtable是线程安全的。Hashtable内部的方法基本都经过synchronized修饰。
2. 效率
因为线程安全的问题，HashMap要比Hashtable效率高一点，另外，Hashtable基本被淘汰。
3. 对null key 和 null value的支持
在HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null。但是在Hashtable中put进的键值只要有一个null，就直接抛NPE异常。
4. 初始容量大小和每次扩容大小的不同
1. 创建时如果不指定容量初始值，Hashtable默认的初始大小为11，之后每次扩容变为原来的 2n+1。HashMap默认的初始化大小为16，之后每次扩容，容量变为原来的2倍。
2. 创建时如果给定了容量的初始值，那么Hashtable会直接使用你给定的大小，而HashMap会将其扩容到2的幂次方大小（HashMap中的tableSizeFor()方法保证），也就是说HashMap总是使用2的幂次方作为哈希表的大小。
5. 底层数据结构
JDK 8以后的HashMap在解决哈希冲突时有变化，当链表长度大于阈值（默认8）时，将链表转化为红黑树，以减少搜索时间。而Hashtable没有这样的机制。
HashMap | HashSet 区别
我们知道，HashSet底层是基于HashMap实现。
1. HashSet如果检验重复
1. HashSet 计算对象的hashcode值来判断对象加入的位置，同时与其他加入的对象的hashcode值比较。如果没有相符的hashcode值则假设对象没有重复出现。否则调用equals()方法检查hashcode值相等的对象是否真的相同，如果两者相同，则加入操作失败。
2. hashcode() | equals() 相关规定
如果两个对象相等，则hashcode一定也是相同的
两个对象相等,对两个equals方法返回true
两个对象有相同的hashcode值，它们也不一定是相等的
综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。
3. == | equals() 区别
==是判断两个变量或实例是不是指向同一个内存空间，equals是判断两个变量或实例所指向的内存空间的值是不是相同
==是指对内存地址进行比较，equals()是对字符串的内容进行比较
==指引用是否相同，equals()指的是值是否相同
HashMap 底层实现
1. JDK 1.8 previous
JDK1.8 之前 HashMap 底层是 ==数组和链表== 结合在一起使用也就是 ==链表散列==。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
JDK 8 的hash()方法
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
2. JDK 1.8 next
在 JDK 1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认是8）时，将链表转换为红黑树，以减少搜索时间。
TreeMap、TreeSet以及JDK1.8之后的HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。
3. HashMap 的长度为何是2的幂次方
为让HashMap存取高效，尽量减少碰撞，即就是尽量让数据均匀分布。Hash值得取值范围大概有40亿的映射空间，只要哈希函数映射得比较均匀松散，一般难以出现碰撞，但是一个40亿长度的数组，内存是放不下的，所以这个散列值不能直接拿来用，在我们用之前需要先对数组的长度取模运算，得到的余数才能用来作为要存放的位置（对应数组下标）。这个数组下标的计算方法时：(n - 1) & hash。（n表示数组长度）。所以这也就是为啥HashMap的长度要是2的幂次方。
4. HashMap多线程操作导致死循环问题
这里主要原因是因为 在并发下的 rehash() 操作造成元素之间会形成一个循环链表。在JDK 1.8之后解决了这个问题，但是还是不建议在多线程环境下使用HashMap，因为在多线程环境下使用HashMap还是会存在其它问题，如：数据丢失等。在并发环境下推荐使用：ConcurrentHashMap。
ConcurrentHashMap | Hashtable 区别
Hashtable 与 ConcurrentHashMap 的区别主要体现在实现线程安全的方式不同。
1. 底层数据结构
JDK 1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK 1.8 采用的数据结构跟HashMap JDK 1.8 的结构一样 数组+链表/红黑二叉树 。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
==2. 实现线程安全的方式==
① ==在JDK1.7的时候，ConcurrentHashMap（分段锁）== 对整个桶数组进行了分割分段(Segment)，==每一把锁只锁容器其中一部分数据==，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。 到了 JDK 1.8 的时候已经摒弃了Segment的概念，而是直接用 ==Node 数组+链表+红黑树== 的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。
② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。
3. ConcurrentHashMap 线程安全的具体实现方式（底层具体实现）
1. JDK 1.7
首先将数据分为一段一段的存储，然后将每一段数据陪一把锁，当一个线程占用锁访问其中一个段数据时，其它段数据也能被其它线程访问。
提示：ConcurrentHashMap 是由 Segment数组结构 和HashEntry 数组结构构成。
Segment 实现了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
2. JDK 1.8
ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS和synchronized 来保证并发安全。数据结构跟 HashMap 1.8 的结构类似，==数组+链表/红黑二叉树==。Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）
==synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。==
comparable() | comparator 区别
- comparable 接口实际上是出自 java.lang 包，它有一个 compareTo(Object obj) 方法用来排序。
- comparator 接口实际上是出自 java.util 包，它有一个 compare(Object o1, Object o2) 方法用来排序。
一般地，如果我们需要对一个集合自定义排序时，我们需要重写 compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式：1. 重写方法。2. 使用两个参数版的Collections.sort()。
集合框架底层数据结构总结
Collection
1. List
1. ArrayList：Object数组
2. Vector：Object数组
3. LinkedList：双向链表（JDK 1.6之前为循环链表，JDK 1.7取消循环）
2. Set
1. HashSet（无序|唯一）：基于HashMap实现，底层采用HashMap来保存元素。
2. LinkedHashSet：继承了HashSet，并且其内部是通过LinkedHashMap来实现的。
3. TreeSet（有序|唯一）：红黑树（自平衡排序二叉树）。
Map
1. HashMap
JDK 1.8 之前HashMap由数组+链表组成，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（拉链法解决冲突）。JDK 1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转为红黑树，以减少搜索时间。
2. LinkedHashMap
LinkedHashMap 继承自 HashMap，所以它的底层仍然是==基于拉链式散列结构即由数组和链表或红黑树==组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
3. Hashtable
数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。
4. TreeMap
红黑树（自平衡排序二叉树）
集合的选用
主要根据集合的特点选用，如我们需要根据键值获取到元素值时就选用Map接口下的集合。需要排序时选择TreeMap，不需要排序时选择HashMap，需要保证线程安全时选用ConcurrentHashMap。只需要存放元素值时，选择实现Collection接口的集合，需要保证元素唯一时选择实现Set接口的集合如：TreeSet或HashSet，不需要就选择List接口的ArrayList或LinkedList，然后再根据实现这些接口的集合特点来选用。
