泛型，数据结构，List接口，Set接口

泛型

泛型是什么？

在Java语言中，是一种类型参数，可以设置存储数据的类型。

泛型解决程序中的什么问题？

1.在创建集合对象时，明确集合中所存储元素的类型（限定类型）

2.泛型在使用在代码编写时期的技术方式（编译期技术）

·3.泛型在程序运行后，就擦除

泛型的使用？

泛型类

 //当不确定类中的某个属性使用什么类型时，可以用泛型表示public class 类名<T>{ } public class 泛型类<T>{ private T 变量; } //在创建泛型类对象时，明确类型 泛型类<Integer> 对象 = new 泛型类<Integer>();//泛型类中成员变量的类型为：Integer 泛型类<String> 对象 = new 泛型类<String>();//泛型类中成员变量的类型为：String

//泛型类： 当不能确类中成员变量具体使用类型时，可以用泛型表示class MyClass<T>{ private T obj; public T getObj() { return obj; } public void setObj(T obj) { this.obj = obj; }}public class GenerictyDemo1 { public static void main(String[] args) { //创建对象：指定泛型类型为String MyClass<String> mc = new MyClass<>(); mc.setObj(\"你好！\"); System.out.println(mc.getObj());//你好！ MyClass<Integer> mc1 = new MyClass<>(); mc1.setObj(412); System.out.println(mc1.getObj());//412 }}

泛型接口

当不确定接口中的某个方法参数使用什么类型、或方法的返回值使用什么类型时：可以用泛型表示

public interface 泛型接口<T>{ public void method(T a); } //情况1：在子类编写时，指定接口上泛型的具体类型 public class 子类 implements 泛型接口<String>{ //方法重写 public void method(String a){ } } /**情况2：在子类编写时，没有指定接口上的泛型。 意味着：子类也使用和接口相同的泛型了（子类：泛型类）*/ public class 子类<T> implements 泛型接口<T>{ //方法重写 public void method(T a){ } } 子类<Integer> 对象 = new 子类<>();//创建子类对象时，明确了泛型的类型

//自定义泛型接口public interface MyCollection<T> { public void add(T param);}//子类在实现接口时，明确了接口上泛型的具体类型public class MyCollectionImpl implements MyCollection<Integer>{ @Override public void add(Integer param) { }}//子类在实现接口时，继承了接口上一样的泛型public class MyCollectionImpl2<T> implements MyCollection<T> { @Override public void add(T param) { }}public class Test1 { public static void main(String[] args) { //子类实现接口时，明确了接口上泛型的类型 MyCollectionImpl myCollection = new MyCollectionImpl(); myCollection.add(100); }}public class Test2 { public static void main(String[] args) { //子类实现接口时，没有指定泛型类型（子类使用了和接口一样的泛型） //创建子类对象时，明确泛型类型 MyCollectionImpl2<String> myCollectionImpl2 = new MyCollectionImpl2<>(); myCollectionImpl2.add(\"字符串\"); }}

泛型方法

的作用：声明该方法是泛型方法，T是一个类型变量，而不是具体类。

 //语法格式，在方法的返回值类型前，加上泛型 修饰符号 <泛型> 返回值类型 方法名( 泛型 参数1 , ...){ //方法体 } /**当前类没有声明为泛型类，但该类中的方法参数或方法返回值不确定类型时： 使用泛型方法*/ public <T> void method(T param){ } //当调用方法时，向方法中传递参数的类型，就是泛型的类型

