[数据结构与算法]Java面试题整理《集合篇》

Java集合

集合就是一个可变长度的用来存放数据的容器，准确的说是存放数据对象引用的容器，集合类存放的都是对象的引用，而不是对象的本身（不能存储基本数据类型）。集合类存放于 Java.util 包中，主要有 3 种：set、list和 map。

• 1. Collection：Collection 是集合 List、Set、Queue 的最基本的接口。
• 2. Iterator：迭代器，可以通过迭代器遍历集合中的数据
• 3. Map：是映射表的基础接口

集合和数组的区别

• 数组是固定长度的；集合可变长度的。
• 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
• 数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

Collection 和 Collections 有什么区别？

• Collection是最基本的集合接口，Collection派生了两个子接口list和set，分别定义了两种不同的存储方式。
• Collections是一个包装类，它包含各种有关集合操作的静态方法（对集合的搜索、排序、线程安全化等），此类不能实例化，就像一个工具类，服务于Collection框架。

List、Set与Map三者的区别？

• List ：存储的元素是有序的（按对象的顺序保存对象）、可重复的，允许多个Null元素对象，每个元素都有索引。
• Set：存储的元素是?序的、不可重复的，最多允许一个Null元素对象，只能通过迭代器或foreach的方式进行遍历。
• Map：以键值对（kye-value）的方式存储元素，Key 是?序的、不可重复的，value 是?序的、可重复的，每个键最多映射到?个值。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

List集合

• Arraylist ：基于动态的 Object[] 数组实现的，连序内存存储，适合下标访问（随机访问），适?于频繁的查找?作，数组的缺点是每个元素之间不能有间隔，当数组大小不满足时需要增加存储能力，就要将已经有数组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时，需要对数组进行复制、移动、代价比较高。因此，它适合随机查找和遍历，不适合插入和删除。
• Vector ： 基于动态的Object[] 数组，支持线程的同步，即某一时刻只有一个线程能够写 Vector，避免多线程同时写而引起的不一致性，但实现同步需要很高的花费，因此，访问它比访问 ArrayList 慢
• LinkedList ： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)，适合数据的动态插入和删除，随机访问和遍历速度比较慢。另外，他还提供了 List 接口中没有定义的方法，专门用于操作表头和表尾元素，可以当作堆栈、队列和双向队列使用。

Set集合

• HashSet （?序，唯?）： HashSet 底层就是基于 HashMap 实现的，HashSet的值存放于HashMap的key上，HashMap的value统一为present。因此 HashSet 的实现比较简单，除了 clone() 、 writeObject() 、 readObject() 是 HashSet??不得不实现之外，其他?法都是直接调? HashMap 中的?法。
• LinkedHashSet ： LinkedHashSet 是 HashSet 的?类，并且其内部是通过 LinkedHashMap来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现?样，不过还是有?点点区别的。
• TreeSet （有序，唯?）：红黑树（自平衡的排序二叉树） 基于二叉树的原理对新 add()的对象按照指定的顺序排序（升序、降序），每增加一个对象都会进行排序，将对象插入的二叉树指定的位置。（可以对Integer 和 String 对象都进行默认的排序，而自定义类的对象是不可以的，须实现 Comparable 接口，并且覆写相应的 compareTo()函数）

Map集合

• HashMap ： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表?度?于阈值（默认为 8）（将链表转换成红?树前会判断，如果当前数组的?度?于 64，那么会选择先进?数组扩容，?不是转换为红?树）时，将链表转化为红?树，以减少搜索时间
• LinkedHashMap ： LinkedHashMap 继承? HashMap ，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红?树组成。另外， LinkedHashMap 在上?结构的基础上，增加了?条双向链表，使得上?的结构可以保持键值对的插?顺序。同时通过对链表进?相应的操作，实现了访问顺序相关逻辑。
• Hashtable ： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突?存在的
• TreeMap ： 红?树（?平衡的排序?叉树）

Arraylist 与 LinkedList 区别?

• 底层数据结构： Arraylist 底层使?的是 Object 数组； LinkedList 底层使?的是双向链表数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。）
• 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，不保证线程安全；
• 插?和删除是否受元素位置的影响：
  ① ArrayList 采?数组存储，所以插?和删除元素的时间复杂度受元素位置的影响。 执? add(E e) ?法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)，但是可能会产生扩容。但是如果要在指定位置 i插?和删除元素的话时间复杂度就为 O(n-i)。因为在进?上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执?向后位/向前移?位的操作。
  ②LinkedList 采?链表存储，所以对于 add(E e) ?法的插?，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置 i 插?和删除元素的话时间复杂度近似为 O(n) 因为需要先移动到指定位置再插?。
• 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找。
• 内存空间占?：LinkedList 的每一个节点要比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了前后引用。而 ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留?定的容量空间。

在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。

ArrayList的扩容机制：
以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。 之后在进行扩容时，每次扩容为原来的 1.5 倍。

多线程场景下如何使用 ArrayList？

ArrayList 不是线程安全的，如果遇到多线程场景，可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样：

List<String> synchronizedList = Collections.synchronizedList(list); 

synchronizedList.add("aaa"); 

synchronizedList.add("bbb"); 

