Java集合框架2：常见问题

小灰灰 2023-03-05 03:25 5阅读 0赞

### 文章目录 ###

*   *   *  1.List，Set，Map三者的区别？
         *  2.ArrayList与LinkedList的区别？
         *  3.List的遍历选择
         *  4.双向链表与双向循环链表的不同
         *  6.ArrayList和Vector有什么区别呢？为什么用ArrayList取代Vector呢？
         *  7.HashSet如何检查重复呢？
         *  8.ConcurrentHashMap于HashTable的区别
         *  9.ConcurrentHashMap线程安全的底层实现
         *  10.ArrayList的扩容机制

### 1.List，Set，Map三者的区别？ ###

*  List：List是对付顺序的好帮手，它的接口存储一组不唯一（可以有多个元素引用相同的对象）有序的对象。
 *  Set：Set有着独一无二的性质，不允许重复的集合，不会有多个元素引用相同的对象。
 *  Map：使用键值对进行存储，两个Key可以引用相同的对象，但Key不能重复，Key可以是任何对象。

### 2.ArrayList与LinkedList的区别？ ###

*  是否能保证线程安全：他们两都不是同步的，所以不能保证线程安全。
 *  底层数据结构：ArrayList底层使用的是Object数组，LinkedList底层使用的是双向链表的结构。
 *  插入和删除的时候是否会受元素位置的影响：  
    （1）ArrayList采用数组存储，所以在操作的时候会受元素位置的影响，默认add的时候，元素都是添加到末尾，这时的时间复杂度是O(1)；但插入在指定位置时，此时的时间复杂度就变成了O(n)。  
    （2）LinkedList采用链表存储，对于插入删除的操作不受位置的影响，近似为O(1)；但是在指定位置进行插入和删除的操作的时候，时间复杂度近似为O(n)，因为指针需要先移动到指定的位置再插入。
 *  是否支持快速随机访问：LinkedList不支持高效的随机的访问，但是ArrayList可以，因为后者直接从下标进行访问。
 *  内存空间占用情况：  
    （1）ArrayList的空间空间浪费主要体现在列表的结尾会预留一定的容量空间，因为要中间插入的时候那个元素后的每个元素都要后移。  
    （2）LinkedList的空间花费则体现在它的每一个元素都需要消耗较多的空间，因为要存放它后继和前驱的数据。

### 3.List的遍历选择 ###

*  这里要说的一个接口就是RandomAccess接⼝，查看源码我们发现实际上 RandomAccess 接⼝中什么都没有定义。所以，RandomAccess 接⼝不过是⼀个标识罢了。标识什么？ 标识实现这个接⼝的类具有随机访问功能。在 binarySearch（ ）⽅法中，它要判断传⼊的list 是否 RamdomAccess 的实例，如果是，调⽤indexedBinarySearch（） ⽅法，如果不是，那么调⽤ iteratorBinarySearch（） ⽅法。

public static <T>
     int binarySearch(List<? extends Comparable<? super Tjk list, T key)
    { 
    	 if (list instanceof RandomAccess || list.size()
    <BINARYSEARCH_THRESHOLD)
    		 return Collections.indexedBinarySearch(list, key);
     else
    	 return Collections.iteratorBinarySearch(list, key);
     }

*  ArrayList 实现了 RandomAccess 接⼝， ⽽ LinkedList 没有实现。为什么呢？我觉得还是和底层数据结构有关！ ArrayList 底层是数组，⽽ LinkedList 底层是链表。数组天然⽀持随机访问，时间复杂度为 O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O（n），所以不⽀持快速随机访问。 ArrayList 实现了 RandomAccess 接⼝，就表明了他具有快速随机访问功能。 RandomAccess 接⼝只是标识，并不是说 ArrayList 实现 RandomAccess 接⼝才具有快速随机访问功能的！
 *  List遍历方式的选择：  
    （1）实现了 RandomAccess 接⼝的list，优先选择普通 for 循环 ，其次 foreach。  
    （2）未实现 RandomAccess 接⼝的list，优先选择iterator遍历（foreach遍历底层也是通过  
    iterator实现的,），⼤size的数据，千万不要使⽤普通for循环。

### 4.双向链表与双向循环链表的不同 ###

*  双向链表： 包含两个指针，⼀个prev指向前⼀个节点，⼀个next指向后⼀个节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]
 *  双向循环链表：最后一个节点的next指向head，而head的prev指向最后一个节点，构成了一个环。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]

### 6.ArrayList和Vector有什么区别呢？为什么用ArrayList取代Vector呢？ ###

*  Vector 类的所有⽅法都是同步的。可以由两个线程安全地访问⼀个Vector对象、但是⼀个线程访问Vector的话代码要在同步操作上耗费⼤量的时间。
 *  Arraylist 不是同步的，所以在不需要保证线程安全时建议使⽤Arraylist。
 *  如果又想用ArrayList又想线程安全呢？  
    （1）用List list =Collections.synchronizedList(new ArrayList());创建对象。  
    （2）也可以复制容器 java.util.concurrent.CopyOnWriteArrayList进行操作,例如：final CopyOnWriteArrayList cowList = new CopyOnWriteArrayList(Object);

