Java集合框架史上最详解（list set 以及map）

2020-12-13

字数统计: 5k字 | 阅读时长≈ 18分

Java集合框架史上最详解（list set 以及map）

一、集合框架总体架构

1.1 集合框架在被设计时需满足的目标

①该框架必须是高性能的。基本集合（动态数组、链表、数、哈希表）的实现也必须是高效的；

②该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性；

③对一个集合的扩展和适应必须是简单的。

在了解并熟悉Java集合框架的时候，先了解其在被设计时需满足的目标是必须的。

1.2 所有的集合框架需要包含的内容

①接口：是代表集合抽象的数据类型。例如Collection、List、Set、Map等。之所以定义多个接口，是为了以不同的方式操作集合对象；

②实现（类）：是集合接口的具体体现。从本质上讲，它们是可重复的数据结构。例如ArrayList、LinkedList、HashSet以及HashMap；

③算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

集合框架体系如图所示：

1.3 Java集合框架图

先来看一张Java集合框架图：

上面这张图虽然详细讲述了Java集合框架，但是乍一看感觉太复杂了，那不妨来看一下下面的这张图，更能一眼就能清晰地明白Java集合框架了。

从上面的集合框架图可以看出，Java集合框架主要包括两种类型的容器，一种是集合（Collection），存放一个元素集合，另一种是图（Map），存储键–值对映射。Collection接口又有3种子类型，分别为List，Set以及Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。

1.4 常用的集合在系统中的区别

常用的集合在系统中定义了四大接口，这四类的区别是：

①Java.util.Set 接口及其子类，Set提供的是一个无序的集合，集合中的元素是不可以重复的，访问集合中的元素只能根据元素本身来访问（这也是集合里元素不允许重复的原因）；

②Java.util.List 接口及其子类，List提供的是一个有序的集合，集合中的元素是可以重复的，访问集合中的元素可以根据元素的索引来访问；

③Java.util.Queue接口及其子类，提供了基于队列的集合体系；

④Java.util.Map 接口及其子类，Map提供了一个映射（对应）关系的集合数据结构，访问时只能根据每项元素的key来访问其value；

每一种集合，都可以理解为是用来在内存中存放一组对象的某种”容器”—就像数组，就像我们自己定义的对列。

二、主要分析一下Set、List以及Map三个接口以及实现它们类的方法

2.1 Set接口及其实现类方法

2.1.1 Set接口

Set接口是一种不包括重复元素的Collection，是继承了Collection接口的子接口。 它维持它自己内部排序，所以对其进行随机访问没有任何意义。与List一样，它同样允许null的存在但仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素必须不同，同时也需要注意任何可变对象。它是一种最简单的集合，只是简单地将对象加入集合中，就好比往口袋里放东西，但是这里需要注意一下：虽然Set中元素没有顺序，但是元素在Set中的位置是由该元素的HashCode决定的，其具体的位置是固定的。它有三个具体的实现类，分别为散列集HashSet、链式散列集LinkedHashSet以及树形集TreeSet。

1）HashSet

HashSet 是一个没有重复元素的集合。它是由HashMap实现的，**不保证元素的顺序(这里所说的没有顺序是指：元素插入的顺序与输出的顺序不一致)**，而且HashSet允许使用null 元素。HashSet是非同步的，如果多个线程同时访问一个哈希set，而其中至少一个线程修改了该set，那么它必须保持外部同步。 HashSet按Hash算法来存储集合的元素，因此具有很好的存取和查找性能。

HashSet使用和理解中容易出现的误区:

a.HashSet中存放null值

HashSet中是允许存入null值的，但是在HashSet中仅仅能够存入一个null值。

b.HashSet中存储元素的位置是固定的

HashSet中存储的元素的是无序的，这个没什么好说的，但是由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的。

HashSet的实现方式大致如下，通过一个HashMap存储元素，元素是存放在HashMap的Key中，而Value统一使用一个Object对象。

c.必须小心操作可变对象（Mutable Object）

如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题

2）LinkedHashSet

LinkedHashSet继承自HashSet，其底层是基于LinkedHashMap来实现的，有序，非同步。LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

3）TreeSet

TreeSet是一个有序集合，其底层是基于TreeMap实现的 ， 非线程安全。TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。当我们构造TreeSet时，若使用不带参数的构造函数，则TreeSet的使用自然比较器；若用户需要使用自定义的比较器，则需要使用带比较器的参数。

注意： TreeSet集合不是通过hashcode和equals函数来比较元素的.它是通过compare或者comparaeTo函数来判断元素是否相等.compare函数通过判断两个对象的id，相同的id判断为重复元素，不会被加入到集合中。

