Java中的集合总结List，Set，Vector，Map，HashMap等（包含底层源码分析）

清疚 2022-09-02 13:43 14阅读 0赞

集合、数组都是对多个数据结构进行存储操作的结构，简称Java容器。但是随着数据量的增大，数组越来越不能满足现代的开发要求。比如数组初始化以后，长度就确定了，不便于扩展；数组声明的时候，就决定了元素初始化的类型且添加、删除操作效率低下。 Java集合可以看做一个容器，比较灵活，可以动态的把多个对象昂如容器中。Java集合可以存储数量不等的多个对象，还可以保存具有映射关系的关联数组。

Java集合可以分为Collection和Map两种体系

①Collection接口：单列数据，定义了存储一组对象方法的集合。 包含了以下子接口。

<1>List接口：存储有序的，可以重复的数据，实现类有ArrayList,LinkedList,Vector

<2>Set接口：存储无序的，不可重复的数据，实现类有HashSet,LinkedHashSet,TreeSet

②Map接口：双列集合，用来存储一对一对的数据，键值对（key—value）存储

其中包含了Map接口的实现类有：HashMap,LinkedHashMap,TreeMap,HashTable,Properties

Collection集合框架图如下：虚线是实现关系，实线是继承关系

Map集合框架图如下：虚线实现关系，实线是继承关系

2、Collection接口方法  
Collection接口中的方法如下：

（1）添加

add(Object obj)：向集合中添加一个对象

addAll(Collection coll)：向集合中添加集合对象

（2）获取有效元素的个数

int size();

（3）清空集合

void clear()

（4）集合是否为空

boolean isEmpty()

（5）集合中是否包含某个元素

boolean contains(Object obj)：通过equals方法判断是否是同一个对象

boolean containsAll(Collection coll)：通过equals方法比较两个集合的元素是否相等

（6）删除

boolean remove(Object obj)：通过equals方法判断是否是删除的那个元素；如果需要删除的元素在集合里面有重复的元素，那么只删除第一个

boolean removeAll(Collection coll)：取当前集合的差集

（7）取两个集合的交集

boolean retainAll(Collection c)：把交集的结果存储到当前集合中

（8）集合是否相等

boolean equals(Object obj)

（9）转成对象数组

Object\[\] toArray()

（10）获取对象的哈希值

hashCode()

（11）遍历Collection集合

iterator()：返回迭代器对象，用于集合遍历

小结：具体实现需要去敲代码啦。可以举个例子，超级简单的了，耶\\/ \\/

3、遍历Collection集合方式：Iterator迭代器接口；for循环遍历  
方式一：Iterator迭代器接口

注意：Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。

设计模式中有种模式叫做迭代器模式，用于提供一种方法访问一个容器对象中的元素，又不暴露该对象中的内部细节。迭代器模式因此而生。

Collection接口继承了java.lang.iterator接口，该接口有一个iterator()方法，那么所有实现Collection接口的集合类都有一个iterator()方法，返回一个Iterater的接口对象。集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标在第一个元素之前。

Iterator接口中的方法：

① hasNext()：判断是否还有下一个元素

② next()：指针下移；并且将下移以后集合位置上的元素返回

③ remove()：删除集合中的元素

Iterator的执行原理：

开始遍历集合的时候，默认next()指向的集合第一个元素之前的位置，hasNext()方法判断集合中是否有下一个元素。如果有下一个元素，next()方法指针下移，并将下移集合位置上的元素进行返回。直到while(iterator.next())为false；迭代过程如下图所示。

注意：Iterator可以删除集合的元素，但是遍历过程中可以通过迭代器对象的remove方法，而不是集合对象的remove方法。

remove方法代码示例：

Iterator iterator = collection.iterator();  
while(iterator.hasNext())\{  
Object obj = iterator.next();  
if(obj.equals("Tom"))\{  
iterator.remove();  
\}  
\}  
方式二：for循环遍历，增强for循环实现集合的遍历

