Java集合（List、Map、Set）详解

素颜马尾好姑娘i 2022-03-15 11:12 343阅读 0赞

#### 一、集合的概念 ####

**1. 什么是集合**  
　　 在Java当中，有一个类专门用来存放其它类的对象，这个类就叫做集合，它就是将若干性质相同或相近的类对象组合在一起而形成的一个整体 。

**2. 常用的Java集合**  
![常用的Java容器][Java]

#### 二、List，Map，Set，Queue ####

**1. List**  
`有序的 collection(也称为序列)`。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。与 set 不同，列表通常允许`重复`的元素。

*  **Arraylist：** Object数组
 *  **Vector：** Object数组
 *  **LinkedList：** 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)

**2. Set**  
一个`不包含重复元素的 collection`。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。正如其名称所暗示的，此接口模仿了数学上的 set 抽象。

*  **HashSet（无序，唯一）:** 基于 HashMap 实现的，底层采用 HashMap 来保存元素
 *  **LinkedHashSet：** LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
 *  **TreeSet（有序，唯一）：** 红黑树(自平衡的排序二叉树。)

**3. Map**  
`将键映射到值的对象`。一个映射不能包含重复的键；每个键最多只能映射到一个值。

*  **HashMap：** JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
 *  **LinkedHashMap：** LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
 *  **Hashtable：** 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。
 *  **TreeMap：** 红黑树（自平衡的排序二叉树）

**4. Queue**  
`在处理元素前用于保存元素的collection`。除了基本的 Collection 操作外，队列还提供其他的插入、提取和检查操作。

**5. List Set Map的区别**

*  **List(对付顺序的好帮手)：** List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象；
 *  **Set(注重独一无二的性质):** 不允许重复的集合。不会有多个元素引用相同的对象。；
 *  **Map(用Key来搜索的专家):** 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

#### 三、ArrayList，LinkedList，Vector ####

**1. ArrayList概念**

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable

ArrayList 的底层是`数组队列`，相当于动态数组。与 Java 中的数组相比，它的容量`能动态增长`。在添加大量元素前，应用程序可以使用`ensureCapacity`操作来增加 ArrayList 实例的容量，这可以减少递增式再分配的数量。

它继承于 **AbstractList**，实现了 **List**, **RandomAccess**, **Cloneable**, **java.io.Serializable** 这些接口。

*  ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
 *  ArrayList 实现了**RandomAccess 接口**， RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持**快速随机访问**的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
 *  ArrayList 实现了**Cloneable 接口**，即覆盖了函数 clone()，**能被克隆**。
 *  ArrayList 实现**java.io.Serializable 接口**，这意味着ArrayList**支持序列化**，**能通过序列化去传输**。

和 Vector 不同，**ArrayList 中的操作不是线程安全的**！所以，建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。

**2. LinkedList概念**

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList是一个实现了 List接口 和 Deque接口 的双端链表。

LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性。

LinkedList不是线程安全的，如果想使其变成线程安全，可以调用静态类Collections类中的`synchronizedList`方法：

List list=Collections.synchronizedList(new LinkedList(...));

内部结构分析:  
**如下图所示：**

![LinkedList内部结构][LinkedList]

看完了图之后，我们再看LinkedList类中的一个**内部私有类Node**就很好理解了：

private static class Node<E> { 
            E item;//节点值
            Node<E> next;//后继节点
            Node<E> prev;//前驱节点
    
            Node(Node<E> prev, E element, Node<E> next) { 
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }

这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继结点。

**3. Vector概念**

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable

Vector 类可以实现`可增长的对象数组`。与数组一样，它包含可以使用整数索引进行访问的组件。但是Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。

Vector 是同步的。

#### 四、ArrayList，LinkedList，Vector常见面试题 ####

**1. Arraylist 与 LinkedList 有什么区别？**

*  **1. 是否保证线程安全：** `ArrayList` 和 `LinkedList` 都是不同步的，也就是都不保证线程安全；
 *  **2. 底层数据结构：** `Arraylist` 底层使用的是 **`Object` 数组**；`LinkedList` 底层使用的是 **双向链表** 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环）；
 *  **3. 插入和删除效率：** ① **`ArrayList` 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。** 比如：执行`add(E e)`方法的时候， `ArrayList` 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（`add(int index, E element)`）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② **`LinkedList` 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。**
 *  **4. 是否支持快速随机访问：** `LinkedList` 不支持`高效`的随机元素访问，而 `ArrayList` 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于`get(int index)`方法)；
 *  **5. 内存空间占用：** ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

**下面再总结一下Arraylist 与 LinkedList的场景选择：**  
综合来说，在需要频繁读取集合中的元素时，更推介使用ArrayList，而在插入和删除操作较多时，更推介使用LinkedList。

**2. ArrayList 与 Vector 的区别是什么?**

`Vector`类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。`Arraylist`不是同步的，所以在不需要保证线程安全时建议使用Arraylist。即：

*  线程安全：Vector 使用了 Synchronized 来实现线程同步，是线程安全的，而 ArrayList 是非线程安全的；
 *  性能：ArrayList 在性能方面要优于 Vector。

#### 五、HashMap，Hashtable，TreeMap ####

**1. HashMap概念**

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

HashMap 主要用来存放`键值对`，它基于`哈希表的Map接口实现`，是常用的Java集合之一。

JDK1.8 之前 HashMap 由 `数组+链表` 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（"拉链法"解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