### 7.HashSet如何检查重复呢？ ###

*  当你把对象加入到HashSet中后，他会首先计算此对象的hashcode来判断对象加入的位置，同时会同之前的对象的hashcode做比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调⽤ equals（） ⽅法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加⼊操作成功。
 *  hashCode()与equals的相关规定：  
    （1）如果两个对象相等，那么他们的hashCode也是相等的。  
    （2）对两个相等的对象进行equals()方法调用，返回true。  
    （3）两个对象的hashCode值相等，他们不一定相同，为什么呢？  
    hashcode本身就是个函数，是可以重载的，你完全可以写个函数总是返回固定值。但hashcode函数从设计要求上来说，要尽量保证：不同对象的hashcode不同。  
    （4）equals⽅法被覆盖过，则hashCode⽅法也必须被覆盖。  
    （5）hashCode()的默认⾏为是对堆上的对象产⽣独特值。如果没有重写hashCode()，则该class的两个对象⽆论如何都不会相等（即使这两个对象指向相同的数据）。

### 8.ConcurrentHashMap于HashTable的区别 ###

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。

*  底层数据结构：  
    （1）**jdk1.7的ConcurrentHashMap底层采用分段的数组+链表实现，jdk1.8采用的数据结构跟HashMap1.8的结构一样，都是数组+链表/红黑树二叉树**。  
    （2）Hashtable 和 JDK1.8 之前的HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是HashTable 的主体，链表则是主要为了解决哈希冲突⽽存在的。
 *  实现线程安全的方式（重点）：  
    （1）jdk1.7的时候，ConcurrentHashMap采用分段锁的形式对整个桶数组进行了分割分段，每一把锁只锁其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高了并发的访问效率。  
    **到了jdk1.8的时候，不再使用对桶数组分割的概念，而是直接使用Node数组+链表+红黑树的数据结构来实现，并发控制使用synchronized和CAS来操作**。虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。  
    （2）对于HashTable来说，**使用synchronized来保证线程安全，但效率很低**。当一个线程同步访问同步方法的时候其他线程也访问同步方法，可能会进入阻塞或者轮询状态，如使用普通话添加元素，另一个线程不能使用put添加元素，也不能使用get，也不能使⽤ get，竞争会越来越激烈效率越低。
 *  更多有关ConcurrentHashMap的介绍：[传送门][Link 1]
 *  两者的对比图：  
    图⽚来源：http://www.cnblogs.com/chengxiao/p/6842045.html  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 3]

### 9.ConcurrentHashMap线程安全的底层实现 ###

*  jdk1.7的版本  
    首先将数据分为一段一段的存储，然后给每一段数据分配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也可以被其他的线程访问。  
    **ConcurrentHashMap是由Segment数据结构和HashEntry数据结构组成的。**  
    Segment实现了ReentrantLock(重进入锁)，所以Segment是一种可重进入锁，扮演了锁的角色。HashEntry用于存储键值对数据。  
    一个ConcurrentHashMap里包含着一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表的结构，一个Segment包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改的时候，必须先获得其对应的Segment的锁。
 *  jdk1.8的版本  
    ConcurrentHashMap取消了Segment的分段锁，采用CAS和synchronized来保证线程安全。数据结构跟HashMap1.8的结构相似，采用数组+链表/红黑树。Java8在链表长度一定阈值（8）时将链表（寻址空间复杂度为O(n)）转换为红黑树（寻址空间复杂度为O(log(N))）。  
    synchronized只锁定当前链表或红黑二叉树的首节点，这样只要HashMap不冲突，就不会产生并发，效率会提升N倍。
 *  扩展：什么是CAS算法  
    CAS：Compare and Swap，即比较再交换。对于CAS的理解，CAS是一种无所算法，它有3个操作数，内存值为V，旧的预期值A，要修改的新值为B。当且仅当预期值A和内存值V修改为B，否则什么也不做。

### 10.ArrayList的扩容机制 ###

*  ArrayList的初始化方式：  
    （1）默认的构造函数，使用初始化容量为10构造一个空列表（无参构造）。  
    （2）带初始容量参数的构造函数（用户自己指定）。  
    （3）构造包含指定的collection元素的列表，这些元素利用该集合的迭代器按顺序返回。如果指定的集合为null，throws NullPointerExpection。  
    值得注意的是：以无参数构造方法创建ArrayList时，实际上会初始化赋值的是一个空数组。当真正对数组进行添加元素操作的时候，才会真正的分配容量，即向数组咱添加第一个元素的时候，数组容量扩为10。
 *  请移步此链接：[传送门][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: /images/20230208/1f12fd2008fa496aa5277eb8b0ac8330.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]: /images/20230208/34d818326aa749eab23d309b3a660722.png
[Link 1]: https://www.cnblogs.com/chengxiao/p/6842045.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]: /images/20230208/b1f59e9517f34347aa56efda904ccb47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 3]: /images/20230208/7b72ccb58576436e9380adbdaf31d8de.png
[Link 2]: https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md