♥6000字介绍集合框架下的List，Set，Map以及支持类Collections【Java养成】

Java学习打卡：第三十天

内容导航

- 表（List）List< E>
- - 数组表ArrayList
  - - linkedList也实现了Deque接口
  - 向量Vector和栈Stack
  - - 数据结构Stack经典问题
- 集（set) Set< E>
- - 散列集和链式散列集
  - - 树型集treeSet
- 图（Map）
- - - 映射的实现类
- 支持类Collections

Java养成计划（打卡第30天)

内容管理：最后一点点内容，介绍集合框架下面的几种数据结构

先来看一下总的集合框架，这是UML表示，Map是键值对，Collection是键值

是不是看着非常的直观，在数据结构中，Queue就是队列，Stack就是栈，linkedList就是链表，ArrayList就是顺序表

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-N7ss5Avg-1634132990423)(C:UsersOMEY-PCAppDataRoamingTyporatypora-user-imagesimage-20211012220211691.png)]

表（List）List< E>

表是一种有序集合，每一个元素都由一个位置下标。学过数据结构就直到除了普通的顺序表，还有LIFO,FIFO表，这些表结构接下来都会一一提到

表的特点：表支持面向位置的操作，用户可以将元素插入指定的位置，向AbstractCollection就没有面向位置，用户也可以访问指定位置的元素。与集（set）不同，表允许出现重复的元素。表涉及的接口和类

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CaQHgWnO-1634132990425)(C:UsersOMEY-PCAppDataRoamingTyporatypora-user-imagesimage-20211012220633885.png)]

从这张Picture可以看到List继承了Collection，关联的迭代器是ListIterator【都是接口】，之后就是有相应的适配器抽象容器，抽象表，还有一个抽象顺序表AbstractSequentialList继承抽象表，其中链式表实现的就是该抽象顺序表，ArrayList和Vector继承的是普通抽象表，之后有Stack继承该Vector；这所有的表都有迭代器

List接口扩展Collection接口，是所有表的根接口

增加的方法主要是面向位置的一些方法，就可以在指定位置操作

void add(int index,E element); //指定位置插入元素
E get(int index); //指定位置的元素
int indexOf(Object o); //指定元素第一次出现的位置
ListIterator listIterator(int startIndex); //返回当前表的表迭代器，参数指定为第一次调用时next方法的下标
List subList(int fromIndex,int toIndex); //获取子表
····

对于equals方法具体就是对象地址相同，都是表，且表对应位置的元素相同

对于iterator除了返回普通的迭代器之外，还可以返回一个表迭代器，该迭代器支持双向遍历

ListIterator接口扩展Iterator接口

ListIterator< E> listIterator(int startIndex);//确定迭代器最开始游标的位置

//hasnext，next，remove
boolean hasPrevious(); //是否有上一个元素
void add(E,e); //向表中插入一个元素
void set(E e); //替换由next或者previous返回的元素【就是游标位置】add也是
int nextIndex(); //返回下一个元素的位置

AbstractList也是对与该接口的实现，其中也只是size和get方法没有实现，并且set，remove，add都只是简单抛出了例外。

可以扩展该类来实现随机存取的表类，那么还应该覆盖set，remove和add提供具体的实现

AbstractSequentialList是Abstract的抽象子类，适合当作那些元素存储便于顺序访问的表的超类，特点是将listIterator声明为抽象的，而get，set，add，remove则是实现了的，要定义适合顺序访问的表类，可以扩展该抽象类，提供size和listIterator的实现

数组表ArrayList

通过上面的表的接口可以看出ArrayList和linkedList是实现List接口的具体两个实现类，在内部，数组表采用数组存储表的元素，而链式表则采用双向链表存储表的元素，如果需要使用下标随机访问元素，并且除了末尾之外，不在其他位置插入或者删除元素，应该考虑使用数组表。如果需要在任意位置插入元素，应该考虑链式表

一个绕的疑问：既然ArrayList和linkedList都是List的实现类，那么都可以实现插入操作，那为什么还要区分两者呢？

