Java集合夺命十连问？

文章目录

• Java集合夺命十连问？
• • 1、引出集合，常见的集合有哪些？
  • 2、线程安全的集合有哪些？
  • 3、ArrayList与LinkedList异同点？
  • 5、ArrayList的扩容机制？
  • 6、HashMap的底层数据结构是什么？
  • 7、为了解决哈希冲突，不直接使用红黑树？而选择先用链表，再转红黑树？
  • 8、HashMap的put方法流程？
  • 9、HashMap的resize方法的执行过程？
  • 10、HashMap为什么线程不安全？

1、引出集合，常见的集合有哪些？

接口体系：List、Set、Queue、Map

类体系：ArrayList、LinkedList、Hashset、TreeSet、LinkedList、HashMap、TreeMap

2、线程安全的集合有哪些？

线程安全：

• Hashtable:比HashMap多了个线程安全。
• concurrentHashMap:是一个高效、线程安全的集合。
• Vector:比ArrayList多了个同步化机制。
• Stack:栈，是线程安全的，继承于Vector。

线程不安全的：

• HashMap
• ArrayList
• LinkedList
• HashSet
• TreeSet
• TreeMap

3、ArrayList与LinkedList异同点？

• **线程安全：**都是不同步的，不保证线程安全；
• **底层数据结构：**Arraylist底层是Object数组，LinkedList底层是双向循环链表；
• 插入和删除是否受元素影响： Arraylist采用数组存储，插入和删除元素的时间复杂度受元素位置影响，如：执行add(E e)方法，默认追加到此列表的末尾，O(1),在指定位置i插入和删除元素,O(n - i),i 以及第i个元素之后n-i个元素都要执行向后/向前移一位操作。LinkedList采用链表存储，插入、删除时间复杂度不受元素位置的影响，都是近似O(1)。
• 快速随机访问： ArrayList实现了RandmpAccess接口，有随机访问，(get(int index)方法)
• 内存空间占用： ArrayList空间浪费主要在list列表的结尾会预留一定的容量空间，LinkedList的空间花费体现在它每一个元素都要消耗比ArrayList更多的空间
• （因为要存放直接后继和直接前驱以及数据）

4、ArrayList与Vector区别？

• Vector是线程安全的，在关键的方法上都加了synchronized关键字，保证线程的安全性
• ArrayList在底层数组不够用时在原来基础上扩展0.5倍，Vector扩展1倍，ArrayList有利于节约空间

5、ArrayList的扩容机制？

ArrayList扩容的本质是计算出新的扩容数组size后实例化，将原来的数组复制到新数组中去，默认情况下，新容量是原容量的1.5倍

6、HashMap的底层数据结构是什么？

JDK1.7的时候是数组加链表，数组是HashMap的主体，链表是为了解决哈希冲突存在的。

JDK1.8的时候是数组+链表+红黑树，链表过长会影响HashMap的性能，所以达到一定条件会进行转换：

• 链表长度超过8，数组长度大于64时，链表会转化为红黑树。
• 当数组长度小于64时，会优先扩容数组，不会转换红黑树，减少搜索时间

7、为了解决哈希冲突，不直接使用红黑树？而选择先用链表，再转红黑树？

因为红黑树，需要左旋、右旋、变色来保持平衡，而单链表不需要，此时单链表能够保证查询性能，当元素大于8个的时候，链表为O(n)，红黑树为O(logn),这时需要红黑树加快查询效率，但是新增节点的效率降低了。

开始的时候用红黑树的结构，元素太少，新增效率又比较慢，无疑是浪费性能

8、HashMap的put方法流程？

1. 首先根据key值计算hash值，找到数组存储的下标
2. 如果数组是空的，调用resize进行初始化
3. 如果没有哈希冲突，直接放在对应的数组下标
4. 如果有冲突，且key已经存在，覆盖掉value;
5. 如果冲突后，发现该节点是红黑树，将节点挂在树上；
6. 如果冲突后是链表判断链表是否大于8，如果大于8且数组容量小于64，进行扩容，如果链表节点大于8且数组容量大于64，将这个结构转换成红黑树，否则链表插入键值对，若key存在，覆盖掉value.

9、HashMap的resize方法的执行过程？

两种情况会调用resize()方法：

1. 第一次调用HashMap的put方法时，会调用resize方法对table数组进行初始化，如果不传入指定值默认大小为16
2. 扩容会调用resize，size > threshold时，table数组大小翻倍。

每次扩容之后容量都是翻倍的，扩容后将原数组中所有元素找到新数组中合适的位置。

当我们把table[i]位置的所有Node迁移到newtab中去的时候：这里面的node要么在newtab的i位置（不变），要么在newtab的i + n位置。我们可以：把table[i]这个桶中的node拆分成两个链表l1和l2:如果hash & n = 0,那么当前这个node被连接到l1链表上；否则连接到l2链表上，这样，遍历完table[i]处的所有node的时候，我们就得到了两个链表l1 和 l2，这时newtab[i] = l1 ,newtab[i + n] = l2，这就完成了table[ i ]位置所有node的迁移，这也是HashMap容量一定是2的整数次幂带来的方便之处。

10、HashMap为什么线程不安全？

多线程下扩容死循环。JDK1.7中的HashMap使用头插法插入元素，多线程的环境下，扩容的时候有可能出现环形链表，JDK1.8使用尾插法，不会出现环形链表的问题。

多线程的put可能导致元素丢失。多线程同时执行put操作，如果计算出来的索引位置是相同的，会造成前一个key被后一个key覆盖，导致元素的丢失。
put和get并发时，可能导致get为null.线程1执行put时，因为元素个数超过threshold而导致rehash，线程2此时执行get,有可能导致这个问题。