Java集合容器——List、Set、Map（详细解析）

Bertha 。 2023-02-13 11:56 115阅读 0赞

**目录**

前言

一、Collection

二、Map

三、扩容机制

四、数据结构

--------------------

# 前言 #

在编程时，可以使用数组来保存多个对象，但数组长度不可变化，一旦在初始化数组时指定了数组长度，这个数组长度就是不可变的。如果需要保存数量变化的数据，数组就有点无能为力了。而且数组无法保存具有映射关系的数据，如成绩表为语文——79，数学——80，这种数据看上去像两个数组，但这两个数组的元素之间有一定的关联关系。  
  
为了保存数量不确定的数据，以及保存具有映射关系的数据（也被称为关联数组），[Java][] 提供了集合类。集合类主要负责保存、盛装其他数据，因此集合类也被称为容器类。Java 所有的集合类都位于 java.util 包下，提供了一个表示和操作对象集合的统一构架，包含大量集合接口，以及这些接口的实现类和操作它们的算法。  
  
集合类和数组不一样，**数组元素既可以是基本类型的值，也可以是对象**（实际上保存的是对象的引用变量），而**集合里只能保存对象**（实际上只是保存对象的引用变量，但通常习惯上认为集合里保存的是对象）。

### Java 集合类型分为 Collection 和 Map，它们是 Java 集合的根接口，这两个接口又包含了一些子接口或实现类。接下来，将细讲Collection和Map。 ###

# 一、Collection #

## 概述： ##

collection接口是集合框架的顶级接口（set与list的父接口，不是map集合的父接口）

*  List , Set继承至Collection接口
 *  Set下主要有HashSet，LinkedHashSet，TreeSet
 *  List下主要有ArrayList，Vector，LinkedList
 *  Collection接口下还有个Queue接口，有PriorityQueue类、ArrayDueue类
 *  Queue、List、Set是同一级别的，都是继承了Collection接口。
 *  LinkedList同时实现了Queue和List接口，其实Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。

## ![format_png][] ##

## List 有序,可重复 ##

ArrayList  
        特点: 底层数据结构是数组，查询快，增删慢。

线程不安全，效率高。

Vector  
        特点: 底层数据结构是数组，查询快，增删慢。

线程安全，效率低。

LinkedList  
        特点: 底层数据结构是链表，查询慢，增删快。

线程不安全，效率高。

##    Set 唯一（不重复） ##

HashSet  
        底层数据结构是哈希表。(唯一，无序)  
        如何来保证元素唯一性?  
        1.依赖两个方法：hashCode()和equals()

LinkedHashSet  
        底层数据结构是链表和哈希表。(唯一，有序)  
        1.由链表保证元素有序（FIFO先入先出队列）  
        2.由哈希表保证元素唯一

TreeSet  
        底层数据结构是红黑树。(唯一，有序)  
        1. 如何保证元素排序的呢?  
            自然排序  
            比较器排序  
        2.如何保证元素唯一性的呢?  
            根据比较的返回值是否是0来决定

补充说明：

*  TreeSet的主要功能用于排序
 *  TreeSet做范围查询效率较高，在数据库的索引中，范围查询较多，所以树结构主要用来做索引，来提高查询效率。  
     
 *  HashSet只是通用的存储数据的集合
 *  HashSet是最常用的，做等值查询效率最高，在开发中，最常用到的就是等值查询。  
     
 *  LinkedHashSet的主要功能用于保证FIFO即有序的集合(先进先出)
 *  LinkedHashSet在一个集合既不能元素重复，又要记录元素的添加顺序时使用。一般使用较少。

*  HashSet和LinkHashSet**允许存在null**数据，但是TreeSet中插入null数据时会报NullPointerException
 *  三者都不是线程安全的，如果要使用线程安全可以 Collections.synchronizedSet()
 *  三者数据插入速度对比：HashSet（无序） > LinkHashSet（FIFO队列） > TreeSet（内部排序）

