集合就像是一个容器，把需要存储的对象存起来以待使用。当我们需要把相同结构的个体整合到一起的时候，我们就可以使用集合。那就有人问了，为什么使用集合来存放数据，数组不是也可以对数据进行存储吗？这就要好好讲讲了。
1.2 为什么使用集合相同点： 集合和数组都可以存储多个对象，把他们整和到一起，对外当做是一个整体存在。
数组的缺点：
- 长度是固定的，是在初始化时就确定了的；数组采用连续的存储空间，删除和添加利率低；数组无法直接保存映射关系；数组缺乏封装，操作频繁。
集合将数组的缺点都解决了，所以，我们通常使用集合来存储对象。
1.3 集合框架java集合框架提供了一套性能优良、使用方便的接口和类，它们位于java。util包中。存放在集合的数据我们称之为元素。
常用类和接口的关系：
集合架构： Collection接口：存储一组不唯一，无序的对象 List接口：存储一组不唯一，有序的对象（这里的有序是索引顺序，不是大小有序） Set接口：存储一组唯一，无序的对象 Map接口：存储一组键值对象，提供key和value的映射 Key 唯一 无序 value 不唯一 无序2. Collection 2.1 概述
Collection 是单列集合最顶层的接口。
子系：从上面的叙述中，我们可以看出，它的子系有可以重复的，有唯一的，有无序，有有序的。
boolean add(Object o); 添加 boolean addAll(Collection c); 添加一个集合2.2.2 删除
void clear(); 删除所有的元素 boolean remove(Object o); 删除指定的元素 boolean remoceAll(Collection c) ; 删除指定集合中的元素2.2.3 判断
boolean contains(Object o) ; 判断集合中是否包含指定的元素 boolean containsAll(Collection c) ; 判断集合中是否包含指定的集合。2.2.4 其他
长度： int size(); 获取： 使用迭代器 Iterator iterator() 交集： boolean retainAll(Collection c); 转化为数组： Object[] toArray();2.3 案例
package com.lmx.collection;
import sun.security.acl.WorldGroupImpl;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class CollectionDemo {
public static void main(String[] args) {
// 创建集合
Collection collection = new ArrayList();
//添加元素
collection.add("Hello");
collection.add("World");
collection.add("JAVA");
collection.addAll(collection);
// 删除
// collection.clear();
// collection.remove("World"); // 一次只能删除一个
// collection.remove("World");
//collection.removeAll(collection);
// 长度
System.out.println(collection.size());
// 判断
System.out.println(collection.contains("JAVA"));
// 获取数据 迭代器
Iterator iterator = collection.iterator();//数据存放在了迭代器中
while (iterator.hasNext()){
String next = (String) iterator.next();
System.out.println(next);
}
// 转化为数组
Object[] objects =collection.toArray();
System.out.println(Arrays.toString(objects));
}
}
案例：collection 中存放对象
import javafx.util.Pair;
import sun.security.acl.WorldGroupImpl;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
public class CollectionDemo {
public static void main(String[] args) {
// 创建集合
Collection collection = new ArrayList();
//添加元素
User user1 = new User("张三","123");
User user2 = new User("李四","234");
User user3 = new User("王五","345");
User user4 = new User("赵六","456");
User user5 = new User("周七","567");
collection.add(user1);
collection.add(user2);
collection.add(user3);
collection.add(user4);
collection.add(user5);
for (Object o : collection) {
System.out.println(((User)o).getName());
}
System.out.println("---------------");
for (int i = 0; i < collection.size(); i++) {
// Collection 接口没有get(),但是ArrayList里面有get()
// 取到的是 Object 对象，需要强制转化为User 类型
System.out.println(((User)((ArrayList)collection).get(i)).getName());
}
System.out.println("----------------");
Iterator iterator = collection.iterator();
while (iterator.hasNext()) {
System.out.println(((User)iterator.next()).getName());
}
System.out.println("-----------------");
Object[] objects = collection.toArray();
for (int i = 0; i < objects.length; i++) {
System.out.println(((User)objects[i]).getName());
}
}
3.List接口的最主要实现类
3.1 方法
因为List接口是继承Collection接口的，所以List 中可以存在所有的collection 方法，而且它还可以有他自己原创的方法。
List 的特有的功能： 1.添加 void add(int index,E element);在指定的下标处添加元素 2.获取 E get(i); 返回指定的位置的元素 3.列表迭代器 ListIterator listIterator(); 4.修改 E set(int index,E element);用指定的元素element，换取列表中指定位置的元素。 5.截取 List subList(int formIndex,int toIndex);// 从索引formIndex到toIndex 之间的部分截取为一个新的List 6.删除 E remove(int index);3.2 实现类（ArrayList、linkedList、Vector） 3.2.1 ArrayList
在内存中分配连续的空间，实现了长度可变的数组（即可以扩容）
优点：遍历元素和按索引查询元素的效率比较高
缺点：添加和删除需要大量移动元素，所以效率较低；按内容查找效率也较低。
3.2.1.1 相关方法1.集合的创建 最常用：List泛型：list = new ArrayList(); 2.添加：list.add(); -> 在集合末尾添加：add(33) 或 在指定索引处添加：add(2,33) list.addAll();与add()用法一致，不同的是addAll()是添加整个集合 3.删除：list.clear(); -> 删除整个集合 list.remove(); -> 删除指定索引的元素或按照内容删除 remove(new Integer(90)); ->按照内容删除 remove(90); ->按照索引删除元素 removeAll(); ->list1.removeAll(list2);删除list1中与list2相同的元素 4.修改：list.set(); -> set(1,99);将索引为1的元素修改为99 5.判断：list.contains(); -> contains(99);判断集合中是否含有元素99，返回boolean类型 list.isEmpty(); -> 判断集合是否为空，若集合size为0，则返回true 6.保留：retainAll(); -> list1.retainAll(list2);保留list1中与list2相同的元素 7.大小：size(); -> 返回列表中的元素数 8.遍历：fori循环 for-each循环 迭代：iterator或ListIterator【Itr是ArrayList类的内部类，它实现了Iterator接口】 注意：再添加数据时，数据类型应保持一致，否则在遍历集合时会报错->ClassCastException 解决：1.使用强制转换 -> 过于繁琐 2.使用泛型 -> 提高了代码的健壮性，简单 泛型是在JDK1.5之后才出现的。
概述：明确数据类型的工作推迟到创建对象或者是调用它的时候。 <数据类型> // 数据类型只能是引用类型。 优点：把运行时可能出现的问题，提前到了编译的时候，避免了强制转型。3.2.1.2 底层源码
ArrayList实现了三个没有方法的接口：RandomAccess、Cloneable、java.io.Serializable 【声明式接口】
【ArrayList的扩容机制】：
JDK1.7中，使用无参构造方法创建ArrayList对象时，默认底层数组长度是10。JDK1.8中，使用无参构造方法区创建ArrayList对象时，默认底层数组长度是0；第一次添加元素，容量不足就要进行扩容了。容量不足时进行扩容，默认扩容50%，若扩容50%还不足容纳新增元素，就扩容为能容纳新增元素的最小数量。
【底层源码】：ArrayList底层是数组
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量等于旧的容量+旧的容量右移一位 => 相当于一次扩容50%
if (newCapacity - minCapacity < 0)//如果增长完还不够用，就让新的容量等于要添加的总容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)//增长后够用，就用这个新的容量去用
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
3.2.2 linkedList
linkedList也实现了List接口，底层是双向链表，它的内存分布不是连续的，故内存地址不是连续的。
它的优缺点与ArrayList恰恰相反。
优点：添加和删除需要大量移动元素，所以效率较低；按内容查找效率也较低。
缺点：遍历元素和按索引查询元素的效率比较高
3.2.2.1 相关方法linkedList与ArrayList的方法最大的不同就是，ArrayList可以使用索引去添加、删除、修改、查询数据，但是linkedList则不能，但是他也有他特有的方法，如：addFirst(11)、addLast(11)、removeFirst(11)、removeLast(11)、getFirst()、getLast()等方法。
注意：推荐向上转型进行集合的创建
3.2.2.2 底层源码底层是一个双向链表
public class linkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable { transient int size = 0; transient Node first;//前指针 transient Node last;//后指针 public linkedList() { }
其中Node是一个节点,双向链表是由一个一个的节点构成的。
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
linkedList实现了Deque接口，Deque接口又继承了Queue接口，所以除了可以作为线性表来使用，还可以当做栈和队列来使用。
栈、队列栈：Deque 先进后出 push()入栈 pop()出栈 peek()获取栈顶元素 队列：Queue3.2.3 Vector
Java中Vector类是允许不同类型元素共存的变长数组。
在相对于ArrayList来说，Vector线程是安全的，也就是说是同步的。创建了一个向量类的对象后，可以往其中随意地插入不同的类的对象，既不需顾及类型也不需预先选定向量的容量，并可方便地进行查找。
初始容量为10，若没有指定扩容大小，则默认扩容为原来的一倍
4. Set接口的主要实现类特点：无序、唯一（不重复） Set相比Collection,没有增加任何方法，而List却增加了和索引相关的一些方法。4.1 实现类（HashSet、linkedHashSet、TreeSet） 4.1.1 HashSet
HashSet实现了Set接口，底层使用HashTable哈希表存储结构（数组+链表）
优点：添加速度快、查询速度快、删除速度快
缺点：无序
【验证无序的、不允许重复】
import java.util.HashSet;
import java.util.Set;
public class SetDemo1 {
public static void main(String[] args) {
Set set = new HashSet<>();
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("Hello");
set.add("java");
set.add("world");
set.add("Py");
set.add("a");
set.add("b");
set.add("c");
set.add("d");
set.add("Hello");
set.add("java");
set.add("world");
set.add("Py");
// 根据底层代码分析，add去重的原理是：hashCode(),equals()
for (String s : set) {
System.out.println(s);
}
}
}
HashSet的底层使用的是HashMap，所以底层结构也是哈希表HashSet的元素到HashMap中做key,value统一是一个 Object() 4.1.2 linkedHashSet
linkedHashSet是继承了HashSet类，也是采用的哈希表的存储结构，但是同时使用链表维护次序。
优点：相比于HashSet,linkedHashSet是有序的【按照添加顺序】
4.1.3 TreeSetTreeSet实现了Set接口，采用二叉树（红黑树）的结构【红黑树：是一个二叉平衡树，左边都小于根节点，右边都大于根节点，并且两侧的高度差不会超过1】
优点：有序（按照元素大小顺序）、在按照内容查询时，速度比List要快【有序：对红黑树进行中序遍历先左再根再右，从而得到一个由小到大的一个顺序】
缺点：查询速度没有HashSet快
小结： 所以查询速度：List: O(n)< TreeSet:O(log2^n) 【自然排序】 任意对象放入HashSet、linkedHashSet 等底层是哈希表的集合中，必须重写hashCode()、equals()两个方法。【自带的一些类已经重写过了，如String,但是自己创建的类一定要重写，否则他们放入集合中不会进行去重】 任意对象放入TreeSet等底层结构是红黑树的集合中，都需要实现Comparable接口，并实现其方法CompareTo() ->这是一个内部比较器。 Comparable接口至多制定一种规则，如果希望按照多种规则进行排序，可以使用外部比较器Comparator。【注：底层代码优先调用外部比较器】 【Comparator外部比较器】 TreeSet底层使用的是TreeMap,所以底层结构也是红黑树TreeSet的元素e是作为TreeMap的key存在的，value统一为一个Object()
5. Map接口的主要实现类
相关方法： HashMap实现了Map接口，采用Hashtable哈希表存储结构（数组+链表）,哈希表可以保证Key的唯一性。 优点：添加、查询、删除速度都很快 缺点：Key是无序的 JDK1.7及其之前，HashMap底层就是一个table数组+链表实现的哈希表存储结构，链表的每一个节点就是一个Entry,其中包括：键Key、值value、键的哈希码hash、执行下一行节点的引用next四部分。 JDK1.7中HashMap的主要成员变量及其含义： static final int DEFAULT_INITAL_CAPACITY=16 哈希表主数组的默认长度 static final int DEFAULT_LOAD_FACTOR=0.75f 默认的装填因子 transient Entry 若添加的元素超过（装填因子*数组长度），则会引起哈希冲突 哈希表的主数组长度必须是2^n [n是初始容量] 哈希表的扩容有两个条件，1.添加元素前，它的size(总大小)>=threshold(阈值) 2.添加元素的存储位置table[bucketIndex] (桶的位置)不为空【若为空，则先不进行扩容，下次再判断是否扩容】 需要扩容时，哈希表扩容成原来容量的二倍 符合添加条件时，元素是添加到链表的最前面 添加Entry时，若发现了相同的key已经存在，就使用新的value替代旧的value，并且返回旧的value linkedHashMap继承了HashMap类，采用哈希表存储结构，同时使用链表进行次序的维护。 优点：除了继承了HashMap的优点外，linkedHashMap的Key是有序的（按照添加顺序有序） TreeMap实现了Map接口，采用二叉树的存储结构 优点：Key有序【是按照大小有序的】、查询速度比List快【按照内容查询】 缺点：查询速度没有HashMap快 小结: 查询速度 List < TreeMap < HashMap 底层结构就是红黑树，红黑树的结构包括了：key、value、left、right、parent、color 添加原理：
都是从根节点进行比较添加过程就是构造二叉平衡树的过程，会自动平衡平衡过程离不开比较，外部比较器会优先考虑，然后才是考虑内部比较器。如果两个比较器都没有，就要抛出异常
6.迭代器 Iterator
Iterator就是专门为遍历集合而生的，集合没有提供专门的遍历方法，而是由迭代器去完成的。Iterator的实现实际上就是迭代器设计模式的实现。 Collection、List、Set集合均可以，但是Map集合不行 >> 提供Iterator()方法的就可以将元素交给Iterator >>> 实现Iterable接口的集合类都可以使用迭代器遍历【由浅入深理解】 联系： for-each遍历集合时，底层使用的还是Iterator【编译器会直接变成迭代器进行遍历】 凡是可以使用for-each遍历集合时，那就一定能使用Iterator进行遍历 区别： for-each不仅能遍历集合，还能遍历数组，而Iterator只能遍历集合 使用for-each遍历集合时不能删除元素，直接删会抛异常ConcurrentModificationException并发修改的异常；而使用迭代器则可以删除 ListIterator继承了Iterator ListIterator和Iterator之间的关系与区别： 关联：它们都可以遍历List集合 区别： Iterator可以应用于更多的集合，像List 、Set及其子类；ListIterator只能用于List集合及其子类； 遍历顺序不同
Iterator只能顺序向后遍历；ListIterator还可以逆序向前遍历Iterator可以在遍历的过程中remover(); ListIterator可以在遍历的过程中remove()、add()、set()ListIterator可以定位当前索引位置，以及下一个nextIndex()【向后遍历】和前一个previousIndex()【向前遍历】；Iterator没有此功能 Collections是集合工具类，是为了方便集合的操作而存在的类。 相关方法： 添加元素 Collections.addAll(); 排序 Collections.sort(); 查找->前提是已经自然有序 Collections.binarySearch(); 最大值和最小值 Collections.max(); Collections.min(); 填充->就是将所有元素的值都变为一个值 Collections.fill(); 复制->将一个集合的内容复制到另一个集合里 Collections.copy(); 同步 【第一代集合类】最开始使用的集合是Vector和Hashtbale，它们线程安全，但是效率却很低； 【第二代集合类】所以后面有了ArrayList、HashMap集合的普及，它们虽然效率很快，但是线性不安全。 为了使效率又快，线性又安全，所以Collections提供了同步方法： Collections.synchronizedList();将线程转变成安全的 【第三代集合类】当然，在JDK1.5后便有了并发的结合类：CopyonWriterArrayList、CopyonWriterArraySetw、ConcurrentHashMap，它们不仅线程安全，而且效率也很快。它们都在java.util.concurrent包下，使用Lock锁。import java.util.TreeSet;
public class TreeSetDemo1 {
public static void main(String[] args) {
TreeSet
注意
import java.sql.Struct;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;
public class TreeSetDemo {
public static void main(String[] args) {
TreeSet
特点： 存储的键值对映射关系，根据key可以找到value
Map
5.1 实现类（HashMap、linkedHashMap、TreeMap）
5.1.1 HashMap
HashMap: key 唯一的、无序的 ->与HashSet特点相同
value 不唯一的、无序的 ->与Collection特点相同
5.1.1.1 HashMap底层解析
linkedHashMap: key 唯一的、有序的【添加顺序】 ->与linkedHashSet特点相同
value 不唯一的、无序的
5.1.3 TreeMap
TreeMap key 唯一的且不能为null的、有序的【按自然顺序】
value 不唯一的、无序的
5.1.3.1 TreeMap底层解析
boolean hasNext(); 判断是否存在另一个可访问的元素Object next(); 返回要访问的下一个元素void remove(); 删除上次访问返回的元素【若在循环中，直接删除元素，会报错（ConcurrentModificationException并发修改的异常），而在使用迭代器进行删除，不会报错】
6.2 使用范围
使用范围不同
7. Collections集合工具类
