面试题002-Java-Java集合

面试题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 三者的区别？三者底层的数据结构？
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操作直接对哈希表中的节点进行操作，通过更加细粒度的锁，保证了高效的并发访问。