集合面试题

①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，然后该线程就会发现此时有并发修改的发生，就会抛出一个并发修改的异常，这样去避免数据不一致和错误的情况。