#Java-集合进阶-Collection、Set

1.Collection

Collection是单列集合顶层接口：

• 它表示一组对象, 这些对象也称为Collection的元素
• JDK 不提供此接口的任何直接实现，它提供更具体的子接口(如Set和List)实现

创建Collection对象的方法：

• 使用多态的方式

Collection<String> co = new ArrayList<>();

• 使用它的实现类创建对象：

ArrayList<String> co = new ArrayList<>();

这里给出图例：来自黑马程序员

• 蓝色表示接口
• 红色是实现类

我们前面学的ArrayLIst只是集合的一小部分

1.1 Collection集合常用方法

1. 添加元素

• 细节1:如果我们要往List系列集合中添加数据,那么方法永远返回true,因为List系列的是允许元素重复的。
• 细节2:如果我们要往Set系列集合中添加数据,如果当前要添加元素不存在,方法返回true,表示添加成功。
  如果当前要添加的元素已经存在,方法返回false,表示添加失败。
  因为Set系列的集合不允许重复。

coll.add("aaa");
coll.add("bbb");
coll.add("ccc");
System.out.println(coll);

2. 删除

因为Collection中定义的是List和Set中共性的内容，因为set中是没有索引的所以删除的方法中也没有索引。

• 集合中存在这个元素删除成功返回true
• 不存在返回false

3. contains(Object o)

这个方法在底层是依靠传入的数据的对象中的equals方法来判断内容（属性）是否存在，所以在我们自定义的类中，要重写equals方法，否则会继承Object中的方法：比较的是地址值

但是我们需要的是比较内容（属性）

在我们的编译器中右键生成，会有重写equals和hash方法的快捷方式

1.2 迭代器的使用

在Collection所代表的集合中有Set，它是没有索引的，所以为了实现遍历。我们引出迭代器的概念，因为迭代器的遍历是不依赖索引的

遍历的步骤：

1. Iterator< E > iterator(): 返回此集合中元素的迭代器,通过集合对象的iterator()方法得到，默认指向集合的零索引的元素

ArrayList<String> ar = new ArrayList<>();
Iterator<String> it = ar.iterator();

2. boolean hasNext(): 判断当前位置是否有元素可以被取出，当前位置存在元素返回true，不存在返回false

3. E next(): 获取当前位置的元素, 将迭代器对象移向下一个索引位置

配合循环去使用代码示例：

//获取迭代器对象
ArrayList<String> ar = new ArrayList<>();
Iterator<String> it = ar.iterator();
//使用循环获取元素
while(it.hasNext()) {
	System.out.println(it.next());
}

注意事项：

• 一个迭代器对象移动到集合末尾外（集合最大索引 + 1的位置），这时再次调用next()方法，就会报错
• 一个迭代器遍历完毕，它所指向的元素位置不会复位，如果需要再次遍历，可以再创建另一个迭代器对象
• 循环中建议只用一次next()方法，因为如果多次调用，但是集合已经遍历完毕，但是next()方法还没有调用完毕，就会报错（第一点注意）
• 迭代器遍历时候（循环中），不能使用集合的方法进行增删元素，但是可以用迭代器的方法删除元素（不能增加元素）

1.3 增强for

• 增强for的底层就是迭代器, 为了简化迭代器的代码书写的。

• 它是JDK5之后出现的,其内部原理就是一个 Iterator迭代器

• 所有的单列集合和数组才能用增强for进行遍历。

格式：

for(集合/数组中元素的数据类型 变量名 :  集合/数组名) {

	// 已经将当前遍历到的元素封装到变量中了,直接使用变量即可

}

集合/数组中元素的数据类型 变量名，这里的变量实际上只是一个第三方用来展示的变量，在循环中对这个变量进行修改也不会影响集合中的数据

String name = "lshhhh";
for(String s : name) {
	System.out.println(s);
}

1.4 lambda表达式遍历

lambda表达式遍历:

default void forEach(Consumer <? super T> action);

Consumer是一个函数式接口，为了方便理解我们先用匿名内部类的方法进行传参

//1.创建集合并添加元素
Collection<String> coll = new ArrayList<>();
coll.add("zhangsan");
coll.add("lisi");
coll.add("wangwu");
//2.利用匿名内部类的形式
coll.forEach(new Consumer<String>() {
	@Override
	public void accept(String s) {
		System.out.println(s);
	}
}) ;

使用匿名内部类的解释：

• 在底层其实也会自己遍历集合,依次得到每一个元素
• 把得到的每一个元素,传递给下面的accept方法(我们在匿名内部类中重写的方法)
• s 依次表示集合中的每一个数据

