小滴课堂Java集合相关面试题总结

1. ArrayList如何保证线程安全？

// 答案：
// 方式一：
// synchronizedList底层相当于把集合的set add remove方法加上synchronized锁
List<Object> list = Collections.synchronizedList(new ArrayList<>());

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

// 方式三：
// 自己写一个包装类，继承ArrayList 根据业务，对add set remove方法进行加锁控制

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

2. Vector 和 ArrayList 的初始容量和扩容？

• 二者初始容量均为0，即在调用空参构造函数实例化时，二者容量为0，并在第一次加入元素数据时候附上初始容量值10
• Vector扩容时，如果未指定扩容递增值capacityIncrement，或该值不大于0时，每次扩容为原来的1倍，否则扩容量为capacityIncrement的值
• ArrayList扩容时，每次扩容为原来的1.5倍

3. CopyOnWriteArrayList添加新元素是否需要扩容？具体是如何做的？

• CopyOnWriteArrayList 底层并非动态扩容数组，不能动态扩容，其线程安全是通过加可重入锁ReentrantLock来保证的
• 当向CopyOnWriteArrayList添加元素时，线程获取锁的执行权后，add 方法中会新建一个容量为（旧数组容量+1）的数组，将旧数组数据拷贝到该数组中，并将新加入的数据放入新数组尾部

代码如下：

public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

CopyOnWriteArrayList适用于，读多写少的情况下（读写分离）！因为每次调用修改数组结构的方法都需要重新新建数组，性能低！

4. HashMap 与 HashTable 的区别？

HashMap

• HashMap：底层是基于数组+链表 + 红黑树，非线程安全的，默认容量是16、允许有空的健和值
• 初始size为16，扩容：newsize = oldsize << 1，size一定为2的n次幂
• 当Map中元素总数超过Entry数组的75%，触发扩容操作，为了减少链表长度，元素分配更均匀计算index方法：index = hash & (tab.length – 1)
• 扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入

HashTable

• HashTable：底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁(synchroized)住整个HashTable，效率低，ConcurrentHashMap做了相关优化
• 初始size为11，扩容：(tab.length << 1) + 1
• 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

二者区别

• HashMap不是线程安全的，HashTable是线程安全的
• HashMap允许将null作为一个entry的key或者value，而Hashtable不允许
• HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解
• Hashtable继承自Dictionary类，而HashMap是Map 接口的一个实现类

HashMap与HashTable 求index桶位

• HashMap：index = hash & (tab.length – 1)
• HashTable：index = (hash & 0x7FFFFFFF) % tab.length

二者求桶位index的公式都是为了使每次计算得到的桶位index更分散，这样可以降低哈希冲突。

HashTable中：

• 0x7FFFFFFF 是0111 1111 1111 1111 1111 1111 1111 1111：除符号位外的所有 1
• (hash & 0x7FFFFFFF)得到的结果将产生正整数
• (hash & 0x7FFFFFFF) % tab.length 计算得到的index结果始终为正整数，且确保index的值在 tab.length 范围内！
• HashTable 的数组长度采用奇数导致的hash冲突会比较少，采用偶数会导致的冲突会增多！所以初始容量为11，扩容为newsize = olesize << 1+1，保证每次扩容结果均为奇数

HashMap中：

• 初始容量为 16，当有效数据数量达到数组容量的0.75倍时，触发扩容
• 桶位计算公式：index = hash & (tab.length – 1)，计算桶位index时，容量一定要为2的n次幂，即偶数，这样是为了减少hash冲突，扩容：newsize = oldsize << 1，得到的结果也是偶数
• 此外桶中的链表长度大于8时且数组长度达到64，链表进行树化，小于6时进行反树化
• JDK1.8前HashMap中的链表采用的是头插法，优点是：效率高于尾插法，因为不需要遍历一次链表再进行数据插入
• JDK1.8后使用尾插法，之所以采用尾插法是因为要去判段链表的长度是否大于了8
• HashMap解决哈希冲突的方法采用的是：链表法
• HashMap是先插入数据再判断是否需要库容！

5. HashMap和TreeMap的区别？

• HashMap 上面介绍过了，直接看TreeMap
• TreeMap 底层是基于平衡二叉树(红黑树)，可以自定义排序规则，要实现Comparator接口，能便捷的实现内部元素的各种排序，但是性能比HashMap差

6. Set和Map的关系

• 二者核心都是不保存重复的元素，存储一组唯一的对象
• Set的每一种实现都是对应Map里面的一种封装
• 例如HashSet 底层对应的就是封装了HashMap，TreeSet底层就是封装了TreeMap

7. 插件Map的排序规则是怎样的？

• LinkedHashMap，按照元素添加顺序排序（也可以设置成按照访问顺序排序）
• TreeMap，可以按照自然排序，也可以自定义排序 TreeMap(Comparetor c)

8. HashMap底层为什么选择红黑树而不用其他树，比如二叉查找树，为什么不一开始就使用红黑树，而是链表长度到达8且数组容量大于64的时候才树化？

• 二叉查找树在特殊情况下也会变成一条线性结构，和原先的长链表存在一样的深度遍历问题，查找性能慢，例如：
  
• 使用红黑树主要是为了提升查找数据的速度，红黑树是平衡二叉树的一种，插入新数据后会通过左旋，右旋，变色等操作来保持平衡，解决单链表查询深度的问题
• 之所以一开始不用红黑树是因为，当链表数据量少的时候，遍历线性链表比遍历红黑树消耗的资源少 (因为少量数据，红黑树本身自选、变色保持平衡也是需要消耗资源的)，所以前期使用线性表
• 而之所以以8为树化门槛，是因为经过大量测试，8这个值是最合适的

文章来源: csp1999.blog.csdn.net，作者：兴趣使然の草帽路飞，版权归原作者所有，如需转载，请联系作者。

原文链接：csp1999.blog.csdn.net/article/details/113796502