for (int i = 0; i < synchronizedList.size(); i++) { 
	System.out.println(synchronizedList.get(i)); 
}

也可以使用线程安全的CopyOnWriteArrayList，其底层也是对增删改方法进行加锁：final ReentrantLock lock = this.lock;

HashMap 和 Hashtable 有什么区别？

• 线程是否安全：HashMap是线程不安全的，HashTable是线程安全的（内部的?法基本都经过 synchronized 修饰）；
• 效率： 因为线程安全的问题， HashMap 要? HashTable 效率??点
• 是否支持键值为null：HashMap中允许键和值为null，但是null作为键只能有一个，HashTable不支持；
• 扩容机制：HashMap的默认容器是16，为2倍扩容，HashTable默认是11，为2倍+1扩容；
• 底层数据结构： JDK1.8 以后的 HashMap 当链表?度?于阈值（默认为 8）（将链表转换成红?树前会判断，如果当前数组的?度?于 64，那么会选择先进?数组扩容，?不是转换为红?树）时，将链表转化为红?树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet区别

HashSet如何检查重复？

当你把对象加?HashSet 时， HashSet 会先计算对象的 hashcode 值来判断对象加?的位置，同时也会与其他加?的对象的 hashcode 值作比较，如果没有相符的 hashcode ， HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调? equals() ?法来检查hashcode 相等的对象是否真的相同。如果两者相同， HashSet 就不会让加?操作成功。

HashMap 的实现原理？

Hash算法：哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈
希值

扰动函数：是 HashMap 的 hash 方法。使? hash 方法也就是扰动函数是为了防??些实现?较差的hashCode() 方法换句话说使?扰动函数之后可以减少碰撞。 多次扰动可以加大哈希值低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性&均匀性，最终减少Hash冲突（jdk1.8扰动了两次，1次位运算 + 1次异或运算，已经达到了高位低位同时参与运算的目的；）

JDK1.8 之前：
JDK1.8 之前 HashMap 底层是数组和链表结合在?起使?也就是链表散列。

• 当我们要put元素时，HashMap 通过key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置。
• 如果当前位置存在元素的话，就判断该元素与要存?的元素的 hash 值以及 key 是否相同。
• 如果相同的话，直接覆盖，不相同就将当前的key-value放如链表中，通过拉链法解决冲突。
• 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。

JDK1.8 之后：
JDK1.8 之后引入了红黑树的概念，当链表?度?于阈值（默认为 8）（将链表转换成红?树前会判断，如果当前数组的?度?于 64，那么会选择先进?数组扩容，而不是转换为红?树）时，将链表转化为红?树，以减少搜索时间。（长度低于6时恢复为链表）

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

什么是红黑树？

• 红黑树是一种特殊的二叉查找树，红黑树的每个结点上都有存储位表示结点的颜色，可以是红(Red)或黑(Black)。
• 红黑树的每个结点是红色或者黑色。但是不管怎么样他的根结点是黑色。每个为空的叶子结点也是黑色
• 如果一个结点是红色的，则它的子结点必须是黑色的。
• 每个结点到叶子结点所经过的黑色结点的个数一样的。（确保没有一条路径会比其他路径长出俩倍，所以红黑树是相对接近平衡的二叉树的）

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。保证这颗树依然是红黑树。

HashMap的扩容操作是怎么实现的？

• 在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进
  行扩容；
• 每次扩展的时候，都是扩展2倍；
• 扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。

在putVal()中，我们看到在这个函数里面使用到了2次resize()方法，resize()方法表示的在进行第一次初始化时会对其进行扩容，或者当该数组的实际大小大于其临界值值(第一次为12)，这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发，这也是JDK1.8版本的一个优化的地方，在1.7中，扩容之后需要重新去计算其Hash值，根据Hash值对其进行分发，但在1.8版本中，则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0，重新进行hash分配后，该元素的位置要么停留在原始位置，要么移动到原始位置+增加的数组大小这个位置上

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

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。我们首先可能会想到采用%取余的操作来实现。但是取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

ConcurrentHashMap的实现原理

JDK1.7 的 ConcurrentHashMap 底层采?分段（Segment）的数组+链表实现，?个 ConcurrentHashMap ?包含?个 Segment 数组，每个Segment中都包含了一个HashEntry数组，HashEntry ?于存储键值对数据，HashEntry之间组成了链表结构。每?段数据配?把ReentranLock锁，当?个线程占?锁访问其中?个段数据时，其他段的数据也能被其他线程访问。
元素查找：二次hash，第一次定位segment字段，第二次hash定位到元素所在的链表的头部

JDK1.8中ConcurrentHashMap 取消了 Segment 分段锁，?是采用 Node 数组（链表采用Node，红黑树采用TreeNode） + 链表 / 红?树的方式，数据结构跟 HashMap1.8 的结构类似。Node的val和next都用volatile修饰，保证可见性查找，替换。通过 CAS 和 synchronized 来保证并发安全，synchronized 只锁定当前链表或红??叉树的?节点，这样只要 hash 不冲突，就不会产?并发，效率?提升 N 倍。

参考文章：
https://gitee.com/SnailClimb/JavaGuide
https://www.bilibili.com/video/BV1Eb4y1R7zd
https://csp1999.blog.csdn.net/article/details/117192375