public class Test { public static void main(String[] args) { //创建集合 ArrayList<String> list= new ArrayList<>(); list.add(\"java\"); list.add(\"mysql\");//String[] strs = new String[list.size()]; //在调用方法时，以传递的参数作为泛型的类型 String[] strings = list.toArray( new String[2] ); System.out.println(strings[1]); System.out.println(strings[0]); }}

问题：开发时选择哪个泛型定义？第1.先明确要定义的是接口还是类 ·当类中的成员变量，在不确定具体使用哪种类型时，可以使用：泛型 表 示类型 ·当接口中方法，在不确定方法参数类型或方法返回值类型时，可以使用： 泛型 表示类型第2.在编写工具类时，工具类中的方法参数或方法返回值，不确定具体类型， 可以使用： 泛型问题：泛型定义的语法//泛型类public class 类名<T,E,X,Y>{ private T name; private E a; private X n; private Y m; public 类名(T name , E a , X n ,Y m){ }}new 类名<String,Integer,Double,Student>();//泛型接口public interface 接口名<T,E>{}//泛型方法public <T> T 方法名(T 参数名){}问题： 怎么明确泛型指定的具体类型（指定泛型上的类型）//泛型类： 在创建对象时，指定泛型类型类名<String> 对象 = new 类名<>();//泛型接口： 1.在子类实现接口时，明确指定了泛型类型 //2.子类继承接口上的泛型（子类变为泛型类）interface 接口<T>{ public void method(T n); public T get();}class 子类 implements 接口<Integer>{ public void method(Integer n){ } public Integer get(){ }}class 子类<T> implements 接口<T>{ public void method(T n){ } public T get(){ }}//泛型方法：public class 类{ public <T> T getInstance(T param){ }}Student stu = 类对象.getInstance( new Student() )

泛型通配符

泛型中的通配符： ? (任意类型)

通常在开发中，?是和泛型的上下限一起使用

泛型的下限//指定泛型中的最小类型<? super 最小类型> ? 可以是最小类型? 可以是父类型 -----------------------------------------------------泛型的上限//指定泛型中的最大类型<? extends 最大类型> ? 可以是最大类型? 可以是子类型 

//父类public class Person { private String name; private int age; public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; }}//子类public class Student extends Person { private double score; public void study(){ } public double getScore() { return score; } public void setScore(double score) { this.score = score; }}//子类public class Worker extends Person { private double money; //工作 public void work(){ } public double getScore() { return money; } public void setScore(double money) { this.money = money; }}public class Test1 { public static void main(String[] args) { //创建集合对象时，指定元素类型 //在java中有多态的概念，但是泛型中没有多态 //ArrayList list = new ArrayList(); //在语法定义层面，可以使用： 泛型的通配符 ? (任意类型) //ArrayList list = new ArrayList(); //ArrayList students = new ArrayList(); ArrayList<Student> students = new ArrayList<>(); method(students); ArrayList<Worker> workers = new ArrayList<Worker>(); method(workers); ArrayList<String> list = new ArrayList<>();// method(list); }// public static void method( ArrayList list ){//// list.add(new Student());//// list.add(new Worker());//会报错//// } public static void method( ArrayList<? extends Person> list ){ }}public class Test2 { public static void main(String[] args) { ArrayList<Object> list1 = new ArrayList<>(); show1(list1); ArrayList<Double> list2 = new ArrayList<>(); show2(list2); } //接收的参数类型是：Number或其父类型（Object） public static void show1(ArrayList<? super Number> list){ } //接收的参数类型是： Number或其子类型 public static void show2(ArrayList<? extends Number> list){ }}

数据结构

数据结构：就是一种存储数据的排列方式

栈（先进后出）

数据进入栈模型的过程称为：压/进栈

数据离开栈模型的过程称为：弹/出栈

队列：（队列是一种线性结构）

特点：先进先出

数据从后端进入队列模型的过程称为：入队列

数据从前端离开队列模型的过程称为：出队列

数组结构

数组在内存中的体现是一块连续存储数据的空间

特点：

1.查询快

2. 增删元素效率慢-

例：在已学习的ArrayList集合，底层就是使用：数组结构，ArrayList集合的特点：查询快、增删慢

链表

链表结构

在内存中是使用节点来存储数据

节点 = 数据 + 地址- 链表：有头、有尾

分类：

1. 单向链表：只能从头到尾

2. 双向链表：可以从头到尾，也可以从尾到头 （提高查询效率）

代表集合类：LinkedList

树

二叉树：

以根节点为坐标，小于根节点的数据存储在左边，大于根节点的数据存储在右边

度：

每一个节点的子节点数量，二叉树中，任意一个节点的度要小于等于2

平衡二叉树

二叉树左右两个子树的高度差不超过1

任意节点的左右两个子树都是一棵平衡二叉树

当添加一个节点之后，该树不再是一棵平衡二叉树：通过旋转方式平衡二叉树

二叉查找树

二叉查找树，又称二叉排序树或者二叉搜索树。

特点：