我们可以使用lambda表达式取优化代码：

//lambda表达式
coll.forEach(s -> System.out.println(s));

1.5 List集合

List集合的概述

• 有序集合,这里的有序指的是存取顺序
• 用户可以精确控制列表中每个元素的插入位置, 用户可以通过整数索引访问元素,并搜索列表中的元素
• 与Set集合不同, 列表通常允许重复的元素

Vector已经撤销

我们现在学习List接口中的方法，这些方法只能被它的实现类所使用

a.List中关于索引的方法

1.add()

private static void method1(List<String> list) {
        list.add(0,"qqq");
        System.out.println(list);
    }

• 在此集合中的指定位置插入指定的元素
• 原来位置上的元素往后挪一个索引.

2. remove()

 private static void method2(List<String> list) {
        String s = list.remove(0);
        System.out.println(s);
        System.out.println(list);
    }

在List集合中有两个删除的方法

• 第一个 删除指定的元素,返回值表示当前元素是否删除成功
• 第二个 删除指定索引的元素,返回值表示实际删除的元素

那么我们在使用这个方法的使用到底使用的是哪一个：

• 当我们在调用方法的时候，如果出现了重载现象，会优先调用形参和实参类型一样的方法

例如：

ArrayList<Integer> arr = new ArrayList<>();
arr.add(1);
arr.add(2);
arr.add(3);
arr.remove(1);

上面的代码中是会删除元素1，还是索引为1的元素2

• 会删除2

因为remove（int index），中形参int类型，传入的数据1，也是int类型

如果我们想使用删除对应元素的方法remove(Object o)，就要把基本数据类型进行手动装箱

Integer i = Integer.valueOf(1);
arr.remove(i);

b.在List实现类中可以使用的遍历方式

1. 迭代器
2. 列表迭代器
3. 增强for
4. Lambda表达式
5. 普通for循环

我们主要讲 普通for循环和列表迭代器，其他的遍历方式和在Collection中讲的一样

• 普通for循环

size方法跟get方法还有循环结合的方式，利用索引获取到集合中的每一个元素

for (int i = 0; i < list.size(); i++) {
     //i:依次表示集合中的每一个索引
     String s = list.get(i);
     System.out.println(s);
}

• 列表迭代器

获取一个列表迭代器的对象，里面的指针默认也是指向0索引的

额外添加了一个方法：add()在遍历的过程中，可以添加元素，添加元素的位置是当前遍历元素的后面

ListIterator<String> it = list.listIterator();
while(it.hasNext()){
    String str = it.next();
    if("bbb".equals(str)){
        //qqq
        it.add("qqq");
    }
}

c.总结

• 迭代器遍历：在遍历的过程中需要删除元素,请使用迭代器。

• 列表迭代器：在遍历的过程中需要添加元素,请使用列表迭代器。

• 增强for遍历和Lambda表达式：仅仅想遍历,那么使用增强for或Lambda表达式。

• 普通for：如果遍历的时候想操作索引,可以用普通for。

1.6 数据结构

1.栈

2.队列

3.数组

4.链表

5.二叉树

6.二叉查找树

7.平衡二叉树

8.红黑树

2.泛型

在JDK5才使用泛型，所以在JDK5之前的集合操作是比较麻烦的

没有泛性的集合在添加元素的时候是可以添加任何的引用类型，但是在添加的时候使用的是多态的方式
添加数据的类型规定是：Object
但是我们都知道泛型有一个弊端：用泛型创建的对象不能使用子类中特有的方法

所以在JDK5之前获取元素之后要进行操作需要使用强制类型转换，因为获取出来的类型都是Object类

所以在之后提出类泛型的概念，但是需要我们注意的是，Java中的泛型是伪泛型

泛型只是在编译阶段为我们在集合中输入数据进行了限制，但是在集合中数据还是按照Object类型来存储，只是在获取数据的时候进行了自动的强制转换

泛型需要注意的细节：

• 泛型中不能写基本数据类型
• 指定泛型的具体类型后,传递数据时,可以传入该类类型或者其子类类型
• 如果不写泛型,类型默认是Object

总的来说泛型的出现是为了统一集合的数据类型

a.泛型的其他应用

1.泛型类

当我们在定义一个类的时候不确定这个类中传入的参数是什么类型，就可以使用泛型类，在这个类中所有的方法都可以使用这个类型
细节：

• 需要在类名后面加上：< E >
• 其中一部分方法的参数类型或者返回值类型也要是泛型
• 其中的E只是代表泛型的类型，可以用其他字母K，T，V等代替