增强for循环底层也是Iterator迭代器，具体请转到：https://blog.csdn.net/Sunshineoe/article/details/109470170

4、Collection子接口一：List  
Java中的数组可以用List集合来代替，解决了存储数据的局限性。

List集合的特点，集合中的元素有序，可以重复，集合中的元素都有其对应的索引。容器中的元素对应的是一个整型的序号记载容器中的位置，可以根据序号存取容器中的元素。List接口实现类常用的有：

ArrayList,LinkedList,Vector。下面对实现类进行介绍。

① ArrayList：作为List接口的主要实现类，线程不安全，效率高；底层是Object\[\]数组，elementData进行存储。

② LinkedList：对于频繁的插入、删除操作，使用类的效率比ArrayList高，底层使用的是双向链表

③ Vector：作为List接口的古老的类，线程安全，效率低；底层是Object\[\]数组，elementData进行存储。

List接口中常用方法：

void add(Object obj)：在集合的末尾添加元素

void add(int index,Object obj):在index位置上插入obj元素

Object get(int index)：获取指定index位置上的元素

void remove(int index)：删除index位置上的元素

void remove(Object obj)：删除obj元素

set(int index,Object obj)：修改index位置上的obj元素

size()：集合的长度

List集合遍历的方式：

① Iterator迭代器方式

② 增强for循环

③ 普通的循环

JDK1.7的ArrayList实现类的源码分析：

当创建ArrayList list = new ArrayList()，底层创建的是一个初始值为10的Object数组。有点饿汉式单例模式的意思。着急去创建数组容量的初始值。这也是JDK1.7和JDK1.8的一个重要区别。

添加元素的源码：

grow方法就是扩容的，当存储空间不够的时候，集合会进行扩容，默认扩容原来的1.5倍

JDK1.8的ArrayList实现类的源码分析：

初始化构造器的时候先给一个空的容量值，1.7的时候是直接在构造方法中初始值就给一个10。

增加元素的时候首先看一看当前容量够不够，不够的话在进行扩容。

如果是第一次添加，把默认值的赋值。

ArrayList小结：

JDK1.7 ArrayList源码分析：

JDK1.7情况下ArrayList list = new ArrayList();底层创建了一个长度为10的Object\[\]数组 ElementData。

list.add(123);// elementData\[0\] = new Integer(123);

...

list.add(11)；// 如果此次的添加导致底层elementData数组的容量不够，则扩容

默认情况下会扩容原来数组容量的1.5倍，同时将原有数组的数据复制到新的数组中。建议开发中带参数的构造器：ArrayList list = new ArrayList(int capacity);

JDK1.8 ArrayList的变化以及源码分析：

ArrayList list = new ArrayList();//底层是Object\[\] elementData初始化为\{\}，并没有创建。

当调用list.add(123)；// 第一次调用add的时候，底层才创建长度为10的数组，并将123添加elemrntData数组里。

// 后续扩容的操作和JDK 1.7相似。

小结：

jdk7中ArrayList的对象类似于单例模式的饿汉式，而jdk8中的ArrayList的对象的创建类似于单例模式中的懒汉式，延迟了数组的创建，节省内存。

LinkedList实现类的源码分析：

LinkedList底层是双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。同时，定义内部类Node，作为linkedList中保存数据的基本数据结构，Node除了保存数据，还定义的两个变量：① prev变量记录了前一个元素的位置 ② next变量记录了下一个元素的位置。

LinkedList是一个一个的结点组成的，结点是由Node来存储，分别记录链表的首末数组。使用泛型E定义存储。

链表中添加元素，也就是在链表的尾部添加元素。

LinkedList小结：

LinkedList list = new LinkedList();内部声明了Node类型的first和last属性，默认值为null。list.add(123)的时候，将123封装到Node中，创建了Node对象。

Vector实现类的源码分析：