**注意：这里关于Set，我们先来了解四个问题  
    1、HashSet为什么是无序的  
    2、LinkedHashSet和TreeSet是有序的，具体是怎么实现的  
    3、TreeSet的两种排序方式怎么实现  
    4、三者的插入性能比较**

## ##

## 1、HashSet为什么是无序的 ##

有序、无序是指在进行插入操作时，插入位置的顺序性

先插的位置在前，后插的位置在后，则为有序，反之无序

那我们举个例子，为什么HashSet是无序的

Set<String> set = new HashSet<String>();
    set.add("hello");
    set.add("hello");//重复元素
    set.add("java");
    set.add("world");
    System.out.println(set);//[java, world, hello]

1）先看下HashSet的add源码，会发现，该方法是将数据值存入到HashMap的key中，到这里我们就明白了，HsahMap在保存数据时，顺序是通过计算key的hash值和当前数组长度的 **&** 运算，计算保存数据的下标位置，**所以说set是无序的**。

public boolean add(E e) {
            return map.put(e, PRESENT)==null;
    }

2）我们可以点进去验证一下put方法实现原理

public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
    }

static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

## 2、LinkedHashSet和TreeSet是有序的，具体是怎么实现的 ##

这里我们对LinkedHashSet、TreeSet以及HashSet的排序做个测试，代码如下：

public static void main(String[] args) {
            HashSet<String> hashSet = new HashSet<>();
            LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
            TreeSet<String> treeSet = new TreeSet<>();
    
            for (String data : Arrays.asList("hello","hello", "world", "java")) {
                hashSet.add(data);
                linkedHashSet.add(data);
                treeSet.add(data);
            }
    
            //不保证有序
            //输出：HashSet :[world, java, hello]
            System.out.println("HashSet :" + hashSet);
    
            //FIFO先入先出队列
            //输出：LinkedHashSet :[hello, world, java]
            System.out.println("LinkedHashSet :" + linkedHashSet);
    
            //内部实现排序
            //默认进行正序排列,因为这里是字符串，所以是按首字母排序的
            //输出：TreeSet :[hello, java, world]
            System.out.println("TreeSet :" + treeSet);
    }

## 结论： ##

*  HashSet：无序（key的hash值和当前数组长度的 **&** 运算），不重复
 *  LinkedHashSet：有序（FIFO先入先出队列），不重复
 *  TreeSet：有序（自然排序和比较器排序），不重复

## 3、TreeSet的两种排序方式怎么实现 ##

在讲TreeSet两种排序前我们先做两个测试：

### 3.1基本数据类型的排序 ###

public static void main(String[] args) {
    
            // 自然顺序进行排序
            TreeSet<Integer> ts = new TreeSet<Integer>();
            // 添加元素
            ts.add(1);
            ts.add(18);
            ts.add(23);
            ts.add(22);
            ts.add(17);
            ts.add(24);
            ts.add(19);
            ts.add(18);
            ts.add(2);
    
            // 遍历
            //输出: 1,2,17,18,19,22,23,24,
            for (Integer i : ts) {
                System.out.print(i+",");
            }
    
    }

结果为： 1,2,17,18,19,22,23,24,

由于TreeSet可以实现对元素按照某种规则进行排序，所以我们这里看到的是正常的排序。

### 3.2 如果是引用数据类型呢,比如自定义对象,又该如何排序呢? ###

3.2.1 错误示范

测试类代码：

import java.util.TreeSet;
    
    /**
     * @author sunlee
     * @date 2020/5/30 12:27
     */
    public class MyCollectionTest {
    
        public static void main(String[] args) {
    
            TreeSet<Student> ts=new TreeSet<Student>();
            //创建元素对象
            Student s1=new Student("sun",12);
            Student s2=new Student("zhaoxin",2);
            Student s3=new Student("manw",45);
            Student s4=new Student("weien",78);
            Student s5=new Student("sun",01);
            Student s6=new Student("timo",100);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
        }
    }

Student类：

