集合面试题

目录

• ①HashMap的理解？以及为什么要把链表转换为红黑树？
• ②HashMap的put？
• ③HashMap的扩容？
• ④加载因子为什么是0.75？
• ⑤modcount的作用？
• ⑥HashMap与HashTable的区别？
• ⑥HashMap中1.7和1.8的区别？
• ⑦HashMap与ConcurrentHashMap的区别？
• ⑧ArrayList和LinkedList的区别？

---

ArrayList：底层是数组，并且线程不安全。初始大小为0，第一次add的时候扩容(扩容使用grow()方法)为10，再次扩容则为1.5倍。

Vector：底层也是数组，但是线程安全，因为其方法被synchronized修饰。

LinkedList：底层是双向链表，增加删除效率高，查效率低要遍历链表。

HashSet：底层其实是HashMap，即数组+链表+红黑树。

TreeSet：底层是TreeMap。

①HashMap的理解？以及为什么要把链表转换为红黑树？

答：HashMap是双列集合中存放以k-v键值对(并且支持null)的一种集合类型，其底层在jdk1.7之前为数组+链表，在jdk1.8引入了红黑树，底层实现就变成了链表+数组+红黑树(当链表的长度大于8并且数组的长度大于64时链表就会树化为红黑树)。并且HashMap的底层采用链地址法来解决哈希冲突。引入红黑树的原因：链表长度变长就会导致查找的效率降低，将链表转换为红黑树可以加快查询效率。因为链表查询时间复杂度是O(n),而红黑树的查询时间复杂度是O(log n)。(如果数据直接在数组上时间复杂度就是O(1))

②HashMap的put？

①构造器：HashMap初始化时，就只设置了一下加载因子(0.75)

②put方法：

第一步：首先通过hash()方法去计算出哈希值

第二步：判断table是否为空，为空就调用resize()方法去创建一个初始大小为16的table

第三步：然后根据数组长度和哈希值得到索引位置，再判断这个位置是否为空，如果为空就创建一个Node然后放进去

第四步：如果不为空，则去判断其hash值和Key是否相同，如果都是相同的，就会将其value替换掉

第五步：如果比较出key不相同，则去链表上循环比较，直到找到有相同的hash值和key，替换掉就退出，如果整个链表上都没有的话，就会在链表的尾部插入，加入后就会判断是否要扩容还是树化。

③HashMap的扩容？

答：首先hashmap在创建的时候是一个空的，然后在第一次put的时候去检查到table为空，就调用resize()方法给扩容到初始大小16。

然后一直添加数据，当发现链表的长度大于8的时候，就会调用treeifBin()方法去树化，不是直接树化，而是还要先判断数组的长度是否大于64，如果没有的话就还是先会调用resize()去扩容数组为2倍的长度，直到判断出链表长度大于8并且数组长度大于64时，才会把链表转换为红黑树，再添加数据进去。

④加载因子为什么是0.75？

答：首先加载因子是表示hashmap的扩容阈值，当元素数量到达数组长度的0.75就会发生扩容。0.75是默认的加载因子，我们也可以设置成自己想要的值，为什么0.75，首先加载因子的选择是一种权衡，如果加载因子较小，就到导致频繁的扩容发生，导致哈希表的填充度较低，可能会浪费空间。如果加载因子较大虽然减少了扩容的频率，也会导致更多的哈希冲突的发生，导致链表的长度增加，从而影响性能。所以默认的0.75在大多数情况下能够提供较好的性能和空间利用率。所以官方文档中有一段话说明了0.75提供了一个时间复杂度和空间复杂度的一个折中点。

⑤modcount的作用？

答：首先modcount是用来记录被修改的次数。每次put或者remove都会使其加一。这个字段一般是用来实现快速失败(fast-fail)和保证数据一致性的，比如说一个线程在对集合进行遍历的时候会首先把modcount放到一个expectedmodcount中，然后遍历的时候会去比较当前的modcount和expectedmodcount，此时如果当另外一个线程去修改或者删除了集合元素时，会使modcount+1，然后该线程就会发现此时有并发修改的发生，就会抛出一个并发修改的异常，这样去避免数据不一致和错误的情况。

⑥HashMap与HashTable的区别？

答：其都是map下的集合，都是存储k-v键值对的。区别在于

①首先HashMap是线程不安全的，HashTable则是线程安全的，因为其所有的方法都加了synchronized关键字，但是这样导致了性能大大降低所以HashMap的效率要比HashTable快。

②HashTable底层是基于数组+链表实现的，而HashMap在jdk1.7时是数组+链表，但在jdk1.8的时候引入了红黑树，在链表长度大于8并且数组长度大于64时，链表会转换为红黑树。

③HashMap的默认初始大小为16，扩容容量为2倍，而HashTable默认初始大小为11，扩容容量为2n+1。

④HashMap可以null作为键值，但是null键只能有一个，而Hashtable不行。 而且像现在不推荐使用HashTable

⑥HashMap中1.7和1.8的区别？

答：①首先底层结构，1.7是数组加链表，1.8是数组+链表+红黑树。提高了插入和查询的效率。

②插入数据的方式：1.7是头插法，1.8是尾插法。

③1.7中哈希算法比较复杂，为了提高Key的散列性，存在各种右移和异或运算，而1.8引入了红黑树，简化了哈希算法，节省CPU资源。

⑦HashMap与ConcurrentHashMap的区别？

答：首先二者都是以k-v键值对存储数据的集合。其区别在于：

①HashMap是线程不安全的，ConcurrentHashMap是JUC下的是线程安全的，在jdk1.7的时候是通过分段锁来实现的线程安全，jdk1.8则是用Synchronized和CAS以及volatile来保证了线程的安全。

②HashMap允许以null作为键值，而ConcurrentHashMap不允许，因为要避免空值在多线程并发场景下的歧义问题，即如果一个线程读到了一个null的数据，无法判断其是空值还是不存在。

③ConcurrentHashMap支持协助扩容，而HashMap扩容时需要暂停其他操作。 ④迭代：HashMap迭代器因为有modcount的使用导致其他线程修改或删除时，遍历失败，而ConcurrentHashMap则提供了安全的迭代器。

⑧ArrayList和LinkedList的区别？

答：首先他们都是实现了List接口的集合。主要区别在于：

①数据结构：ArrayList是数组实现的，而LinkedList是双向链表实现的。

②访问效率：ArrayList的访问效率比LinkedList快。ArrayList的访问的时间复杂度是O(1)可以通过下标直接定位，而LinkedList访问的时间复杂度是O(n)，只能通过遍历链表去找到。

③增加和删除：LinkedList的增加和删除的效率要比ArrayList快。因为LinkedList只要去修改前后元素的指针即可，而ArrayList要移动插入点或者删除点后面的元素位置。

④空间占用：LinkedList的占用空间比ArrayList大，因为LinkedList的每个节点不仅要保存数据吗，还要保存前后元素的指针。