代码示例：自己写一个集合方法

//当我在编写一个类的时候,如果不确定类型,那么这个类就可以定义为泛型类。
public class MyArrayList<E> {
	Object[] obj = new Object[10];
	int size;

	/*
	E:表示是不确定的类型。该类型在类名后面已经定义过了。
	e:形参的名字,变量名
	* */
	public boolean add(E e){
		obj[size] = e;
		size++;
		return true;
	}
	
	public E get(int index){
		return (E)obj[index];
	}
	
	@Override
	public String toString() {
		return Arrays.toString(obj);
	}
}

b.泛型方法

当只有一个或者少个方法的参数类型是不确定的，我们无需使用泛型类的方法引入泛型。可以使用泛型方法：
泛型方法的格式：

修饰符<E> 返回值类型 方法名（参数类型 形参）{};

代码示例：

public static<E> void addAll(ArrayList<E> list, E...e) {
 	for (E element : e) {
 		list.add(element);
 	}
 }

我们在测试类中就可以使用：

ArrayList<String> list = new ArrayList<>();
AddAll.addAll(list,"lsh","ljh","hhh");

c.泛型接口

泛型接口的定义：

修饰符 interface 接口名<类型>{};

举例：Java定义好的接口

public interface List<E>{};

使用泛型接口的方法：

1. 实现类给出具体类型：实现类中所有的泛型被替换为具体的类型

public class MyList implements List<String> {};
//创建实现类的对象
MyList mylist = new Mylist();

2. 实现类延续泛型，在创建实现类对象的时候确定具体类型

public class MyList<E> implements List<String> {};
//创建实现类对象
MyList<String> mylist = new Mylist<>();

2.泛型的通配符

泛型不能继承，但数据可以继承

1. 泛型不能继承

//我们使用上面的代码作为例子
public static<GrandFather> void addAll(ArrayList<GrandFather> list) {}
//一个继承体系
 class GrandFather{}
 class Father extends GrandFather{}
 class Son extends Father{}
//在测试类中
addAll(GrandFather);
addAll(Father);//报错
addAll(Son);//报错

泛型规定的类型，在传入的时候就只能传入这个类型

2. 数据可以继承（多态）

//创建一个集合，泛型为GrandFather
ArrayList<GrandFather> list = new ArrayList<>();
list.add(Father);
list.add(Son);

泛型的通配符：

• ? 也表示不确定的类型

也可以进行类型的限定

• ? extends E:表示可以传递E或者E所有的子类类型
• super E:表示可以传递E或者E所有的父类类型

应用场景:

1. 如果我们在定义类、方法、接口的时候,如果类型不确定,就可以定义泛型类、泛型方法、泛型接口。
2. 如果类型不确定,但是能知道以后只能传递某个继承体系中的,就可以泛型的通配符

public static void addAll(ArrayList< ? extends GrandFather> list) {}

当使用泛型通配符的时候不用在修饰符的后面加上泛型

a. 泛型综合小案例

略

3.Set集合

Set系列集合

• 无序: 存取顺序不一致

//使用多态创建对象
Set<String> s = new HashSet<>();
boolean r1 = s.add("张三");
boolean r2 = s.add("李四");
System.out.println(s);
//输出的结果可能是：
李四,张三

• 不重复: 可以去除重复

• 无索引: 没有带索引的方法,所以不能使用普通for循环遍历,也不能通过索引来获取元素

Set集合的实现类

• HashSet:无序、不重复、无索引
• LinkedHashSet: 有序、不重复、无索引
• TreeSet:可排序、不重复、无索引
  
  接下来我们学习图片中Set相关的数据结构的部分

3.1数据结构

1.二叉树

2.二叉查找树

3.平衡二叉树

4.红黑树

3.2 HashSet

• 底层数据结构是哈希表
• 存取无序
• 不可以存储重复元素
• 没有索引, 不能使用普通for循环遍历

哈希表的存储方式是：通过对象的地址或者是属性值计算得到哈希值，通过哈希值得到数组索引把数据放在哈希表中。
下面a,b,c三点是讲解底层原理：

a.哈希值

• 哈希值是根据hashCode方法算出来的int类型的整数

• 该方法定义在Object类中,所有对象都可以调用,默认使用地址值进行计算

• 一般情况下,会重写hashCode方法,利用对象内部的属性值计算哈希值

因为一般情况下通过对象地址计算出来的哈希值并没有太大的意义

//得到的索引
int index = (数组长度 - 1) & 哈希值

