面试题002-Java-Java集合
题目自测
- 1. 说说 List,Set,Map 三者的区别?三者底层的数据结构?
- 2. 有哪些集合是线程不安全的?怎么解决呢?
- 3. 比较 HashSet 、LinkedHashSet 和 TreeSet 三者的异同?
- 4. HashMap 和 Hashtable 的区别?HashMap 和 HashSet 区别? HashMap 和 TreeMap 区别?
- 5. HashMap 的底层实现?
- 6. HashMap 的长度为什么是 2 的幂次方?
- 7. ConcurrentHashMap 和 Hashtable 的区别?
- 8. ConcurrentHashMap 线程安全的具体实现方式/底层具体实现?
题目答案
1. 说说 List,Set,Map 三者的区别?三者底层的数据结构?
答:List 有序、可以包含重复元素。主要实现类为 ArrayList 底层数据结构为动态数组。
Set 无序,不可以包含重复元素。主要实现类为 HashSet 底层数据结构为哈希表。
Map 存储键值对,键不能重复,值可以重复。主要实现类为 HashMap 底层数据结构为数组+链表/红黑树。
2. 有哪些集合是线程不安全的?怎么解决呢?
答:常见的线程不安全的集合类有 ArrayList,LinkedList,HashSet,TreeSet, HashMap,TreeMap等。
解决办法有:1.使用concurrent包中的并发集合类,如ConcurrentHashMap等。
2.使用Collections类的静态方法返回线程安全的集合。
3.使用synchroniza关键字对需要同步的代码块加锁。
3. 比较 HashSet 、LinkedHashSet 和 TreeSet 三者的异同?
答:相同点是这三个类都实现了Set接口,都提供了集合的基本操作,都是线程不安全的。
HashSet 底层数据结构为哈希表,元素无序。
LinkedHashSet 底层数据结构为链表和哈希表,元素按照插入顺序排序,先进先出。
TreeSet 底层数据结构为红黑树,按照自然排序或者通过Comparator自定义排序。
4. HashMap 和 Hashtable 的区别?HashMap 和 HashSet 区别? HashMap 和 TreeMap 区别?
答:
HashMap 和 Hashtable :
- HashMap 线程不安全。可以存储一个null键,和多个null值。初始容量为16,扩容时容量翻倍。
- Hashtable 线程安全,其中的大部分方法使用synchronized关键字修饰。不可以存储null键和值。初始容量为11,扩容时容量变为原来的2n+1。
HashMap 和 HashSet:
- HashMap 存储键值对,基于哈希表实现。
- HashSet 仅存储不重复的元素,基于HashMap实现。
HashMap 和 TreeMap:
- HashMap 基于哈希表实现,不保证顺序,操作时间复杂度为O(1)。
- TreeMap 基于红黑树实现,按照自然排序或者通过Comparator自定义排序,操作时间复杂度为O(log n)。
5. HashMap 的底层实现?
答:它的底层是基于数组+链表、JDK8之后还包括红黑树来存储键值对。
在存储数据时,使用键的hashCode方法计算哈希值,通过哈希值确定元素在数组中的位置。HashMap会根据数组的占用情况自动的调整容量,当超过阈值时,会进行扩容,大小为原来的两倍,并将旧数组的所有元素重新计算哈值后放入新数组。如果该位置为空就直接插入,否则就检查链表或者红黑树,如果链表中已经存在相同的键,就更新对应的值,如果不存在相同的键,则插入新节点,JDK8以后当链表长度超过阈值8时,就将链表转为红黑树。
6. HashMap 的长度为什么是 2 的幂次方?
答:HashMap的长度为2的幂次方,主要是为了简化索引计算、减少哈希冲突和提高性能。通过位运算代替取模运算,可以更高效地计算数组索引,并确保哈希值的均匀分布。
7. ConcurrentHashMap 和 Hashtable 的区别?
答:两者的区别主要体现在实现线程安全的方式上不同
Hashtable 使用单一锁机制,使用synchronized关键字来实现,适用于低并发场景。
ConcurrentHashMap 采用了一种更复杂的机制,包括CAS操作、分段锁和sychronized相结合的方式来实现线程安全,提供更高的并发性能。
8. ConcurrentHashMap 线程安全的具体实现方式/底层具体实现?
答:在JDK1.7及之前,采用分段锁机制,它通过将整个Map分成多个Segment,每个Segment都有自己的锁,从而允许多线程同时访问不同的Segment。
在JDK8及以后取消了Segment,采用synchronized和CAS操作直接对哈希表中的节点进行操作,通过更加细粒度的锁,保证了高效的并发访问。