复习
1.Collection根接口
增: boolean add(E e)
删: boolean remove(Object obj)
改: 无
查: 无
其他: clear isEmpty size contains toArray
2.迭代器: 遍历集合(与索引无关)
Iterator<集合的泛型> it = 集合对象.iterator();
while(it.hasNext()){
集合的泛型 变量名 = it.next();
}
增强for循环,就是迭代器的语法糖(简便格式)
for(数据类型 变量名 : 集合/数组){
System.out.println(变量名);
}
=========================
注意:使用迭代器的过程中,你不能直接通过代码对集合的元素进行增删操作.
如果你想增删元素,a.使用普通的fori循环 b.使用迭代器提供remove方法
3.泛型(理解)
给一个泛型类,比如ArrayList<E>,怎么使用??
ArrayList<String> arr = new ArrayList<String>();
ArrayList<Integer> arr = new ArrayList<Integer>();
4.4+1种数据结构
栈结构: 先进后出
队列结构: 先进先出
数组结构: 查询快,增删慢
链表结构: 查询慢,增删快
红黑树结构: 查询速度非常恐怖
今日内容
- List接口
List接口的实现类(ArrayList,LinkedList,Vector) - Set接口
Set接口的实现类(HashSet,LinkedHashSet,TreeSet) - Collections 专门操作集合的工具类
打乱顺序,排序(默认),自定义排序
List接口[重点]
List接口特点
- 继承了Collection接口
- List接口的特点:
1.有序的(Java中的有序的是指存取顺序保持一致,如存入2,1,3 取出也是2,1,3)
2.有索引的
3.元素可重复的
List接口中常用方法
- 继承Collection接口, 所以有Collection中的8个(7个常见,1个获取迭代器)
- List接口自己的特有方法(跟索引相关)
增: add(int index, E e)
删:remove(int index)
改:set(int index, E 新元素);
查:get(int index) - List接口的实现类
1.ArrayList集合 [重点]
2.LinkedList集合[重点]
3.Vector[了解]
ArrayList的数据结构以及使用
特点: 查询快,增删慢!!
- ArrayList集合的方法(7个Collection中的+1个迭代器+4个List中的)
- 数据结构:ArrayList集合底层采用的是数组结构.因此查询快,增删慢
LinkedList集合的数据结构以及使用
特点:查询慢,增删快
- LinkedList的方法(7个Collection中的+1个迭代器+4个List接口中的) 特有方法有8个:
public void addFirst(E e) :将指定元素插入此列表的开头。
public void addLast(E e) :将指定元素添加到此列表的结尾。
public E getFirst() :返回此列表的第一个元素。
public E getLast() :返回此列表的最后一个元素。
public E removeFirst() :移除并返回此列表的第一个元素。
public E removeLast() :移除并返回此列表的最后一个元素。
public E pop() :将指定元素添加到此列表的结尾。从此列表所表示的堆栈处弹出一个元素。底层为removeFirst()和此方法一样
public void push(E e) :将指定元素插入此列表的开头。将元素推入此列表所表示的堆栈。底层为addFirst() 和此方法一样
public boolean isEmpty() ：如果列表不包含元素，则返回true。
LinkedList集合数据存储的结构是链表结构方便元素添加、删除的集合。
LinkedList的使用
LinkedList的源码分析(了解)
- LinkedList的底层采用链表结构(双向链表)
- LinkedList这个类有两个成员变量
Node<E> first; 记录了开始节点
Node<E> last; 记录了结束节点 - 节点类Node,是这样的
它是LinkedList的内部类
private static class Node<E>{
E item; 该节点的数据域
Node<E> prev; 指针域,指向上一个节点
Node<E> next; 指针域,指向下一个节点
} - LinkedList的add方法
a.将新增的节点,添加到last节点之后
b.并且将size++,总的元素个数增加1 - LinkedList的get方法
a.先查找指定索引的那个节点(从前往后找,从后往前找)
b.找到节点之后,获取节点的数据域,然后返回
Collections类(重点)
Collections的介绍
是一个集合的工具类,该类中的很多静态方法用来操作集合
Collections的常用功能
- public static void shuffle(List<?> list) :打乱集合顺序。
- public static <T> void sort(List<T> list,Comparator<T> com); 带有比较器的排序方法
如果集合泛型是数值类型, 按照数值大小升序(比较器详细讲解在下边)
如果集合泛型是Chararcter类型,那按照字符的码值升序
如果集合泛型是String类型,那么按照首字母升序,如果首字母一样,按照次字母排序,以此类推
- public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。
注意:
sort、max、min三个方法都需要指定排序的规则。即：如果集合中存的是自定义对象，那么该对象必须要实现Comparable接口或者给这三个方法传递一个Comparator的实现类作为比较器.
使用Collections类的sort方法
使用带有比较器的sort方法:
//使用比较器降序排序
public class TestCollections02 {
public static void main(String[] args) {
//1.创建一个集合
ArrayList<Integer> arr = new ArrayList<Integer>();
//2.添加点元素
arr.add(2);
arr.add(8);
arr.add(3);
arr.add(9);
arr.add(4);
arr.add(1);
arr.add(6);
arr.add(7);
arr.add(5);
System.out.println(arr);
//3.使用带有比较器的sort方法
Collections.sort(arr, new Comparator<Integer>() {
/**
* 该方法就是比较方法
* @param o1 第一元素
* @param o2 第二元素
* @return 返回值代表谁大谁小,如果是正数代表o1大,如果适合负数代表o2大,如果是0代表一样大
*
* 口诀:
* 升序 前-后
*/
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
System.out.println(arr);
}
}
//使用比较器排序自定义类型
public class TestCollections03 {
public static void main(String[] args) {
//1.创建一个集合
ArrayList<Dog> arr = new ArrayList<Dog>();
//2.加狗
arr.add(new Dog(1,"jack",4));
arr.add(new Dog(4,"lilei",3));
arr.add(new Dog(2,"ady",2));
arr.add(new Dog(3,"hanmmeimei",5));
//3.对狗集合继续排序
Collections.sort(arr, new Comparator<Dog>() {
@Override
public int compare(Dog o1, Dog o2) {
//升序 前-后
//按照狗的年龄降序
// return o2.age-o1.age;
//按照狗的名字的长度升序
// return o1.name.length()-o2.name.length();
//按照狗的年龄和腿数的总和,升序
return (o1.age+o1.legs)-(o2.age+o2.legs);
}
});
//4.打印
for (Dog dog : arr) {
System.out.println(dog);
}
}
}
排序
自然排序和比较器排序
- 整数类型(int,short,byte,long) 可以用减法,
- 引用类型 使用 对象名.compareTo(对象名)方法
自然排序(只能实现一种排序规则)
根据数字的大小
Comparable接口
在定义类中实现Comparable接口,并且重写该接口内的比较规则的方法 然后在测试类中可以配合 Conllections.sort().使用,打印出来的集合就是按照了自定义的比较规则而打印
也可以配合TreeSet集合使用
自然排序缺点:
只能实现一种比较规则. 所以比较规则多的话使用比较器排序
图解代码
比较器排序
比较规则写在类的内部,每个比较器都可以实现一个自定义比较规则,想要用多种规则,就用多个比较器实现,一般使用匿名内部类填写规则.
Comparator接口(比较器)
Collections中有两个sort重载方法, 一个根据从小到大排序, 一个根据规则排序
public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。参数列表中, 一个为集合, 一个为接口实现类对象.接口参数需要传入接口的实现类对象或者使用匿名内部类实现.
此匿名内部类中的返回值口诀为: 升序前-后
public static void main(String[] args) {
// 创建四个学生对象 存储到集合中
ArrayList<Student> list = new ArrayList<Student>();
list.add(new Student("rose",18));
list.add(new Student("jack",16));
list.add(new Student("abc",20));
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
这里的返回值,升序 前-后
return o1.getAge()-o2.getAge();//以学生的年龄升序
或者使用 return o1.name.compareTo(o2.name) 字符串已经实现好了 compareTo方法
}
});
for (Student student : list) {
System.out.println(student);
}
}
可变参数
- 使用
在JDK1.5之后，如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，我们可以对其简化.
格式：
修饰符 返回值类型 方法名(参数类型... 形参名){ }
注意：
1.一个方法只能有一个可变参数
2.如果方法中有多个参数，可变参数要放到最后。
- 应用场景
Collections
在Collections中也提供了添加一些元素方法：
public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。
public class CollectionsDemo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
//原来写法
//list.add(12);
//list.add(14);
//list.add(15);
//list.add(1000);
//采用工具类 完成 往集合中添加元素
Collections.addAll(list, 5, 222, 1，2);
System.out.println(list);
}
Set接口[重点]
Set接口的特点
- 继承Collection接口
- 特点:
1.无序.(实现类LinkedHashSet除外)(Java中无序指,存入2,1,3. 打印出来可能是1,2,3等)
2.无索引
3.元素不可重复
注意: 除了Set接口的实现类LinkedHashSet是有序的
Set接口的常用方法以及常用子类
- Set接口中的方法(7个Collection继承的常见方法,1个迭代器)
- Set接口没有特有方法
- Set接口的实现类
1.HashSet
2.LinkedHashSet
3.TreeSet
HashSet的数据结构以及使用
- HashSet没有特有方法
- HashSet底层采用的是哈希表结构(数组结构+链表结构+红黑树结构)无序,无索引,元素唯一
- HashSet的使用
public class TestHashSet {
public static void main(String[] args) {
//1.创建一个HashSet对象
HashSet<String> set = new HashSet<String>();
//2.添加,没有带索引的方法,证明无索引
set.add("php");
set.add("java");
set.add("python");
set.add("c++");
set.add("c#");
//3.直接的打印,证明无序
System.out.println(set);//[c#, python, c++, java, php]
//4.再加一个一样元素,证明唯一
set.add("php");
set.add("php");
set.add("php");
set.add("php");
set.add("php");
set.add("php");
System.out.println(set);
}
}
哈希表结构的介绍
- Java中的每个对象的哈希值(对象的"数字指纹")
1.对象的哈希值,相当于对象的"指纹"(哈希值是十进制, 对象的地址值是十六进制 , 换算之后值一样)
2.获取对象的哈希值
调用对象.hashCode方法就可以获取 返回值为int
public class TestHashDemo01 {
public static void main(String[] args) {
//1.获取一个对象的哈希码值
Student s1 = new Student(10,"前妻");
int hashCode = s1.hashCode();
System.out.println(hashCode);//1163157884
}
}
3.Java中的地址值真实面目是哈希值的十六进制表示
4.Java中的地址值存在,但是看不见
Dog d = new Dog(); 变量d中存储的是Dog()对象的真正地址值. 打印d 是Object类中的toString方法此方法是打印出哈希值. 因此隐藏了对象的地址值.
5.不同的两个对象,可能会有哈希值相同的情况, 因为获取的哈希值方法返回值为int类型, 对象可以有无数个, 哈希值只有int范围个.(特别是String类会有可能出现地址值相同如 "abc"和"acD")
-
哈希表结构特点(无序,无索引,无重复)
1.哈希表结构会先比较两个对象的哈希值,再调用equals比较两个对象.只有哈希值相同,并且equals返回值为true.才判定这两个元素为重复的,后进来的元素不再进行添加操作(具体底层操作如下图)
2.哈希表结构 = 数组结构 + 链表结构 +红黑树结构
- 哈希值(上图解释)
因为哈希表结构底层使用了数组结构, 所以哈希值决定了元素放入数组的哪个位置
HashSet中使用了HashMap
如 键:a,hash:97 计算方法为: hash%数组长度=需要放置的数组下标 97%16 = 6 所以将元素a放在数组下标为6的位置. 如果哈希值一样, 计算出来的下标一样的话, 就用链表形式,当多于8个链表的时候,采用了红黑树结构
哈希表结构保存自定义类型[重要]
因为哈希表判断两个元素重复与否, 先判断的是哈希值,再使用equals方法判断.
所以为了保证元素的唯一性, 如果元素是自定义类型, 必须重写hashCode和equals方法 (alt+insert)快捷键
/**
* 使用哈希表保存自定义类型的练习
*/
public class TestHashSetDemo {
public static void main(String[] args) {
//1.创建一个哈希表结构的集合
HashSet<Dog> dogHashSet = new HashSet<Dog>();
//2.保存对象
dogHashSet.add(new Dog(10,"旺小财",3));
dogHashSet.add(new Dog(20,"旺中财",4));
dogHashSet.add(new Dog(30,"旺大财",5));
dogHashSet.add(new Dog(40,"旺老财",6));
//再添加一只狗
dogHashSet.add(new Dog(30,"旺大财",5));
//哈希表判断两个元素重复or不重复的依据是什么??
// 哈希表和equals
//为了保证元素的唯一性,我们要重写hashCode和equals,根据内容来计算哈希值,equals也改成比较内容
//3.打印
for (Dog dog : dogHashSet) {
System.out.println(dog);
}
}
}
public class Dog {
int age;
String name;
int legs;
public Dog() {
}
public Dog(int age, String name, int legs) {
this.age = age;
this.name = name;
this.legs = legs;
}
@Override
public String toString() {
return "Dog{" +
"age=" + age +
", name='" + name + '\'' +
", legs=" + legs +
'}';
}
//为了保证哈希表中元素的唯一性,我们需要重写hashCode和equals方法
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Dog dog = (Dog) o;
return age == dog.age &&
legs == dog.legs &&
Objects.equals(name, dog.name);
}
@Override
public int hashCode() {
return Objects.hash(age, name, legs);
}
}
HashSet源码分析
- 构造方法
HashSet<String> set = new HashSet<String>();
public HashSet() {
map = new HashMap<>();
}
HashSet底层实际是依赖一个HashMap
- HashSet的add方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
实际上是调用HashMap的put方法
- HashMap的put方法
HashMap保存键时,是根据键的哈希值确定保存位置.
LinkedHashSet的数据结构以及使用
- LinkedHashSet特点:有序,无索引,元素不重复
- LinkedHashSet无特有方法
- LinkedHashSet底层采用链表+哈希表结构
- LinkedHashSet的使用)
TreeSet的数据结构以及使用
- TreeSet的特点
1.无序的但是有自然顺序(存取顺序不一样, 但是无序中一种特殊存在,有自然顺序, 打印出的值是按自然数值从小到大打印出来, 如 输入 321, 打印出来为123)
2.无索引的
3.元素唯一
按照元素大小进行排序,要求元素实现Comparable接口(自然排序)或者加比较器 - TreeSet特有方法: 没有
- TreeSet底层采用红黑树结构
- TreeSet的使用
public static void main(String[] args) {
//无参构造,默认使用元素的自然顺序进行排序
TreeSet<Integer> set = new TreeSet<Integer>();
set.add(20);
set.add(18);
set.add(23);
set.add(22);
set.add(17);
set.add(24);
set.add(19);
System.out.println(set);
}
控制台的输出结果为:
[17, 18, 19, 20, 22, 23, 24]
- TreeSet也可以使用比较器自定义排序规则
因为TreeSet的构造方法有两个
public TreeSet()： 根据其元素的自然排序进行排序
public TreeSet(Comparator<E> comparator): 根据指定的比较器进行排序