这就像普通接口的实现，虽然接口中的声明是一样的，但是实现的方式可能是不一样的，这里比如add(int index,E element); 就是在某一个位置插入元素，两种实现都可以实现，只是效率不一样。

就是数据结构中的顺序表和链表，它们都是可以实现在任意位置插入删除的；只是顺序表会耗时间一些，仅此而已，所以我们使用数据时就要考虑一下选用哪种数据结构

链式表占用的空间要大一些，存储效率低一些，除了数据之外，还有两个指针（引用），就是双链表的结构，实现方式就是之前的QueueNode那样子。

数组表的构造方法有几种

ArrayList(); //创造一个初始容量为10的空数组表
ArrayList(Collection
ArrarList(int initalCapacity); //创建一个指定容量的空数组表

【其实这就是顺序表和链表的区别，存储的结构不一样】只是java中封装了，都是数据结构中的基础知识

LinlkedList(); //构造一个空链式表
linkedList(Collection

参数化类型ArrayList< Integer>是List< Integer>的子类，由于泛型一旦指定就不能更改，所以List< X>中x就是Integer，不会是非Integer，所以强制类型转换不会报错，（类和类才存在继承和强制类型转换，而同一个泛型有类型擦除技术，是同样的.class文件，不存在继承之类的问题）

linkedList也实现了Deque接口

所以linkedList也提供了一些双向队列的操作（double ended queue)

public interface Dequeextends Queue{
    int size();
    void addFirst();
    void addLast();
    E getFirst();
    E getLast();
    E removeFirst(); //删除并返回第一个元素
    E removeLast();
}

这里涉及的数据接口就是队列FIFO表，队尾插入，队首删除，所以调用addLast,和removeFirst就是入队和出队，具体的实现可以看源码，等之后讲解数据结构时，就会具体讲解。

向量Vector和栈Stack

Vector继承AbstractList，Stack又继承Vector ，需要注意的时Vector和Stack是同步的，【加上synchronized修饰】这里和之前生产者和消费者中的Queue一样，防止多线程引起的数据冲突（当时模拟过）

与ArrayList一样，Vector也采用数组存储元素，向量的容量可以根据需要任意动态伸缩，且一定不会小于向量的大小构造方法和linkedList一样是三个

Vector();
Vector(Collection
Vector(int initalCapacity);

栈Stack是对Vector的扩展，新增栈的操作方法

public class Stack extends Vector{
	public Stack(); //空栈
    public E push(E item); //栈顶压入元素
    public E pop(); //返回并返回栈顶
    public E peek(); //返回栈顶元素
    boolean isEmpty(); //栈空
    public int search(Object o); //返回指定元素在栈的位置，栈顶为1
}

数据结构Stack经典问题

括号匹配，给出一串表达式，如果不匹配就报错，匹配就不报错

package Luogu;

import java.util.*;

public class ContainerDemo {
	public static boolean match(Character b,Character a)//注意顺序
	{
		if(a == '('&&b == ')')
			return true;
		if(a == '['&&b == ']')
			return true;
		if(a == '{'&&b == '}')
			return true;
		return false;
		
	}
	public static void isMatch(String str)
	{//给的是字符串，但入栈的是字符，使用包裹体
		Stack stack = new Stack(); //空栈
		Character c;
		for(int i = 0;i < str.length();i++)//之前没有lenth方法，只能while，这里就直接用方法 lenth是长度，size是容量
		{
			c = str.charAt(i); //获取字符
			switch(c){
				case '(':
				case '[':
				case '{':
					stack.push(c); //入栈
					break;
				case ')':
				case ']':
				case '}':
					if(stack.isEmpty())
					{
						System.out.println("右括号多余");
					    return; //防止重复输出
					}
					if(match(c,stack.peek()))
					{
						stack.pop();//出栈
						break;
					}
					else {
						System.out.println("不匹配");
					    return; //防止重复输出
					}
			}
		}
		if(!stack.isEmpty())
			System.out.println("左括号多余");
		else 
			System.out.println("匹配呢");
	}
	
	public static void main(String[] args) {
		isMatch("{3+5}");
		isMatch("[(3+5)");
		isMatch("[3+5)");
		isMatch("[(3+5)]}");
  }
}//任何问题都是值得重视的
//这里match时注意顺序，还有就是方法体中，逻辑运算符的运用

输出结果为

匹配呢
左括号多余
不匹配
右括号多余

集（set) Set< E>

集就是数学中的集合，集合中不能包含相同元素，所以如果存储数据需要相同数据就只能使用表了，一个集中不能存在时式子el.equals(e2)成立的e1,e2，一个集中最多只能包含一个null元素,因为不重复呢

从上面的总图可以看出，集也是继承的Clloection

集所涉及的主要接口和类

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sPSOtOvg-1634132990427)(file:///C:UsersOMEY-PCdocumentsTencent Files1589827479ImageC2C1D642008C54073A404C1092EA64DC391.jpg)]

Set接口扩展Collection接口，是所有集的根接口，但是并没有扩展增加新的方法，但是对与一些方法做了新的约定

add(E e) 方法向集中添加指定元素，若集中已经包含该元素，则不做添加操作，直接返回false
equals(Object o) 测试当前集与参数对象o是否相等。若参与对象o也是一个集且其所有元素多存在于当前集、两个集的元素个数相等，则返回true
hasCode() 返回集的散列码，一个集的散列码等于所有元素的散列码之和。【这里可以去了解哈希表】

AbstractSet是一个扩展AbstractCollection类并实现Set接口的抽象类。但是**除了对从AbstractCollection类继承而来的equals方法和hashCode方法进行覆盖、提供特定的实现之外，该抽象类没有做更多的工作

散列集和链式散列集

Hash（散列，哈希），HashSet类扩展AbstractSet抽象类，是一个基于哈希表技术实现的Set接口的具体类，散列集的元素是没有顺序的，不能保证其迭代器按照某种次序返回元素，散列集包含null元素

散列集的构造方法为

HashSet(); //创建一个空散列集，初始容量为16，装填因子为0.75
HahSet(int initalCapacity); //创建一个由指定初始容量的空散列集，装填因子为0.75
HashSet(int initalCapacity, floatFactor);// 创建一个指定初始容量和指定装填因子的空散列集
HashSet(Collection c); //创建一个指定集合元素的散列集，状态因子为0.75

散列集的迭代器遍历元素的效率与散列集的容量成正比，因此不应该设置太大的初始容量（或太小的装填因子）

链式散列集linkedList类扩展HashSet类，是一个基于散列表技术和链表技术实现的Set接口的具体类，链式散列集是有顺序的，其迭代器可以按元素插入集合的顺序返回各元素。链式散列集允许包含null元素

链式散列集的构造方法为

linkedHashSet(); //创建一个空链式散列集，初始容量为16，装填因子为0.75
linkedHahSet(int initalCapacity); //创建一个由指定初始容量的空链式散列集，装填因子为0.75
linkedHashSet(int initalCapacity, floatFactor);// 创建一个指定初始容量和指定装填因子的空链式散列集
linkedHashSet(Collection c); //创建一个指定集合元素的链式散列集，状态因子为0.75

关于集合的底层实现到数据结构就会再详细讲解

这里可以先大概回答一下问题

哈希表（散列表）的存储时依靠数组实现的，那既然数组已经够方便了，那为什么还需要哈希表？

那现在比如给一个数组，那要再数组中查询某个数，那就需要使用循环遍历，这样的话效率就比较低了，那么如何降低这时间复杂度呢？比如我要查询11，那我就直到它在那个位置，然后看是否在那个位置

hash函数就建立了数据与存储位置之间的关系，方便存取和插入

装载因子 == 数据个数/数组容量；容量越大，迭代器效率低，但是装载因子过大，又会增大hash冲突的概率

这里就以一个例题来看一下Set的操作

使用散列集或者链式散列集，在实验类中定义两个类犯法，方法addElements使用Scanner从文本中抽取单词添加到指定的集，方法print利用print利用迭代器遍历输出指定集的各元素

package Luogu;

import java.util.*;

public class ContainerDemo {
	private static String text = "Do sit down.Do study hard!"+"Let me  try again.Let Tom go there themself";
    public static void addElements(Set set)
    {
    	Scanner scanner = new Scanner(text);//从String中获取数据
    	scanner.useDelimiter("[\s.! ]\s*");//将text从！. 空白分隔
    	while(scanner.hasNext())//是否还有token
    	{//加入集合
    		set.add(scanner.next());//和迭代器一样也是光标
    	}
    }
  //利用迭代器遍历并输出
	public static void print(Set set)
	{
		Iterator iterator = set.iterator();
		while(iterator.hasNext())
		{
			System.out.print(iterator.next()+" ");
		}
		System.out.println();
	}
	//操作
	public static void main(String[] args) {
		Set hashset = new HashSet();//上转型
		addElements(hashset);
		print(hashset);//元素只允许出现一次
		Set linkedset = new linkedHashSet<>();
		addElements(linkedset);
		print(linkedset);//按照添加的顺序添加
		
	}
}

这里的输出结果为

study again go Do down Tom there themself me Let try hard sit
Do sit down study hard Let me try again Tom go there themself

链式hash集是是按照插入顺序输出的，而普通的就是无序的，但是这里两者都是会自动删除重复的元素，就是add的时候执行的

树型集treeSet

这个类继承AbstractSet的扩展，同时实现了SortedSet接口，加入的元素必须是可以相互比较的，树型集根据比较结果维护其元素的顺序，树型集的迭代器按照升序遍历遍历元素

树型集之间的比较以及排序方式有两种

自然顺序：添加到树型集中的元素必须实现Comparable接口，提供compareTo方法，元素之间就是利用该方法排序和比较，很多ApI比如String类和基本类型类都实现了该接口
比较器顺序：给树型集指定一个实现Comparator接口的比较器，利用比较器对象的相关方法完成排序和比较，加入树型集的元素必须可利用该比较器进行比较

Comparator接口中声明了两个方法

public interface Comaparator{
    int compare(T o1,T o2); //比较两个参数对象，返回负整数，零或正整数
    boolean equals(Object obj); //比较参数o是否和当前比较器相等
}

这里具体使用那种构造方法与与构造方法有关

TreeSet(); //创建一个空树型集，采用自然顺序排序
TreeSet(Comparator
TreeSet(Collection
TreeSet(SortedSet< E> s); //创建一个树型集，包含与参数集相同的元素，采用与参数集相同的排序方式

与散列集相比，树型集是可比较和有序的，除了Set的基本方法，还有一些与元素次序有关的方法

Comparator comparator();//返回集的比较器，若是自然顺序，则为null
E first(); // 集的第一个元素
E last(); //返回最后一个元素
SortedSethead[tail][sub]Set(E fromElement); //返回一个视图

目前来看，树型集相比散列集就是一个可比较，一个不可比较，如果要求操作次序相关或者需要比较，就采用树型集

下面来举一个例子

使用树型集，首先定义一个比较器类，用来比较两个字符串的大小，比较时忽略大小写，应用程序先后采用自然顺序和比较器顺序创建两个树型集，添加和删除元素使用上一个例子的方法

package Luogu;import java.util.*;public class ContainerDemo implements Comparator{//要使用比较器顺序，那就要实现Comparator类	private static String text = "Do sit down.Do study hard!"+"Let me  try again.Let Tom go there themself";    //覆写比较方法	@Override	public int compare(String o1, String o2) {		return o1.compareToIgnoreCase(o2);//忽略大小写的比较	}	//添加元素	public static void addElements(Set set)    {    	Scanner scanner = new Scanner(text);//从String中获取数据    	scanner.useDelimiter("[\s.! ]\s*");//将text从！. 空白分隔    	while(scanner.hasNext())//是否还有token    	{//加入集合    		set.add(scanner.next());//和迭代器一样也是光标    	}    }  //利用迭代器遍历并输出	public static void print(Set set)	{		Iterator iterator = set.iterator();		while(iterator.hasNext())		{			System.out.print(iterator.next()+" ");		}		System.out.println();	}	//操作	public static void main(String[] args) {//		Set hashset = new HashSet();//上转型//		addElements(hashset);//		print(hashset);//元素只允许出现一次//		Set linkedset = new linkedHashSet();//		addElements(linkedset);//		print(linkedset);//按照添加的顺序添加		Set treeset = new TreeSet(); //自然顺序		addElements(treeset);		print(treeset);		Set comset = new TreeSet(new ContainerDemo());		addElements(comset);		print(comset);			}}//这里为了方便就直接继承了比较器了

输出的结果为

Do Let Tom again down go hard me sit study themself there try
again Do down go hard Let me sit study themself there Tom try

前面的是自然排序，实际上使用的是元素本身的compareTo来比较的，Unicode码；后面使用的是比较器顺序，这里的比较器是要求忽略大小写，所以两者的结果不一样

图（Map）

映射是一种键-值对集合，其中键和值都可以是任意类型的对象，映射不能包含重复的键，每一个键最多只能对应一个值

与表和集将Collection作为根接口不同，映射以Map为根接口，映射涉及的接口和类为

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GCwOhhiY-1634132990429)(file:///C:UsersOMEY-PCdocumentsTencent Files1589827479ImageC2C73A24B4150C6A0D6E78FCD511EA9B760.jpg)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bqrdvABh-1634132990431)(https://www.freesion.com/images/840/730d25e60a75d5c23c4fdb09665668e8.JPEG)]

Map接口和Collection接口是不一样的，因为所传入的类型数量是不一样的

public interface Map{    void clear(); //删除所有的键--值对    V get(Object key); //返回指定键对应的值 （由键获值）    V put(K key,V value); //添加一个键-值对    void putAll(Map m); //将映射m的所有键--值对添加到当前映射    V remove(Object k); //删除指定键对应的值    int size(); //返回键值对的数目    boolean isEmpty(); //当前映射是否为空    boolean containsKey(Object key); //测试是狗包含具有指定键的键值对    boolean containsValue(Object value); //测试是否包含指定值的键值对    boolean equals(Object o); //测试两个映射是否相等    Set> entrySet(); //返回当前映射的一个集视图【不重复】    Set keySet(); //返回当前映射的一个集视图 【键是不重复的，为Set】    Collection values(); //返回当前值的一个集合视图 【值可能重复，为Collection】}

与集不能有重复的元素一样，映射要求不能有重复的键，相比表可以通过下标访问元素，映射可以通过键访问相应的值（这在数据结果的内部排序中的key是相同的意思），与集和表使用add或者addAll方法添加元素不同，映射通过put方法与putAll方法添加元素

这里添加时，如果与原键值对具有相同的键，那么就用新值替代原值并返回原址，否则添加后返回Null。putAll就是调用的put方法来解决

表和集都可以使用迭代器遍历访问所有元素，映射没有迭代器，但映射可以返回视图返回一个集合视图，从而间接访问。keySet方法返回所有键值的集视图，values方法返回所有值的集合视图，entry方法返回映射中所有键值对的集视图，其中键值对的表示为Map.Entrydui想，Entry是嵌套在Map中的接口，声明的方法有

K getKey(); //返回键值对的键V getValue(); //返回键值对的值V setValule(V value); //设置键值对的值

AbstractMap是Map的一个抽象类，除了entrySet方法，它实现了接口中的其他方法，可扩展该类来定义具体的映射类，如果定义的映射是不可更改的，那就要覆盖put，提供具体的实现，entrySet().iterator()返回的迭代器必须有remove方法

映射的实现类

和Set类似，也有Hash，linkedHash，Tree三种具体实现类

构造方法

HashMap();
HahMap(int initialCapacity);
HashMap(int initialCapacity,floatFactor); //都是和之前相同的意义，只是变成了映射
HashMap(Map m);

与散列集一样，散列映射基于散列表技术，键值对没有顺序

链式散列映射的键值对是有序的，其顺序有两种模式：插入顺序【之前那种】访问顺序【按照元素最后一次被访问的时间，由早到晚排序】，选择那种排序方式取决于构造方法

前四个和上面一样，都是插入排序
linkedHashMap(int initialCapacity,floatFactor,boolean accessOrder);//true就是访问顺序

与树型集一样，树型映射是按照键值排序的，排序顺序还是自然顺序和比较器顺序，树型映射的构造方法和树型集差不多

TreeMap();
TreeMap(Comparator
TreeMap(Map m);
TreeMap(SortedMap m);

树型映射不仅实现了Map接口，同时也实现了SortedMap接口，声明的也是与次序相关的方法，与树型集是类似的，这里就不再赘述了

所以说，散列，链式散列，树，就是三种不同的结构，散列无需，后两者有序，链式散列是插入顺序，再Map中还可能使访问顺序，树就使自然顺序或者比较器顺序

支持类Collections

这个类和Collection有什么渊源呢，Collections是集合框架的支持类，提供了一组静态方法，便于programmer对表和集和映射进行更为有效的管理

frequency //对象在集合中出现的次数max //最大元素集合中min //最小元素集合中repalceAll  //用新值替换表中所有的旧值shuffle  //随机打乱表中的顺序binarySearch  //使用二分查找法在排好序（自然顺序）的表中查找对象，返回对象的下标sort //使用自然顺序排序表中元素synchronizedList //包装指定表成为同步表synochronizedSet //包装指定集synchronizedMap //包装指定映射synchronizedSortedMap //包装指定有序映射unmodifiableList //包装指定表为只读表（不可修改） ····Set Map SortedMap

树型集和树型映射都支持对元素进行排序，但是表没有相应的实现类，Collections中的sort方法就提供了对表的排序，二分查找可以在表中查找元素。若找到就返回元素下标，没有找到就返回【-<插入点> -1】

Collection和Map接口的方法都没有要求保障线程安全，所以一般的对象都不是线程安全的，多线程访问时iju可能引起数据混乱，Collections中的synchronizedSet之类的方法就可以包装这些对象（形成同步版本），但是需要注意，如果利用迭代器访问元素，还是要自己完成线程同步

List list = Collections.synchronizedList(new ArrayLiast);//这就是装饰器，就像IO中的过滤流一样，最里面一定使原始的synchronized(list){    Iterator i = list.iterator();    while(i.hasnext())    {//迭代器访问要自己加同步锁，因为只是list为同步的，就是list中的方法        process(i.next);}}

另外还有unmodified方法可以包装成只读版本

下面来演示一下Collections的使用

package Luogu;import java.util.*;public class ContainerDemo{	public static void main(String[] args) {		List list = new linkedList();//要随机插入，所以使用链式表		//产生10个0-100之间的随机数插入链式表中		for(int i = 0;i <10;i++)		{			list.add((int)(Math.random()*100));//这里int也可以，不能转化为包装类型		}		System.out.println("未排序的 "+list);		Collections.sort(list); //调用类方法进行排序		System.out.println("排序之后 "+ list);		//无论表中是否有10，都在相应位插入10		int find = Collections.binarySearch(list, 10);//使用二分查找		find = find >= 0?find:-(find+1); //使用三目符，如果找到就		list.add(find, 10);		System.out.println("插入后"+list);		//包装为只读类型		list = Collections.unmodifiableList(list);//注意原来的表没有被覆盖，和String一样，要指针赋值		try {			list.add(10); //自己加例外		}catch(Exception e) {			e.printStackTrace();		}	}}

这里的一种输出结果为

未排序的 [20, 90, 16, 39, 93, 51, 76, 46, 25, 70]
排序之后 [16, 20, 25, 39, 46, 51, 70, 76, 90, 93]
插入后[10, 16, 20, 25, 39, 46, 51, 70, 76, 90, 93]
java.lang.UnsupportedOperationException

Collections类是一个非常适用的类，可以方便对表list进行排序

对于集合的简单介绍就到此结束了，SE也就这样子了，接下来会分享项目的具体实现~

♥6000字介绍集合框架下的List，Set，Map以及支持类Collections【Java养成】

Java相关栏目本月热门文章