Java：Java集合系统整理

1. 集合是做什么的？

Java集合类位于Java.util包中，是一个用来存放对象的容器。

2. Java集合框架

可以发现上述所有的集合类，除Map之外，都实现了Iterator接口。
Iterator可用来遍历集合类，提供有hasNext(), next(), remove()三个方法;
其子接口ListIterator在此基础上增加了add(), previous(), hasPrevious()三个方法。

3. 面试题汇总

3.1 List、Set、Map三者的区别？

• List（对付顺序的好帮手）: 存储的元素是顺序的，可重复的；
• Set（注重独一无二的性质）: 存储的元素是无序的，不可重复的；
• Map（用key来搜索的专家）: 使用键值对（key-value）存储，key是无序的，不可重复的；value是无序的，可重复的。

3.2 ArrayList和LinkedList的区别？

1）底层数据结构

• ArrayList底层使用的是Object数组；
• LinkedList底层使用的是双向链表（JDK1.6之前是循环链表，1.7之后取消了循环链表）。

2）插入和删除是否受元素位置的影响

• ArrayList会；
• LinkedList不会。

3）内存占用空间

• ArrayList空间浪费主要体现在List结尾会预留一定的容量空间；
• LinkedList空间浪费体现在每个节点需要存后继和前驱。

4）是否支持快速随机访问

• 随机访问是指通过元素的序号快速获取元素对象（对应于get(int index)方法）
• ArrayList支持；LinkedList不支持。

3.3 ArrayList和Vector的区别？

• ArrayList是List的主要实现类，底层使用Object数组实现，是线程不安全的；
• Vector是List的古老实现类，底层也使用Object数组实现，是线程安全的。

3.4 HashMap和HashTable的区别？

1）线程是否安全

• HashMap线程不安全，想要线程安全的话使用ConcurrentHashMap；
• HashTable线程安全，内部所有的方法基本都经过synchronized修饰。

2）效率高

• HashMap效率高；
• HashTable基本被淘汰，不要在代码中使用它。

3）null值

• HashMap允许key和value为null值，key为null只能有一个，value为null可以有多个；
• HashTable不允许有null值，否则会报异常。

4）初始容量和每次扩充容量大小的不同

• HashMap初始容量为16 ，扩容变为原来的2倍 ，创建时如果给定容量初始值，容量会成为设置容量的2的幂次方； -- HashMap总是使用2的幂作为哈希表的大小
• HashTable初始容量为11 ，扩容每次扩为2n+1，创建时如果给定容量初始值，给定为几就是几。

5）底层数据结构

• Jdk1.8后HashMap扩容机制发生了较大变化，当链表长度大于阈值8（默认）时 ，先判断数组长度如果小于64先对数组进行扩容而不转换成红黑树，之后如果链表长度大于8则将链表转成红黑树；
• HashTable没有这样的机制。

3.5 HashMap和HashSet的区别？

1）HashSet底层是基于HashMap实现的；
2）HashMap实现Map接口，HashSet实现Set接口；
3）HashMap存储键值对，HashSet存储不重复的对象；
4）HashMap添加元素使用put，HashSet添加元素使用add;
5）HashMap使用键计算hashCode ，HashSet使用成员对象计算hashCode，两个对象可能成员对象相同，hashCode相同，使用equals来判断对象的相等性。

3.6 HashSet如何检查重复？

• 新来一个对象，HashSet先检查已存有的对象中是否包含新对象的hashCode，如果不包含，直接加入，如果包含，再equals()看是否相同，不相同则加入，相同则与已有对象重复，不加入这个对象。

注意：hashCode重写与equals()重写问题。

3.7 HashMap底层实现？

1）JDK1.8之前

• 底层是数组和链表；
• 扰动函数（JDK1.7有四次扰动，JDK1.8有进行优化）计算出哈希值，通过（n-1）& hash值（？） 判断当前元素存放的位置；
• 如果当前位置存有元素，判断已存有和准备存入的元素哈希值和key 是否相同，如果相同，覆盖，如果不同，拉链法解决冲突。

2）JDK1.8之后

• 解决哈希冲突时有了较大变化：
• 当链表长度大于默认阈值8时，先判断此时数组长度是否小于64，小于64则先对数组扩容（原来的2倍），否则将链表转换成红黑树，减少搜索时间。

TreeMap、TreeSet、JDK1.8之后的HashMap底层都用到了红黑树；
红黑树是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成线性结构。

3.8 HashMap的长度为什么是2的幂次方？

1）Hash值的范围-2147483648到2147483647，前后加起来大概40亿的映射空间，一般应用是很难出现碰撞的。问题是一个40亿长度的数组，内存是放不下的；
2）所以这个散列值用之前还要先做对数组的长度取模运算，余数为对应的数组下标。数组下标 =（n-1）& hash（n代表数组长度）；
3）hash%length==hash&(length-1)成立的前提是length是2的n次方（why?）；
4）二进制位操作符&相对于%能提高运算效率。

3.9 ConCurrentHashMap和HashTable的区别？

1）底层数据结构不同

• JDK1.7的ConcurrentHashMap底层为分段的数组+链表；JDK1.8之后ConcurrentHashMap与HashMap结构相同，数组+链表/红黑树，与HashMap基本相同；
• HashTable和JDK1.8之前的HashMap结构类似底层是数组(主体)+链表(解决哈希冲突)

2）线程安全实现的方式不同

• ConcurrentHashMap在JDK1.7时，分段锁对数组进行分割分段，没把锁只锁数组中一部分数据。1.8之后，摒弃了段的概念，直接用Node数组+链表/红黑树，并发控制使用synchronized和CAS。整体看起来像是优化过且线程安全的HashMap，尽管JDK1.8中还可以看到段，但已简化其属性，仅是为了兼容旧版本。
• HashTable是同一把锁，效率低下。

3.10 ConCurrentHashMap线程安全的具体实现方式/底层具体实现？

1）JDK1.7

• 数据分成一段一段存储，每个数据段配一把锁，当线程占用锁访问一个数据段时，其他数据段可以被另一个线程访问；
• ConcurrentHashMap = Segment + HashEntry: Segment实现了ReentrantLock，是一种可重入锁。HashEntry用于寸键值对数据。
• 一个ConcurrentHashMap包含一个Segment，Segment结构与HashMap类似（数组+链表），每个Segment守护一个HashEntry（链表结构元素），修改HashEntry首先要获得Segment的锁。

2）JDK1.8

• ConcurrentHashMap取消了Segment分段锁，改用CAS和synchronized来保证并发安全。数据结构跟JDK1.8的HashMap类似。
• Synchronized只锁定当前链表或红黑树的首节点，这样只要不出现Hash冲突，就不会并发，效率提升了N倍。

3.11 比较HashSet、LinkedHashSet和TreeSet三者的异同？

• HashSet是Set的实现类，底层使用HashMap，是线程不安全的，可以存储null值；
• LinkedHashSet是HashSet的子类，可以按添加顺序遍历；
• TreeSet是Set的实现类，底层是红黑树，可以按照添加的顺序遍历，排序的方式有自然排序和定制排序。

参考链接：

https://www.cnblogs.com/lixiansheng/p/11348050.html
JavaGuide