【集合】框架

集合的由来

java是面向对象语言，它对事物的描述都是通过对象来体现的。为了方便对这些对象进行操作，我们就必须把这些对象进行存储，存储这些对象，就不能是一个基本的变量，而应该是一个容器类型的变量。

数组和StringBuffer是容器类型的，StringBuffer的结果是一个字符串，不一定满足我们的要求，所以只能选择数组，这就是“对象数组”。而对象数组又不能适应变化的需求，因为数组的长度是固定的，为了适应变化的需求，java就提供了集合供我们使用。

数组和集合的区别

1 长度区别：

① 数组的长度固定

② 集合长度可变

2 元素的数据类型不同：

① 数组可以存储基本数据类型，也可以存储引用数据类型，存储引用数据类型就是对象数组

② 集合只能存储引用数据类型(集合的出现也就是用来存储对象的)

集合是存储多个元素的，存储多个元素也是有需求的，比如：多个元素中不能有相同的元素、多个元素按照某种规则排序一下。针对不同的需求，集合也有很多类，这些集合类的数据结构也不同。

数据结构：数据的存储方式。

虽然数据结构不同，但是它们有共性的内容(存储、获取、判断等)，通过不断地向上提取，就可以得到一个集合的继承体系结构图，这个体系的老大是Collection。

集合框架图

Collection功能概述

添加功能	1 booleanadd(Object obj) 2 booleanaddAll(Collection c)	1 添加一个元素 2 将集合c中的元素添加到另一个集合中，另一个集合指的就是调用addAll()的集合
删除功能	1 void clear() 2 booleanremove(Object o) 3 boolean removeAll(Collection c)	1 移除所有元素 2 移除一个元素 3 移除一个集合的元素。只要有一个元素被移除就返回true
遍历功能	Iterator<E>iterator()	迭代器，集合的专用遍历方式 。可以用while循环，也可以用for循环遍历。 iterator()返回的是Iterator，是一个接口，实际返回的是实现类的对象，此接口方法有三个： void remove()：移除迭代器返回的最后一个元素 boolean hasNext()：判断是否有元素，如果仍有元素就迭代，返回true Object next()：获取元素，并移动到下一个位置
判断功能	1 booleancontains(Object obj) 2 boolean containsAll(Collection c) 3 boolean isEmpty() 4 boolean CollectionUtils.isEmpty(Collection)	1 判断集合中是否包含指定元素 注意：contains()底层依赖的是equals()。案例：如果是去除ArrayList集合中的重复自定义对象元素，如果要被contains()包含的类对象中没有重写equals()，则默认调用的是Object的equals()，Object的equals()默认比较的是地址值，所以地址值都是不同的，所以被contains()包含的类对象中要重写equals()。 2 判断集合中是否包含指定集合元素。只有包含所有的元素才返回true。 3 判断集合是否为空。 4 可以同时判断一个集合是否为空和是否为null，是Spring框架提供的。如果为null或者为空就返回true
长度功能	intsize()	返回元素的个数
交集功能	boolean retainAll(Collection c)	两个集合都有的元素。 返回的元素去哪了？返回的boolean是什么意思？ 两个集合存在交集，调用该方法的集合存储的是交集的元素，没有其他的元素，返回true。 两个集合不存在交集，调用该方法的集合存储的是空值，没有任何元素，也返回true。 假设有两个集合A，B。A对B做交集，最终的结果保存在A中，B不变；返回值表示的是：A集合的元素是否发生过改变，A集合原来保存的元素发生过改变则返回true，A集合原来保存的元素没有发生过任何改变，则返回false。
转换功能	Object[] toArray()	把集合转为数组。可以实现对数组的遍历

SequencedCollection功能概述

jdk21新增，所有的有序集合都实现了这个接口；由于是有序的集合，它在Collection接口的基础上扩展了一些方法：

添加功能	1 void addFirst(Object o) 2 void addLast(Object o)	1 向头部添加元素 2 向末尾添加元素
删除功能	1 Object removeFirst() 2 Object removeLast()	1 删除头部元素 2 删除末尾元素
获取功能	1 Object getFirst() 2 Object getLast()	1 获取头部元素 2 获取尾部元素
反转功能	SequencedCollection reversed()	反转集合中的元素，返回新的集合，原集合的元素并没有反转

迭代器的使用及注意事项

学生类省略... ...