2.1.2 Set接口的用法

Set是一个接口定义，所以我们只能使用它的实现子类。Set接口常用的子类有散列集HashSet、链式散列集LinkedHashSet以及树形集TreeSet。使用起来也非常的简单，请看以下的代码：

package com.yf1213.Test;

import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class SetTest{
    //程序的入口
    public static void main(String[] args){
        SetTest test = new SetTest();
        Collection sSet = test.getUserSet(3);
        System.out.println("集合中共有元素：" + sSet.size());

        //将Set中的所有元素取出来打印
        //又因为Set中的元素是无序的，所以不能通过索引取得，故使用Set的迭代器
        Iterator<Student> it = sSet.iterator();

        //遍历
        while(it.hasNext()){
            Student st = it.next();
            st.showInfo();
        }
    }

    /*
    * 取得指定数量UserInfo对象
    * @param UserCount：要创建的个数
    * @return
    * */

    public Collection getUserSet(int userCount){
        //创建一个集合对象
        Set sSet = new HashSet();
        for(int i=0; i<userCount; i++){
            Student ui = new Student("用户_"+((char)(65+i)), i+1);
            sSet.add(ui);
        }
        return sSet;
    }
}

注意： 上述代码中 ui.setName(“用户_”+((char)(65+i)));这句， char 型强制转型，得到一个 int 值对应 ASCLL 码的字符，所以我们看到输出的是 A、 B、 C；这是因为这三个字符对应的 ASCLL 码值是 65,66,67。

Student类如下：

package com.yf1213.Test;

public class Student {
	
	private String name;
	private int scroe;
	
	//创建学生对象，传入姓名和学分值
	public Student(String name, int scroe) {
		
		this.name = name;
		this.scroe = scroe;
	}
	
	//输出学生的基本信息
	public void showInfo() {
		System.out.println("姓名："+name+"学分："+scroe);
	}	
}

输出的结果：

集合中共有元素：3
姓名：用户_A学分：1
姓名：用户_C学分：3
姓名：用户_B学分：2

从上述的代码以及输出的结果，可以知道，Set的特点是无序的，所以要取出其中的对象，必须通过Set对象，得到Iterator来遍历这个Set。

同样也能够去看到，我们在集合中放入的对象是有次序的，但在打印时，却不是我们所放入进去的次序，这就能够去说明集合中的对象是无序的，至于它的真实顺序，只有在打印的时候才能得知，在未打印前，并不能真正得到它顺序的。

2.2 List接口以及实现类方法

2.2.1 List接口

List集合代表一个有序集合，集合中每个元素都有其对应的顺序索引。List集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。

List接口继承于Collection接口，它可以定义一个允许重复的有序集合。因为List中的元素是有序的，所以我们可以通过使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

List接口为Collection直接接口。List所代表的是有序的Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

1)ArrayList

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。

ArrayList擅长于随机访问。同时ArrayList是非同步的。

2)LinkedList

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。

由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双重链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List： List list = Collections.synchronizedList(new LinkedList(…));

3)Vector

与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

4)Stack

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

2.2.2 List接口的用法

相对于无序的Set接口，List接口提供多个实现的子类，提供有序的访问集合中的方法，换言之，就是可以根据List中对象放入时的次序来查找对象。List常用的实现类是Vector和ArrayList。代码如下：

package com.yf1213.Test;

import java.util.ArrayList;
import java.util.List;

public class ListTest {
	public static void main(String[] args) {
		ListTest st = new ListTest();
		List<Student> list = st.getUserList(5);
		System.out.println("List中共有元素："+list.size());
		
		//取出list中某个位置的元素：
	    Student sd = list.get(3);
	    sd.showInfo();
	    
	    //输出列表中所有Student对象信息：
	    st.printList(list);
	
	}
	
	/*
	 * 打印出List中对象的内容
	 * */
	public void printList(List<Student> list) {
		for(int i=0; i<list.size(); i++){
			Student us = list.get(i);
			us.showInfo();
		}
	}
	
	/*
	 * 
	 * 取出特定数量Student对象的一个List集合
	 * userCount：要创建的用户个数
	 * */
	
	public List<Student> getUserList(int userCount){
		List userList = new ArrayList();
		for(int i=0; i<userCount; i++) {
			Student ui = new Student("用户_"+((char)(65+i)), i+1);
			userList.add(ui);
		}
		return userList;
	}
}

里面所用的Student类跟之前的是一样的，之后的也一样，这里就赘述了！！！

输出的结果为：

List中共有元素：5
姓名：用户_D学分：4
姓名：用户_A学分：1
姓名：用户_B学分：2
姓名：用户_C学分：3
姓名：用户_D学分：4
姓名：用户_E学分：5