Vector构造器，首先初始化容量为10

添加元素：

线程安全的

5、Collection子接口二：Set  
Set接口是Collection接口的子接口，类比List接口，Set接口是无序的，不可重复的。Set对象判断两个对象是否相同使用的方法是equals方法。

① HashSet:

HashSet底层是 数组 + 链表 形式，底层其实是HashMap

HashSet是Set接口的典型实现，大多数时候使用Set集合时，都使用的是这个类。HashSet按照Hash算法来存储集合中的元素，因此具有很好的存取、查找、删除的性能。

HashSet具有以下特点：不能保证元素的顺序排列，HashSet不是线程安全的，集合元素可以是null

HashSet集合判断两个元素相等的标准，两个对象通过hashCode()方法比较相等，并且两个对象的equals方法的返回值相等。

存放Set容器中的对象，对应的类一定要重写equals方法和hashCode(Object obj)方法，以实现对象的相等规则，即：相等的对象一定有相等的散列码。

关于equals和hashCode方法的重写,具体请访问 ：https://blog.csdn.net/Sunshineoe/article/details/115326777。其实HashSet底层是HashMap，包括equals和hashCode方法的重写。

② LinkedHashSet:

LinkedHashSet是HashSet的子类，LinkedHashSet根据元素的hashCode值来存储元素的存储位置，但他同时使用双向链表维护元素的次序，使元素插入的时候看起来有序。LinkedHashSet插入的性能低于HashSet，LinkedHashSet不允许元素重复。

③ TreeSet:

TreeSet是SortedSet接口的实现类，TreeSet可以确保元素集合处于排序状态，TreeSet的底层使用的是红黑树存储结构。红黑树有两种排序方式，自然排序和定制排序。也就是使用Comparable接口和Comparator接口，具体请访问：https://blog.csdn.net/Sunshineoe/article/details/115608592

（1）HashSet底层源码分析：添加元素的过程

向HashSet集合中添加元素a，首先调用元素a所在类的hashCode方法，计算元素的哈希值，通过计算元素的哈希值确定元素在HashSet底层数组中存放的位置（索引位置）。首先判断数组此位置上是否已经有了元素：

① 如果此位置上没有其他元素，那么就添加成功。

② 如果此位置上有其他元素（或者以链表形式存在的多个元素），则首先比较元素a和元素b的哈希值：

<1>如果元素a的哈希值不相同，则元素a添加成功

<2>如果元素的哈希值相同，进而需要调用元素a所在类的equals方法

（1）equals()方法返回true，元素a添加失败，说明元素的内容是否相同

（2）equals()方法返回false，元素添加成功，说明元素的内容是不一样的，说明添加成功。

（2）LinkedHashSet底层源码分析:添加元素的过程

LinkedHashSet添加元素的时候，使用的是双向链表。添加元素的位置是不确定的，但是添加元素的顺序是确定的。

（3）TreeSet底层源码分析:添加元素的过程

向TreeSet集合汇总添加数据，要求的是相同类的对象。其中两种排序方式：自然排序和定制排序。

在自然排序中，比较两个对象是否相同的标准是compareTo()返回0，不再是equals()比较 。

在定制排序中，比较两个对象是否相同的标准是，compare()返回值为0，不再是equals()比较

红黑树就是二叉树，其中二叉树满足的条件是：当前节点始终比左节点的值大，始终比右孩子的值大。

小结：

Set接口：存储无序的，不可重复的元素

HashSet：底层是HashMap实现的。作为Set接口的主要实现类，线程是不安全的，可以存储null值

LinkedHashSet：底层是链表结构。作为HashSet的子类，遍历其内部数据的时候，可以按照添加顺序遍历

TreeSet：底层是红黑树结构，按照对象的指定属性进行排序。比如Person类中属性有id,name；通过实现Comparable接口进行排序