public class Student {
        private String name;
        private int age;
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    }

结果报错：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODc1OTQ0OQ_size_16_color_FFFFFF_t_70][]

原因分析：内部不知道该按照那一种排序方式排序，所以报错。

解决方法：1.自然排序     2.比较器排序

**3.2.2 自然排序**

自然排序要进行以下操作：

1.Student类中实现 Comparable接口

2.重写Comparable接口中的Compareto方法

public class Student implements Comparable<Student>{
        private String name;
        private int age;
    
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        @Override
        public int compareTo(Student o) {
           //return -1; //-1表示放在红黑树的左边,即逆序输出
            //return 1;  //1表示放在红黑树的右边，即顺序输出
            //return o;  //表示元素相同，仅存放第一个元素
            //主要条件 姓名的长度,如果姓名长度小的就放在左子树，否则放在右子树
            int num=this.name.length()-s.name.length();
            //姓名的长度相同，不代表内容相同,如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数。
            //如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数。
            //如果这两个字符串相等，则结果为 0
            int num1=num==0?this.name.compareTo(s.name):num;
            //姓名的长度和内容相同，不代表年龄相同，所以还要判断年龄
            int num2=num1==0?this.age-s.age:num1;
            //说白了就是按照：姓名长度->姓名字符顺序->年龄 来排序
            return num2;
        }
    }

测试类：

public static void main(String[] args) {
    
            TreeSet<Student> ts=new TreeSet<Student>();
            //创建元素对象
            Student s1=new Student("sun",12);
            Student s2=new Student("zhaoxin",2);
            Student s3=new Student("manw",45);
            Student s4=new Student("weien",78);
            Student s5=new Student("sun",01);
            Student s6=new Student("timo",100);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
    }

运行结果：

sun-----------1
    sun-----------12
    manw-----------45
    timo-----------100
    weien-----------78
    zhaoxin-----------2

**3.2.2 比较器排序**

比较器排序步骤：

1.单独创建一个比较类，这里以MyComparator为例，并且要让其继承Comparator接口

2.重写Comparator接口中的Compare方法

3.在主类的创建实例中使用自定义比较器

代码如下：

Student类：

public class Student {
        private String name;
        private int age;
    
        public Student() {
            super();
            // TODO Auto-generated constructor stub
        }
    
        public Student(String name, int age) {
            super();
            this.name = name;
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
    }

自定义的MyComparator比较器：

import java.util.Comparator;
    
    public class MyComparator implements Comparator<Student> {
    
        @Override
        public int compare(Student s1,Student s2) {
            // 姓名长度
            int num = s1.getName().length() - s2.getName().length();
            // 姓名内容
            int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
            // 年龄
            int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
            return num3;
        }
    
    }

测试类：

public static void main(String[] args) {
    
            //主要加了这一句：new MyComparator()，其他不变
            TreeSet<Student> ts=new TreeSet<Student>(new MyComparator());
    
            //创建元素对象
            Student s1=new Student("sun",12);
            Student s2=new Student("zhaoxin",2);
            Student s3=new Student("manw",45);
            Student s4=new Student("weien",78);
            Student s5=new Student("sun",01);
            Student s6=new Student("timo",100);
    
            //将元素对象添加到集合对象中
            ts.add(s1);
            ts.add(s2);
            ts.add(s3);
            ts.add(s4);
            ts.add(s5);
            ts.add(s6);
    
            //遍历
            for(Student s:ts){
                System.out.println(s.getName()+"-----------"+s.getAge());
            }
    }

运行结果：

sun-----------1
    sun-----------12
    manw-----------45
    timo-----------100
    weien-----------78
    zhaoxin-----------2

## 4、三者的插入性能比较 ##

HashSet、TreeSet、LinkedHashSet性能对比

代码如下：

实体类 Dog：

class Dog implements Comparable<Dog> {
        int size;
    
        public Dog(int s) {
            size = s;
        }
    
        public String toString() {
            return size + "";
        }
    