1. 如果没有重写hashCode方法,不同对象计算出的哈希值是不同的
2. 如果已经重写hashcode方法,不同的对象只要属性值相同,计算出的哈希值就是一样的
3. 但是在小部分情况下,不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。(哈希碰撞)

b.哈希表：

• 在JDK8之前组成结构是：数组 + 链表

• 在JDK8之后组成结构是：数组 + 练表 + 红黑树

在JDK8以后，当链表长度超过8，数组长度大于等于64时，自动转换为红黑树

c.总结

上面我们说到哈希值和哈希表，值得注意的是如果集合中存储的时自定义对象则必须重写hashcode和equals方法

• 这样hashcode计算的就是属性值而不是地址值
• 同样equals方法比较的就是属性值而不是地址值

同样的Java已经为我们重写好了，右键生成中可以找到

回答三个问题：

1. 哈希表为什么存和取的顺序不一样：因为存的时候是按照哈希值计算出的数在进行一定的计算得到的索引，取的时候按照索引0开始使用equals方法比较查找，索引存取顺序不一致
2. 哈希表没有索引：因为哈希表在底层是由数组、链表、红黑树组成，数据结构的多样性使得它没法简单的规定索引
3. 哈希表的去重：使用hashcode得到位置，equals比较是否相等，相等则把这个元素舍弃，不相等存入

3.3 LinkedHashSet集合

底层是哈希表

• 有序、不重复、无索引。
• 这里的有序指的是保证存储和取出的元素顺序一致
• 原理:底层数据结构是依然哈希表, 只是每个元素又额外的多了一个双链表的机制记录存储的顺序。

正是因为多了双链表记录存储顺序的机制，在取的时候也是按照这个链表的顺序进行遍历，所以存取有序

3.5 TreeSet集合

底层是红黑树
它可以对存储到集合中的数据进行排序：

• 根据泛型的不同具有不同的排序规则
• Integer：默认从小到大
• String，char：默认ASCII码表中对应数字从小到大，String类型的略有不同，是先比较第一个字符，如果一样比较下一位，不一样直接比较成功。
• 我们同样可以自定义排序

a.自定义排序

这也是TreeSet集合的特点：自定义排序规则

1. 我们需要实现Comparable这个泛型接口
   1. 这是两种实现方法
   2. 在实现接口时确定泛型的类型
   3. 实现接口是延续泛型，在创建对象时候确定具体类型
2. 在自定义的类中重写compareTo方法，来定义规则

//创建一个学生类，成员对象是：姓名和年龄
@Override
public int compareTo(Student o) {
	//指定排序的规则
	//只看年龄,我想要按照年龄的升序进行排列
	return this.getAge() - o.getAge();
}

• this:表示当前要添加的元素
• o:表示已经在红黑树存在的元素

返回值:

• 负数: 认为要添加的元素是小的, 存左边
• 正数: 认为要添加的元素是大的, 存右边
• 0: 认为要添加的元素已经存在, 舍弃

非自定义的类，例如：String,Integer,Byte...Java已经重写了compareTo方法，不需要我们进行操作

b.修改默认排序

我们使用泛型：String,Integer,Byte....时，可能他们的默认排序规则不能满足我们的使用需求。这个时候我们就需要修改默认的排序

• 默认排序我们使用的是TreeSet的空参构造
• 现在我们修改默认排序可以使用另一个构造方法

TreeSet(comparator(? super E) comparator);

comparator是一个接口，我们要传入的是这个接口的实现类，在其中修改排序规则

代码示例：

要求:存入四个字符串,“c”,“ab”,"df”,"qwer”
按照长度排序,如果一样长则按照首字母排序
采取第二种排序方式:比较器排序

//创建一个泛型为String的TreeSet集合
TreeSet<String> s = new TreeSet<>(new comparator)
//1.创建集合
//o1:表示当前要添加的元素
//o2:表示已经在红黑树存在的元素
//返回值规则跟之前是一样的
TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
	@Override
	public int compare(String o1, String o2) {
		// 按照长度排序
		int i = o1.length() - o2.length();
		//如果一样长则按照首字母排序
		i = i == 0 ? o1. compareTo(o2)	 : i;
		return i;
)};

方法的返回值和自定义排序的规则相同：
返回值:

• 负数: 认为要添加的元素是小的, 存左边
• 正数: 认为要添加的元素是大的, 存右边
• 0: 认为要添加的元素已经存在, 舍弃

需要我们注意的是：当非自定义的对象我们使用了comparator比较器之后，在进行排序的时候就会默认按照我们比较器中重写的规则进行排序