JDK1.8 之前 HashMap 底层是 **数组和链表** 结合在一起使用也就是 **链表散列**。HashMap 通过 **key 的 hashCode 经过扰动函数处理过后得到 hash 值**，然后通过 `(n - 1) & hash` 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过`拉链法`解决冲突。

**所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法，换句话说使用扰动函数之后可以减少碰撞。**

所谓 **“拉链法”** 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。  
![jdk1.8之前的内部结构][jdk1.8]  
相比于之前的版本，JDK1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。  
![JDK1.8之后的HashMap底层数据结构][JDK1.8_HashMap]

**2. Hashtable概念**

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, Serializable

此类实现一个哈希表，该哈希表将键映射到相应的值。任何非 null 对象都可以用作键或值。  
Hashtable 是同步的。

HashMap类大致相当于Hashtable ，除了它是不同步的，并允许null。

**3. TreeMap概念**

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

基于`红黑树(Red-Black tree)的 NavigableMap`实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。  
此实现为 containsKey、get、put 和 remove 操作提供受保证的log(n)时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的 Introduction to Algorithms 中的算法的改编。

注意，此实现`不是同步`的。如果多个线程同时访问一个映射，并且其中至少一个线程从结构上修改了该映射，则其必须外部同步。

#### 五、HashMap，Hashtable，TreeMap常见面试题 ####

**1. HashMap 和 Hashtable 有什么区别？**

*  **线程是否安全：** HashMap 是非线程安全的，HashTable 是线程安全的；因为HashTable 内部的方法基本都经过`synchronized` 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
 *  **效率：** 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
 *  **对Null key 和Null value的支持：** HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException；
 *  **初始容量大小和每次扩充容量大小的不同 ：** 创建时如果不指定容量初始值，HashMap 默认的初始化大小为16，之后每次扩充，容量变为原来的2倍。Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1；
 *  **底层数据结构：** JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间，Hashtable 没有这样的机制。

下面这个方法保证了 HashMap 总是使用2的幂作为哈希表的大小。

/** * Returns a power of two size for the given target capacity. */
        static final int tableSizeFor(int cap) { 
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

**2. ConcurrentHashMap**

*  **底层数据结构：** JDK1.8 的 ConcurrentHashMap 底层采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树；
 *  **实现线程安全的方式（重要）：** **到了 JDK1.8 后ConcurrentHashMap（分段锁）已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化）** 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。  
    **两者的对比图：**

**JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）：**

![JDK1.8的ConcurrentHashMap][JDK1.8_ConcurrentHashMap]  
ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。Java 8在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红黑树（寻址时间复杂度为O(log(N))）  
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

**3. HashMap的实现原理是什么？**

*  [HashMap实现原理][HashMap]

**4. HashMap是有序的还是无序的？**  
　　HashMap 的一个功能缺点就是它的`无序性`，被存入到 HashMap 中的元素，在遍历 HashMap 时，其输出是无序的。如果希望元素保持输入的顺序，可以使用 LinkedHashMap 替代。  
　　LinkedHashMap 继承自 HashMap，具有高效性，同时在 HashMap 的基础上，又在内部增加了一个链表，用以存放元素的顺序。

#### 六、HashSet，TreeSet ####

**1. HashSet概念**

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable

此类实现Set接口，由哈希表（实际为HashMap实例）支持。对集合的迭代次序不作任何保证，特别是它不能保证订单在一段时间内保持不变。这个类允许null元素。

注意，此实现不是同步的。如果多个线程同时访问一个哈希 set，而其中至少一个线程修改了该 set，那么它必须保持外部同步。

**2. TreeSet概念**

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable

基于 `TreeMap 的 NavigableSet 实现`。使用元素的自然顺序对元素进行排序，或者根据创建 set 时提供的 Comparator 进行排序，具体取决于使用的构造方法。  
此实现为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。

注意，此实现不是同步的。如果多个线程同时访问一个 TreeSet，而其中至少一个线程修改了该 set，那么它必须 外部同步。

**3. HashMap 和 HashSet区别**

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 `clone()`、`writeObject()`、`readObject()`是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

<table> 
 <thead> 
  <tr> 
   <th align="center">HashMap</th> 
   <th align="center">HashSet</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">实现了Map接口</td> 
   <td align="center">实现Set接口</td> 
  </tr> 
  <tr> 
   <td align="center">存储键值对</td> 
   <td align="center">仅存储对象</td> 
  </tr> 
  <tr> 
   <td align="center">调用 <code>put()</code>向map中添加元素</td> 
   <td align="center">调用 <code>add()</code>方法向Set中添加元素</td> 
  </tr> 
  <tr> 
   <td align="center">HashMap使用键（Key）计算Hashcode</td> 
   <td align="center">HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以用equals()来判断对象的相等性</td> 
  </tr> 
 </tbody> 
</table>

**4. HashSet如何检查重复？**

当把对象加入`HashSet`时，HashSet会先计算对象的`hashcode`值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用`equals()`方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。

[Java]: /images/20220315/5022eee3030c441f8164d361b7252af5.png
[LinkedList]: /images/20220315/676fdac112dc4fc691ba2c7a069d0003.png
[jdk1.8]: /images/20220315/ac85c1ede495466bab686ad41f5522a6.png
[JDK1.8_HashMap]: /images/20220315/4dd749fb31c4421f989cc4781d01e21a.png
[JDK1.8_ConcurrentHashMap]: /images/20220315/170113e88afd44b1bf060479a33e5883.png
[HashMap]: https://www.jianshu.com/p/c561bab28e19