在向Set中添加元素的时候，其所在的类一定要重写hashCode()方法和equals()方法。重写hashCode()和equals()方法尽可能的保持一致性，相等的对象一定要有相等的散列码。

7、Map集合

Map是双列数据，存储key-value的数据。

（1）HashMap：作为Map的主要实现类；线程是不安全的，效率高；存储null的key和value。

<1>LinkedHashMap：保证在遍历map元素时，按照元素添加的顺序进行遍历。

因为，在原有的HashMap底层结构上，添加了一对指针，指针指向前一个元素和后一个元素。对于频繁的遍历操作，此里的执行效率高于HashMap

（2）TreeMap，保证按照添加的key--value进行排序，实现了排序遍历。此时考虑key是自然排序或者的定制排序。TreeMap底层使用的是红黑树。

（3）HashTable，作为古老的实现类，线程是安全的，效率低，不能存储null值的key和value

Properities：常用来处理配置文件，key和value是String类型。

HashMap底层：

① 数组 + 链表（jdk 7之前）

② 数组 + 链表 +红黑树 （jdk 8 ）

Map集合的遍历方式：请访问：https://blog.csdn.net/Sunshineoe/article/details/115362216

相关常见面试题（下面有答案）：

① HashMap的底层实现原理？

② HashMap和HashTable之间的区别？

Map找那个有一个Entry集合，是存储key -value的存储。一个键值对就是一个Entry对象，使用Set进行存储。

Map结构的理解：

Map的key是无序的，可以重复的，使用Set存储所有的key，key所在的类要重写equals()和hashCode()

Map中的value是无序，可重复的，使用Collection存储所有的value，value所在类要重写equals方法

Map中常用的方法：

① HashMap的底层实现原理？

JDK7的情况：

HashMap map = new HashMap()

在实例化后，底层会创建了长度为16的一维数组Entry\[\] table，执行多次put操作之后。过程如下：

首先，调用key1所在类的hashCode()方法计算key1的哈希值，此哈希值通过一定的算法后，得到在Entry数组存放的位置。

如果此位置上数据为空，此时的key1-value1添加成功。

如果此位置的数据哈希值不为空，比较key1在这个位置上的哈希值，

<1>如果此位置上的哈希值与位置上存在的哈希值都不相同，此时key1-value1添加成功

<2>如果k1的值和已经存在的位置上的哈希值相等，则继续比较key1所在类的equals(key2)

如果equals返回的是false，此时key1-value1添加成功

如果equals返回true，使用value1，替换value2的值，也就是替换。

JDK8的情况：

（1）new HashMap()的时候：底层并没有创建一个长度为16的数组

（2）jdk8 底层数组是：Node\[\],而不是jdk7中的Entry \[\]

（3）jdk7的底层结构是数组+链表。jdk8中的底层结构：数组+链表+红黑树

（4）jdk8中，当数组的某个位置上的元素以链表形式存在的数据的个数 > 8，且当前数组的长度 > 64，此时此索引上的所有数据改为红黑树进行存储。

关于扩容问题：

默认扩容为原来容量的两倍，并将原有的数据复制过来。

jdk7中的Entry \[\] 数组

jdk 8中的情况

8、Collections工具类

Collections还提供了多个线程安全锁synchronoizedXxx（）方法，该方法可以将指定的集合包装成线程同步的集合，从而解决多线程的并发访问集合中的线程安全问题。

例如：

// 说明集合list1是线程安全的  
List list1 = Collections.synchronizedList(list);  
9、总结  
分时间段大概写了3天时间，终于写完了。

重点掌握List集合，Map集合，其中面试中最喜欢问的就是HashMap的底层原理，怎么结局hash冲突？currentHashMap和HashTable的区别，currentHashMap是线程安全的等等。

眼看还有3个月研一的生活就要结束了，然后去找实习。好快！加油呀！

————————————————  
版权声明：本文为CSDN博主「catchCode」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/Sunshineoe/article/details/115647716