从输出的结果可以看出，List接口一个有序的集合，可以通过其索引（即元素在List中的位置，类似于数组的下标）来访问List中的元素的。

2.3 Map接口与其使用方法

2.3.1Map接口

Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了key到Value的映射。同时它也没有继承Collection。在Map中它保证了key与value之间的一一对应关系。也就是说一个key对应一个value，所以它不能存在相同的key值，当然value值可以相同。就好比我们再现实生活中，经常也会看到类似这样的集合，比如IP地址与主机名，身份证号码与个人等等这样一一对应关系的例子，这也就叫做映射。在Java中，专门提供了这样的集合用来存放这种对象关系的对象，即为java.util.Map接口。常常Map接口的实现类主要有：HashMap、LinkedHashMap以及TreeMap的。

①HashMap

以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry[] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。

②LinkedHashMap

LinkedHashMap是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用LinkedHashMap。
LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
根据链表中元素的顺序可以分为： 按插入顺序的链表，和按访问顺序(调用get方法)的链表。默认是按插入顺序排序，如果指定按访问顺序排序，那么调用get方法后，会将这次访问的元素移至链表尾部，不断访问可以形成按访问顺序排序的链表。
注意： 此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
由于LinkedHashMap需要维护元素的插入顺序，因此性能略低于HashMap的性能，但在迭代访问Map里的全部元素时将有很好的性能，因为它以链表来维护内部顺序。

③TreeMap

TreeMap 是一个有序的key-value集合，非同步，基于红黑树（Red-Black tree）实现，每一个key-value节点作为红黑树的一个节点。TreeMap存储时会进行排序的，会根据key来对key-value键值对进行排序，其中排序方式也是分为两种，一种是自然排序，一种是定制排序，具体取决于使用的构造方法。

自然排序： TreeMap中所有的key必须实现Comparable接口，并且所有的key都应该是同一个类的对象，否则会报ClassCastException异常。

定制排序： 定义TreeMap时，创建一个comparator对象，该对象对所有的treeMap中所有的key值进行排序，采用定制排序的时候不需要TreeMap中所有的key必须实现Comparable接口。

TreeMap判断两个元素相等的标准： 两个key通过compareTo()方法返回0，则认为这两个key相等。

如果使用自定义的类来作为TreeMap中的key值，且想让TreeMap能够良好的工作，则必须重写自定义类中的equals()方法，TreeMap中判断相等的标准是：两个key通过equals()方法返回为true，并且通过compareTo()方法比较应该返回为0。

2.3.2 Map接口的用法

在Map中存放的是两种对象，一种称为key（键），另一种成为value（值），它们在Map中是一一对应的关系，这样一对对象又称为Map中的一个Entry（项）；Map中的key是不能够重复的，但是值是可以重复的。下面是实现Map接口的实现类方法。

package com.yf1213.Test;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class MapTest {
	
	public static void main(String[] args) {
		MapTest mt = new MapTest();
		Map<String, Student> map = mt.createUserTable();
		//打印Map中所有的信息：
		mt.printMap(map);
		
		//根据已知的key取出map中对应的一个value：
		String key = ""+2;
		System.out.println("取出的key为"+key+"对象的信息是：");
		Student st = map.get(key);
		st.showInfo();
	}
	
	/*
	 * 创建用户与名字关系的Map对象
	 * 返回：用户名字与用户对象关联的Map对象
	 * */
	
	public Map<String, Student> createUserTable(){
		Map userMap = new HashMap();
		for(int i=0; i<6; i++) {
			Student us = new Student("我是第"+(i+1)+"个", i);
			userMap.put(""+i, us);
		}
		return userMap;
	}
	
	/*
	 * 遍历Map
	 * 
	 * */
	
	public void printMap(Map<String, Student> um) {
		//得到Map中所有的key的集合
		Set<String> set = um.keySet();
		Iterator<String> it = set.iterator();
		
		//迭代key
		while(it.hasNext()) {
			String key = it.next();
			//取出key对应的value
			Student uf = um.get(key);
			uf.showInfo();
		}
	}
}

输出的结果：

姓名：我是第1个学分：0
姓名：我是第2个学分：1
姓名：我是第3个学分：2
姓名：我是第4个学分：3
姓名：我是第5个学分：4
姓名：我是第6个学分：5
取出的key为2对象的信息是：
姓名：我是第3个学分：2

从输出的结果看，我们可以通过key的值来找到value的值，它们是一一对应的关系。

本文作者： feng之锋
本文链接： http://example.com/2020/12/13/Java集合框架 list-set-map /
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！