 1，每一个节点上最多有两个子节点 2，每个节点的左子节点比当前节点小 右子节点比当前节点大

红黑树

平衡二叉B树

每一个节点可以是红或者黑

红黑树不是高度平衡的，它的平衡是通过“自己的红黑规则\"进行实现的

红黑树小结

红黑树不是高度平衡的，它的平衡是通过\"红黑规则\"进行实现的

规则如下：

1. 每一个节点或是红色的，或者是黑色的。
2. 根节点必须是黑色
3. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的；
4. 不能出现两个红色节点相连的情况
5. 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；

List集合

Java语言中集合体系划分：1.Collection (接口)； 2.Map （接口）

java.util.Collection集合： 是一个接口（无法实例化）

1.java.util.List集合（接口） -常用子类：ArrayList 、 LinkedList，Vector（不常用）

2. java.util.Set集合（接口） -常用子类：HashSet、LinkedHashSet、TreeSet

java.util.List集合：

1.带有索引

2. 存储的元素的顺序和获取元素的顺序一致

3.可以存储重复元素

因为List集合可以使用索引，故围绕着索引，设计很多API方法：

List中特有的方法

//添加元素

List集合.add( 索引 ， 元素值) //向List集合中指定索引位置上，添加元素 //如指定索引位置上已有索引，会自动后向移动

//修改元素

List集合.set( 索引 ， 元素值) //修改List集合中指定索引位置上的元素值

//删除元素

List集合.remove(索引) //删除List集合中指定索引位置上的元素值

//获取元素

List集合.get(索引);//返回集合中指定位置的元素。

public class ListDemo1 { //验证List集合的特性 public static void main(String[] args) { //创建List集合（多态、泛型） List<Integer> list = new ArrayList<>(); //添加元素 list.add(100); list.add(300); list.add(200); list.add(300);//允许存储重复元素 System.out.println(list); for (int i = 0; i < list.size(); i++) { //根据索引取出集合中的每一个元素 Integer num = list.get(i); System.out.println(num); } }}运行结果：[100, 300, 200, 300]100300200300

常用子类：

LinkedList集合

特性:

1. 底层使用双向链表结构（有头有尾）

2. 增删快 、查询慢

3. 具有自己的特有方法（围绕着链表的头和尾设计）

// 添加元素addFirst(元素）//把元素添加到链表头部addLast（元素）//把元素添加到链表尾部 // 删除元素removeFirst()//移除并返回此列表的第一个元素removeLast()//移除并返回此列表的最后一个元素。// 获取元素getFirst()//返回此列表的第一个元素getLast()//返回此列表的最后一个元素。

public class LinkedListDemo1 { public static void main(String[] args) { //创建LinkedList集合 LinkedList<Integer> list = new LinkedList<>(); list.add(100); list.add(200); list.add(300); list.add(200);//允许存储重复元素 System.out.println(list);//存取有序//[100, 200, 300, 200] //LinkedList集合中的特有方法 list.addLast(1);//添加到链表的末尾 list.addFirst(999);//添加到链表头部 System.out.println(list);//[999, 100, 200, 300, 200, 1] System.out.println(list.getFirst());//999 System.out.println(list.getLast());//1 list.removeFirst(); list.removeLast(); System.out.println(list);//[100, 200, 300, 200] }}

ArrayList

- 特性：

1. 底层使用数组结构

2. 查询快、增删慢

3. 具有List集合中的特点

Set集合 (接口）

1. 没有索引

2. 存取元素不保证顺序

3. 不允许存储重复元素

Set集合

Set集合中方法全部来自Collection集合，Set集合也是Collection集合的子类型，没有特有方法。Set比Collection定义更严谨。

Set集合要求：

1. 元素不能保证添加和取出顺序（无序）
2. 元素是没有索引的(无索引)
3. 元素唯一(元素唯一)

Set常用子类

HashSet集合 --哈希表结构

特点：

1. 没有索引 （无索引）

2. 存取元素不保证顺序 （无序）

3. 不能存储重复元素 （去重）

1.哈希表去重原理：存储的元素必须重写hashCode、equals方法）

2. JDK1.8底层优化了哈希表（当链表长度超出8，就自动转为红黑树）

3.哈希表结构的集合，操作效率会非常高。

public class SetDemo1 { //验证：Set集合的特点 public static void main(String[] args) { //创建Set集合 Set<String> set= new HashSet<>(); set.add(\"html\"); set.add(\"mysql\"); set.add(\"java\"); //set.add(\"mysql\");//不允许存储重复元素 System.out.println(set);//存取元素顺序不保证一致//[java, html, mysql] //因为Set集合没有索引，所以不能使用普通for循环遍历 //Set集合遍历 ： 迭代器 -> 增强for for (String s : set) { System.out.println(s); } }}

public class HashSetDemo1 { public static void main(String[] args) { //创建HashSet集合 HashSet<String> set = new HashSet<>(); //添加元素 set.add(\"html\"); set.add(\"javascript\"); set.add(\"java\"); set.add(\"mysql\"); //判断集合是否包含某个元素 if(set.contains(\"html\")){ set.remove(\"html\"); } //遍历set for (String s : set) { System.out.println(s);//java mysql javascript } }}

public class Student { private String name; private int age; public Student() { } public Student(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } @Override public int hashCode() { return Objects.hash(name, age); } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return \"Student{\" + \"name=\'\" + name + \'\\\'\' + \", age=\" + age + \'}\'; }}public class HashSetDemo2 { //使用HashSet集合存储：Student对象 （要求：不能有重复对象） public static void main(String[] args) { //创建HashSet集合 HashSet<Student> studentSet = new HashSet<>(); //向集合中添加学生对象 studentSet.add(new Student(\"熊大\", 24)); studentSet.add(new Student(\"光头强\", 24)); studentSet.add(new Student(\"熊二\", 22)); studentSet.add(new Student(\"熊大\", 24)); //遍历集合 for (Student student : studentSet) { System.out.println(student); } /*注意：当使用HashSet存储自定义对象时，可能会出现存储了重复内容的对象 解决方案： 在自定义类中重写hashCode()和equals方法 * */ }}运行结果：Student{name=\'熊二\', age=22}Student{name=\'光头强\', age=24}Student{name=\'熊大\', age=24}

LinkedHashSet集合--链表+哈希表结构

特点：

1. 没有索引

2. 不能存储重复元素

3. 存取元素顺序一致

• 底层：哈希表+链表（保证存储元素的顺序）

LinkedHashSet 特性：

1. 底层使用哈希表+链表的结构

2. 哈希表用来去重、链表用来保证存取元素的顺序

public class LinkedHashSetDemo1 { //验证： 存取元素顺序 public static void main(String[] args) { //创建集合对象 LinkedHashSet<Integer> set = new LinkedHashSet<>(); set.add(200); set.add(300); set.add(100); set.add(100); for (Integer integer : set) { System.out.println(integer); } }}运行结果：200300100

TreeSet集合--红黑树，TreeMap

特性：

1. 底层使用树(红黑树)结构

2. 不能存储重复元素

3. 不具备索引

4. 存储的元素会按照规则进行排序（想要使用TreeSet，需要制定排序规则)

TreeSet集合：

- 底层使用：

红黑树

• 去重、排序（拿树中已存在的元素 ， 和要存储的元素进行比较[比较大小：0、正数、负数] ）

• 存储自定义元素，要保证自定义元素有实现java.lang.Comparable接口

1.JDK提供的：String、Integer 等类，都已具备自然排序（实现Comparable接口）

• String类默认就已有排序规则（按照字典顺序从小到大排序）需求：在TreeSet中存储的String类型数据，按照字符串长度从大到小排序

• 结论：使用自然排序做不到（String类是final修饰，不能继承）

public class TreeSetDemo1 { public static void main(String[] args) { //创建集合对象 TreeSet<Integer> set = new TreeSet<>(); //添加元素 set.add(100); set.add(88);//所存储元素会按照规则进行排序 set.add(99); set.add(55); System.out.println(set);//[55, 88, 99, 100] }}

2.在TreeSet集合中存储：自定义类型 ，需要制定排序规则

TreeSet构造方法：

TreeSet排序

public TreeSet() //默认使用自然排序public TreeSet( Comparator c ) //指定比较器对象 Comparator接口（泛型接口）： 比较器int compare(Object obj1 , Object obj2) //比较两个元素的大小： 0、正数、 负数

自然排序

- 就必须保证自定义类型，有实现java.lang.Comparable接口，并重写compareTo方法

-如果自定义类型，没有实现Comparable接口，在存储到TreeSet集合中时，会引发异常

//比较大小： 0表示相同 、 负数表示小 正数表示大public int compareTo(E e){ 自然排序规则 //返回值有三种： 正数 、 负数 、 0 （底层红黑树需要）}

//使用空参构造创建TreeSet集合//自定义的Student类实现Comparable接口//重写里面的compareTo()方法public class Student implements Comparable<Student>{ private String name; private int age;// @Override// public int compareTo(Object o) {// return 0;// } @Override public int compareTo(Student stu) { //编写排序规则：先按照姓名排序，姓名相同按照年龄排序 //this：当前对象 //stu：传递过来的对象,比较对象 //String类本身实现了Comparable接口，并重写compareTo()方法（结论：String类自带自然排序） int result = this.name.compareTo(stu.name); //返回值为0，表示当前存入的元素跟集合中元素重复 if(result == 0){ //按照年龄排序  result = stu.age - this.age;//降序 //result = this.age - stu.age; // 数值升序 } return result; }//返回值含义总结//• 负值：当前对象应排在比较对象前面//• 零：两对象相等（排序位置相同）//• 正值：当前对象应排在比较对象后面 public Student() { } public Student(String name, int age) { this.name = name; this.age = age; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; return age == student.age && Objects.equals(name, student.name); } @Override public int hashCode() { return Objects.hash(name, age); } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return \"Student{\" + \"name=\'\" + name + \'\\\'\' + \", age=\" + age + \'}\'; } //按照年龄从小到大排，如果年龄一样，则按照姓名首字母排序 // 如果姓名和年龄一样，才认为是同一个学生对象，不存入。// @Override// public int compareTo(Student stu) {// //按照年龄// int result = this.age - stu.age;// //年龄相同：比较姓名// if(result == 0){// result = this.name.compareTo(stu.name);// }// return result;// }}public class TreeSetDemo2 { //使用：TreeSet集合存储自定义对象 public static void main(String[] args) { //创建集合对象 TreeSet<Student> set = new TreeSet<>(); //添加元素 //set.add(new Student(\"熊大2\",23)); set.add(new Student(\"bbb\",23)); set.add(new Student(\"ccc\",22));// set.add(new Student(\"aaa\",24)); set.add(new Student(\"aaa\",23)); set.add(new Student(\"aaa\",24)); //遍历集合 for(Student student:set){ System.out.println(student); } }}/**Student{name=\'aaa\', age=24}Student{name=\'aaa\', age=23}Student{name=\'bbb\', age=23}Student{name=\'ccc\', age=22}*/

比较器排序

比较器排序，就是让TreeSet集合构造方法接收Comparator接口的实现类对象

重写Comparator接口中的 compare(T num1,T num2)方法 , 指定排序规则

注意 : num1代表的是当前往集合中添加的元素 , num2代表的是集合中已经存在的元素,排序原理与自然排序相同!

//比较器排序Comparator的使用步骤//比较器排序，就是让TreeSet集合构造方法接收Comparator接口的实现类对象//重写Comparator接口中的 compare(T o1,T o2)方法 , 指定排序规则//注意 : o1代表的是当前往集合中添加的元素 , o2代表的是集合中已经存在的元素,排序原理与自然排序相同!class MyComparator implements Comparator<String>{ @Override public int compare(String str1, String str2) { //str1 : 要存储的字符串数据 //str2 ： 已存在的字符串数据 int result = str1.length() - str2.length(); //当两个字符串长度相同时：按照字符串字典顺序排序 if(result == 0){ result = str1.compareTo(str2); } return result; }}public class TreeSetDemo3 { public static void main(String[] args) { TreeSet<String> set = new TreeSet<>(new MyComparator()); set.add(\"Java\"); set.add(\"oracle\"); set.add(\"JavaSprient\"); set.add(\"tecahhnd\"); System.out.println(set); }}------------------------------------------------------------[Java, oracle, tecahhnd, JavaSprient]

//自定义对象不具备自然排序的规则public class Teacher { private String name; private int age; public Teacher() { } public Teacher(String name, int age) { this.name = name; this.age = age; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return \"Teacher{\" + \"name=\'\" + name + \'\\\'\' + \", age=\" + age + \'}\'; }}//按照年龄从小到大排，如果年龄一样，则按照姓名首字母排序//如果姓名和年龄一样，才认为是同一个学生对象，不存入。public class TreeSetDemo4 { //使用比较器实现排序规则public static void main(String[] args) { //创建TreeSet集合，并指定比较器排序规则TreeSet<Teacher> teacherSet = new TreeSet<>(new Comparator<Teacher>() { @Override public int compare(Teacher tea1, Teacher tea2) { //比较年龄 int result = tea1.getAge() - tea2.getAge(); //当年龄相同时比较姓名 if(result == 0){  result = tea1.getName().compareTo(tea2.getName()); } // 返回比较结果:0 正数，负数 return result; } }); teacherSet.add(new Teacher(\"zhangsan\",23)); teacherSet.add(new Teacher(\"lisi\",24)); teacherSet.add(new Teacher(\"wangwu\",23)); teacherSet.add(new Teacher(\"zhangsan\",24)); teacherSet.add(new Teacher(\"lisi\",24)); for (Teacher teacher: teacherSet) { System.out.println(teacher); } }}-------------------------------------------------Teacher{name=\'wangwu\', age=23}Teacher{name=\'zhangsan\', age=23}Teacher{name=\'lisi\', age=24}Teacher{name=\'zhangsan\', age=24}

两种方式中，关于返回值的规则：

如果返回值为负数，表示当前存入的元素是较小值，存左边

如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存

如果返回值为正数，表示当前存入的元素是较大值，存右边

哈希表结构

HashSet hm = new HashSet();

• 底层是使用大小为16的数组+链表组成的存储方式

• 哈希表存储数据的方式 （ 借助：哈希值[存储位置] ）

拿要存储的元素，结合哈希算法， 计算出哈希值(存储位置) // 调用： 元素.hashCode() 判断 ： 计算出的存储位置上是否有元素存在 情况1 ： 没有元素存在 => 直接存储 情况2 ： 已有元素存在拿要存储的元素 和 已经存在的元素 进行比较（比较内容是否相同） //元素.equals()   相同： （重复元素） => 不存储  不相同： （不重复元素）再次拿当前存储空间作为算法因子，再次进行哈希算法，计算新的存储空间 

哈希值

哈希值：是JDK根据对象的地址或者对象的属性算出来的int类型的数值

Object类中有一个方法可以获取对象的哈希值

public int hashCode（）；//返回对象的哈希值

对象的哈希值特点：

1.同一个对象多次调用hashCode（）方法返回的哈希值是相同的

2.默认情况下，不同对象的哈希值是不同的，而重写hashCode（）方法，不同对象的哈希值有可能相同

哈希表

1.JDK8之前，底层采用数组+链表实现

2.JDK8以后，底层采用数组 + 链表/红黑树实现

从JDK1.8开始，哈希表底层进行优化，使用：数组+链表/红黑树

• 从链表 => 红黑树时机： 当链表的长度>8，自动 把链表转换为红黑树