        @Override
        public int compareTo(Dog o) {
            //数值大小比较
            return size - o.size;
        }
    }

测试类 PerformanceTest ：

import java.util.HashSet;
    import java.util.LinkedHashSet;
    import java.util.Random;
    import java.util.TreeSet;
    
    /**
     * @author sunlee
     * @date 2020/5/30 13:08
     */
    public class PerformanceTest {
    
        public static void main(String[] args) {
    
            Random r = new Random();
    
            HashSet<Dog> hashSet = new HashSet<Dog>();
            TreeSet<Dog> treeSet = new TreeSet<Dog>();
            LinkedHashSet<Dog> linkedSet = new LinkedHashSet<Dog>();
    
            //hashSet---------------------------------------------------
            long startTime = System.nanoTime();
            for (int i = 0; i < 10000; i++) {
                int x = r.nextInt(10000 - 10) + 10;
                hashSet.add(new Dog(x));
            }
            // end time
            long endTime = System.nanoTime();
            long duration = endTime - startTime;
            System.out.println("HashSet: " + duration);
    
            //treeSet---------------------------------------------------
            startTime = System.nanoTime();
            for (int i = 0; i < 10000; i++) {
                int x = r.nextInt(10000 - 10) + 10;
                treeSet.add(new Dog(x));
            }
            endTime = System.nanoTime();
            duration = endTime - startTime;
            System.out.println("TreeSet: " + duration);
    
            //linkedSet---------------------------------------------------
            startTime = System.nanoTime();
            for (int i = 0; i < 10000; i++) {
                int x = r.nextInt(10000 - 10) + 10;
                linkedSet.add(new Dog(x));
            }
            endTime = System.nanoTime();
            duration = endTime - startTime;
            System.out.println("LinkedHashSet: " + duration);
        }
    }

输出结果：

HashSet: 9319822
    TreeSet: 14542598
    LinkedHashSet: 8672281

插入速度： HashSet>LinkHashSet>TreeSet

总结：TreeSet最慢，因为内部进行排序。

# 二、Map #

![format_png 1][]

Map接口有三个比较重要的实现类，分别是**HashMap**、**TreeMap**和**HashTable**。

**TreeMap**：有序（基于红黑树对所有的key进行排序）、非线程安全、没有调优选项（因为该树总处于平衡状态）、不允许key值为null

**HashMap**：无序、方法不同步、非线程安全、效率较高、允许null值（key和value都允许）

**HashTable**：无序、方法同步、线程安全、效率较低、不允许key值为null

补充：

*  Hashtable的父类是**Dictionary**，HashMap的父类是**AbstractMap**
 *  HashMap：适用于Map中插入、删除和定位元素；对同步性或与遗留代码的兼容性没有任何要求时
 *  Treemap：适用于按自然顺序或自定义顺序遍历键(key)。

# 三、扩容机制 #

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODc1OTQ0OQ_size_16_color_FFFFFF_t_70 1][] #

# 四、数据结构 #

ArrayXxx:底层数据结构是数组，查询快，增删慢

LinkedXxx:底层数据结构是链表，查询慢，增删快

HashXxx:底层数据结构是哈希表。依赖两个方法：hashCode()和equals()

TreeXxx:底层数据结构是二叉树。两种方式排序：自然排序和比较器排序

[Java]: http://c.biancheng.net/java/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2MuYmlhbmNoZW5nLm5ldC91cGxvYWRzL2FsbGltZy8xOTEyMDUvNS0xOTEyMDUxMDM2MzMzVi5wbmc?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODc1OTQ0OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530123040165.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODc1OTQ0OQ==,size_16,color_FFFFFF,t_70
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2MuYmlhbmNoZW5nLm5ldC91cGxvYWRzL2FsbGltZy8xOTEyMDUvNS0xOTEyMDUxMDNHNTk2MC5wbmc?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODc1OTQ0OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531120300428.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODc1OTQ0OQ==,size_16,color_FFFFFF,t_70