public class IteratorDemo { public static void main(String[] args) { Collection c = new ArrayList(); Student s = new Student("张三", 1); Student s2 = new Student("李四", 2); Student s3 = new Student("王五", 3); c.add(s); c.add(s2); c.add(s3); Iterator it = c.iterator(); //通过集合获取迭代器对象。迭代器是依赖于集合而存在的 while (it.hasNext()) { //先判断 Student student = (Student) it.next(); //在获取元素 System.out.println(student.getName()+", "+student.getAge()); } } }

上面除了可以使用while去循环遍历之外，也可以使用for循环。

it是局部变量，for循环执行完毕就是垃圾，提高内存利用率。只编写for循环部分，如下：

for (Iterator it = c.iterator(); it.hasNext(); ) { //没有条件控制 Student student = (Student) it.next(); System.out.println(student.getName()+", "+student.getAge()); }

注意事项：

/* * 如果将以下的注释用链式编程去编写，如果集合的元素是奇数个，则会报错java.util.NoSuchElementException */ Iterator it = c.iterator(); while (it.hasNext()) { //Student student = (Student) it.next(); //System.out.println(student.getName() + ", " + student.getAge()); System.out.println(((Student) it.next()).getName() + ", " + ((Student) it.next()).getAge()); }

从控制台的输出可以看出，张三的年龄为2，实际是1。之所以出现这样的问题是因为Iterator接口的next()是获取元素，并移动到下一个位置。这里第二次调用next()，就移动到了李四的年龄了，再移动就是王五的姓名，最后没有另一个人年龄了，就报错。如果是偶数个不会报错，但是遍历出来的数据是错乱的。所以不能多次使用next()，因为每次访问都是一个对象

迭代器的原理及源码解析

迭代器为什么不定义成一个类，而是一个接口？

假设迭代器定义成一个类，这样就可以通过创建该类的对象，调用该类的方法，来实现集合的遍历，定义成迭代器类，就是一个具体实现，具体实现，这些集合类存储元素的方式就是一样的。BUT！ java中提供了这么多的集合类，而这些集合类的数据结构都是不同的，所以存储元素的方式应该是不同的，进而遍历的方式也应该是不一样的，所以就没有定义成一个迭代器类。

而无论是哪种集合，遍历集合都应该具备获取元素以及判断的功能，在获取元素之前先做判断，这样就不容易出错。而每种集合的方式又不太一样，所以这两个常用的判断跟获取元素功能给提取了出来，并不提供具体实现，这种方式就是接口。

那么，具体的实现类在哪呢？答案是：在具体的实现类中，以成员内部类的方式来体现的。源码如下：

//Iterator接口定义了如下两个方法 public interface Iterator { boolean hasNext(); Object next(); } public interface Iterable { Iterator iterator(); //该方法返回的是Iterator接口 } public interface Collection extends Iterable { Iterator iterator(); } public interface List extends Collection { Iterator iterator(); //到这还没有具体实现，因为List还是接口 } public class ArrayList implements List { public Iterator iterator() { //具体子类实现了 return new Itr(); } private class Itr implements Iterator { //Itr重写了这两个方法 public boolean hasNext() {} public Object next(){} } }

//遍历集合元素 Collection c = new ArrayList(); c.add("hello"); c.add("world"); c.add("java"); Iterator it = c.iterator(); //new Itr(); while(it.hasNext()) { String s = (String)it.next(); System.out.println(s); }

以上遍历集合元素代码解析：

通过c集合对象获取迭代器对象，在多态中通过父类对象访问成员方法的特点中，如果子类重写了父类的方法，输出的结果是子类成员方法重写父类成员方法后的内容。编译看左边，Collection有iterator()，不报错通过，运行看右边，子类ArrayList有iterator()，所以输出的是子类的iterator()，iterator()返回的是new Itr()，Itr是一个具体的实现类，所以，如果返回的是一个接口，实际返回的是实现类的对象。

List集合特点：

有序(存储顺序和取出顺序一致)、可重复

List集合特有功能概述

添加功能	1 void add(int index, Object element) 2 boolean addAll(int index, Collection<? extends E> c)	1 在指定索引位置插入元素 2 在指定索引位置插入一个集合中的所有元素
删除功能	Object remove(int index)	根据索引删除元素，返回被删除的元素
修改功能	Object set(int index, Object element)	根据索引修改元素，返回被修改的元素
获取(遍历)功能	Objectget(int index)	获取指定位置的元素
遍历功能	ListIterator listIterator()	列表迭代器。List集合特有的迭代器 listIterator()返回ListIterator，是一个接口，继承了Iterator。常用的方法有： boolean hasPrevious()：与Iterator接口的hasNext()一样，只不过是逆向判断是否有元素。 Object previous()：与Iterator接口的next()一样，只不过是获取上一个元素。 注意：要实现逆向遍历，首先必须实现正向遍历！所以一般无意义，不使用
其它功能	1 int indexOf(Object o) 2 int lastIndexOf(Object o) 3 List<E> subList(int fromIndex, int toIndex)	1 从前往后查找指定元素的索引，不存在返回-1 2 从前往后查找指定元素最后一次出现的索引值，不存在返回-1 3 包含开始，不包含结束；在此区间截取一个新的List集合，原始集合不变化

List 集合特有遍历功能(普通for)：size()结合get()

public class ListDemo { public static void main(String[] args) { List l = new ArrayList(); l.add("王麻子"); l.add("张飞"); l.add("武松"); for (int i = 0; i < l.size(); i++) { String s = (String) l.get(i); System.out.println(s); } } }

并发修改异常的产生原因及解决办法

public static void main(String[] args) { List l = new ArrayList(); l.add("王麻子"); l.add("张飞"); l.add("武松"); Iterator it = l.iterator(); while (it.hasNext()) { String s = (String) it.next(); if ("张飞".equals(s)) { l.add("好汉"); } } System.out.println(l); }

产生原因：

以上的代码逻辑看似没有问题，如果两个字符串内容相等，则添加新的元素。但是却报错了，之所以报错是因为，迭代器是依赖集合而存在的，当判断到两个字符串内容相等就给集合添加了一个新的元素，之后在用迭代器的hasNext()判断，迭代器却不知道集合里面有新的元素，所以就报错了，这个错叫并发修改异常！

也就是说，迭代器遍历元素的时候，通过集合是不能修改元素的。

解决办法：

集合的创建、往集合添加元素省略

方法1 迭代器遍历元素，迭代器修改元素

/* * 方法1 * 因为Iterator迭代器没有添加功能，它的子接口ListIterator有 */ ListIterator it = l.listIterator(); while (it.hasNext()) { String s = (String) it.next(); if ("张飞".equals(s)) { it.add("好汉"); } } System.out.println(l);

方法2 集合遍历元素，集合修改元素(普通for)

//方法2 for (int i = 0; i < l.size(); i++) { String s = (String) l.get(i); if ("张飞".equals(s)) { l.add("梁山"); } } System.out.println(l);

方法1与方法2的区别是：方法1添加的新元素位于要比较元素的后面，方法2新添加的元素在整个元素的最后面

ArrayList集合特有功能概述

ArrayList集合底层数据结构是数组，随机增删慢，末尾元素增删快，修改快（因为是先查询到指定元素的索引，再修改，所以修改是快的），查询快；线程不安全；效率高

转换功能

public <T> T[] toArray(T[] a)

把集合转成数组

Vector集合特有功能概述

Vector集合类底层数据结构是数组，所以查询快，增删慢；线程安全，所以效率低

添加功能	void addElement(Object obj)	添加功能，jdk1.0出现的，被add()替代
获取功能	1 Object elementAt(int index) 2 Enumeration elements()	1根据索引获取，类似于get() 。jdk1.0出现。被get()替代 2获取多个元素，类似于迭代器。jdk1.0出现。被Iterator iterator()替代 elements()返回Enumeration，是一个接口，实际返回的是实现类的对象，该接口有2个方法： boolean hasMoreElements()：被hasNext()替代 Object nextElement()：被next()替代

LinkedList集合特有功能概述

LinkedList底层数据结构是链表，所以查询慢，随机增删快（末尾元素增删更快）；线程不安全，所以效率高

添加功能	1 void addFirst(Object obj) 2 void addLast(Object obj)	1 将指定元素插入到元素的开头位置处。新添加的元素总是在最前面 。 2 将指定元素插入到元素的末尾位置处
获取功能	1 Object getFirst() 2 Object getLast()	1 获取集合中的第一个元素。集合元素不变化 2 获取集合中的最后一个元素。集合元素不变化
删除功能	1 Object removeFirst() 2 Object removeLast()	1 删除集合中的第一个元素，并返回(获取)删除的元素 2 删除集合中的最后一个元素，并返回删除的元素

Arrays工具类功能概述

转换功能	public static <T> List<T> asList(T... a)	将数组转换为集合，已这种方式创建集合给定初始容量。需要注意的是： 1、只能针对对象数组进行转换，对基本数据类型的数组转换不了 2、转换后的集合不能够对其进行增删元素，但可以修改元素，转换后的集合是一个只读集合，但又完全不是只读集合，因为可以修改集合的元素 适用场景：希望别人不可以增删元素的时候使用
排序功能	public static void sort(Object[] a)	对指定对象数组进行排序

对asList()的使用，代码如下：

// 例 public class ArraysDemo { public static void main(String[] args) { String[] arr = {"hello", "world", "java"}; List<String> list = Arrays.asList(arr); //list.add("javaEE"); //是错误的，虽然转成了集合，但本质还是数组，不能改变集合的大小（也就是不能增删元素，但可以修改元素），会报错：UnsupportedOperationException for (String s : list) { //遍历集合。除了可以使用迭代器，还可以使用foreach System.out.println(s); } } }

//因为方法是可变参数，所以可以省略定义数组的步骤，直接这样编写： List<String> list = Arrays.asList("hello", "world", "java");

注意事项：

此时虽然将一个数组转换为了一个集合，但是不能改变集合的大小，其本质还是一个数组。因为参数是以数组的形式保存下来的，数组的长度不可变。

如果给集合添加、删除元素则报错：UnsupportedOperationException

Set集合特点

无序(存储顺序和取出顺序不一致)、唯一

HashSet集合类底层数据结构是哈希表；线程不安全，所以效率高。哈希表结构底层依赖HashCode()和equals()。哈希表：是一个元素为链表的数组，综合了数组和链表的优点。

HashSet保证元素唯一的源码解析

为什么List集合是可重复的，而Set集合是唯一的呢？

保证Set集合唯一的是它的add()，源码如下：

interface Collection{ ... } interface set extends Collection{ ... } class HashSet implements Set{ private static final Object PRESENT = new Object(); private transient HashMap<E, Object> map; public HashSet{ map = new HashMap<>(); //可以看出，HashSet底层是HashMap } public boolean add(E e){ return map.put(e, PRESENT) == null; //调用了HashMap的put() } } class HashMap implements Map{ public V put(K key, V value) { //看哈希表是否为空，如果为空，就开辟空间 if (table == EMPTY_TABLE) { inflateTable(threshold); } //判断对象是否为null if (key == null) return putForNullKey(value); int hash = hash(key); //算哈希值，调用了hash()。和添加进来元素对象的hashCode()相关 //在哈希表中查找hash值 int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; //走这里其实是没有添加元素 } } modCount++; addEntry(hash, key, value, i); //把元素添加 return null; } transient int hashSeed = 0; //hash() final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); //这里调用的是添加进来元素对象的hashCode() // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } }

通过查看add()源码，可以看出这个方法底层依赖两个方法：hashCode()和equals()。也就是说由这两个方法保证元素唯一性的。

步骤：首先比较哈希值，如果相同，继续走，比较地址值或者比较equals()，如果不同，就直接添加到集合中

按照方法的步骤来说：先看hashCode()值是否相同

相同：继续比较equals()方法。返回true：说明元素重复，就不添加；返回false：说明元素不重复，就添加到集合。

不同：就直接把元素添加到集合。

如果类没有重写hashCode()和equals()，默认使用的Object()。一般来说不会相同。
而String类重写了hashCode()和equals()方法，所以，它就可以把内容相同的字符串去掉，只留下一个。

LinkedHashSet集合类

LinkedHashSet集合类继承自HashSet，LinkedHashSet底层数据结构由 哈希表和链表组成。

特点：有序、唯一

链表保证元素有序(存储和取出顺序一致)；

哈希表保证元素的唯一性。

TreeSet集合类

TreeSet底层数据结构是二叉树。(也称红黑树，是一种自平衡的二叉树)。TreeSet底层是TreeMap

如何存进去元素的？

第一个元素存储的时候，直接作为根节点存储；从第二个元素开始，每个元素与根节点进行比较：

小：作为左节点

大：作为右节点

相等：不存储

如何取出元素？

分 前序遍历、中序遍历、后序遍历。从根节点开始，按照左中右的原则依次取出元素。

特点：排序、唯一

能够对元素按照某种规则进行排序，具体取决于使用的构造方法，有2种：

1 自然排序 -- 无参构造

真正的比较是依赖于元素的compareTo()，这个方法定义在Comparable接口里面的。所以，要想重写compareTo()，就必须实现Comparable接口，这个接口表示的就是自然排序。

2 比较器排序 -- 带参构造

因为带参构造方法需要传入一个Comparator接口，实际要传入的是此接口的实现类的对象。传入此接口实现类的对象可以外部定义一个类实现此接口，重写compare()，但如果只用一次，一般使用匿名内部类，在匿名内部类重写compare()

TreeSet集合类保证元素排序和唯一的原理：

排序：

1 自然排序(是元素具备比较性)

让元素所属的类实现自然排序接口Comparable

2 比较器排序(是集合具备比较性)

让集合的构造方法接收一个比较器接口Comparator的实现类对象

唯一：

是根据比较的返回是否是0来决定的

Map集合

特点：Map集合的最大特点，就是它可以存储键值对的元素，键和值是映射的关系，将键映射到值，一个键映射一个值。键唯一，但值可以重复。无序。

Map集合和Collection集合的区别：

Map集合存储元素是成对出现的，Map集合的键是唯一的，值是可重复的；Collection集合是单独存储元素的，Collection集合的子接口Set是唯一的，List是可重复的。

Map集合的数据结构只针对键，与值无关；Collection集合数据结构针对的是元素

Map集合功能概述

添加功能	Vput(K key,V value)	添加元素
删除功能	1 void clear() 2 Vremove(Object Key)	1 移除所有键值对元素 2 根据键删除键值对元素，并把值返回
判断功能	1 booleancontainsKey(Object key) 2 booleancontainsValue(Object Value) 3 boolean isEmpty()	1 判断集合是否存在指定的键 2 判断集合是否存在指定的值 3 判断集合是否为空
获取(遍历)功能	1 Set<Map.Entry<K,V>>entrySet() 2 Set<K>KeySet() 3 Vget(Object key) 4 Collection<V>values()	1 返回键值对对象的集合 Map.Entry是一个接口，此接口有常用的2个方法： K getKey()：返回与此项对应的键 V getValue()：返回与此项对应的值 2 获取集合中所有的键的集合 3 根据键获取值 4 获取集合中所有的值的集合
长度功能	int size()	返回集合键值对的对数

Map集合的遍历

方法1：根据键找值

思路：获取集合中所有的键的集合；遍历键的集合，得到每一个键；根据键获取值。

先用KeySet()，然后用foreach循环遍历Set集合，得到每一个键，然后再用get(Object key)。

方法2：根据键值对对象找键和值

思路：获取所有键值对对象的集合；遍历键值对对象的集合，得到每一个键值对对象；根据键值对对象得到键和值

public class MapDemo { public static void main(String[] args) { Map<String, String> map = new HashMap<String, String>(); map.put("鹿晗", "关晓彤"); map.put("雪儿", "范范"); map.put("黄晓明", "angelababy"); Set<Entry<String,String>> set = map.entrySet(); for (Entry<String,String> entry : set) { String key = entry.getKey(); String value = entry.getValue(); System.out.println(key+", "+value); } } }

LinkedHashMap集合类

LinkedHashMap集合类继承HashMap。LinkedHashMap底层数据结构由 哈希表和链表组成。

特点：有序、唯一

链表保证元素有序(存储和取出顺序一致)；

哈希表保证元素的唯一性。

TreeMap集合类

TreeMap键的数据结构是二叉树。

特点：排序、唯一

HashMap和Hashtable的区别

Hashtable是jdk1.0出现的，所以它的命名不规范，它的底层也是Map集合的哈希表结构，用法几乎是一样的，HashMap的出现就是用来代替Hashtable的，就像ArrayList集合用来代替Vector。

Hashtable：线程安全的，所以效率低。不允许null键null值；

HashMap：线程不安全，所以效率高。允许null键null值。

Collections——集合操作工具类概述

要知道的几个静态方法

排序功能	public static <T> void sort(List<T> list)	默认自然排序
二分查找	public static <T> int binarySearch(List<?> list, T key)
最大值	public static <T> T max(Collectin<?> coll)
反转	public static <T> void reverse(List<T> list)
随机置换	public static <T> void shuffle(List<T> list)
将一个集合中的所有元素添加到另一个集合中	addAll( java.util.Collection<? super T> c, T... elements )	第一个参数就是被添加的集合 第二个参数是要向第一个参数集合中要添加进去的元素。第二个参数是一个数组，如果第二个参数是集合，需要将集合转为数组，调用toArray()，并且toArray()要指定数组长度