集合

D:\code\黑马\code\collection-app\src\com\lmh

集合体系结构

1. Collection：代表单列集合，每个元素只包含一个值

2. Map：代表双列集合，每个元素都包含两个值(键值对/entry对象)

一. Collection集合

Collection集合概述

• List系列集合：添加的元素是有序、可重复、有索引

  • ArrayList、LinkedList: 有序、可重复、有索引

• Set系列集合：添加的元素是无序、不重复(重复元素在添加时自动合并)、无索引

  • HashSet: 无序、不重复、无索引
  • LinkedHashSet: 有序、不重复、无索引
  • TreeSet: 按照大小默认升序排序、不重复、无索引

• Collection的方法可以被下面的所有分支使用

• List的方法可以被下面的分支ArrayList、LinkedList使用

• Set的方法可以被下面的分支HashSet、LinkedHashSet、TreeSet使用

• HashSet的方法可以被LinkedHashSet使用

PS：下文的标题顺序依据上文的Collection集合的顺序，从上至下

1. Collection

1.1 Collection常用方法（可以被所有单列集合使用）

Collection是单列集合的祖宗，它规定的方法会被所有单列集合所继承，即所有实现Collection接口的类都可以拥有Collection中的方法

方法	说明
public boolean add( E e )	将传入参数添加到Collection集合中
public boolean remove( Object o )	将传入参数从Collection集合中移除，只移除第一个匹配项
public boolean contains( Object o )	判断传入的参数是否在Collection集合中，在返回ture
public boolean isEmpty( )	判断Collection集合是否为空，为空返回true
public int size( )	返回Collection集合的长度
public Object[ ] toArray( )	将Collection集合转为Object[ ]类型数组
public T[ ] toArray( @NotNull T[ ] a )	将Collection集合根据入参转为T[ ]类型数组
public boolean addAll( @NotNull Collection c )	将当前的Collection集合中的元素拷贝到入参的c集合中
public void clear( )	将当前Collection集合中的元素清空

public class Test1 {public static void main(String[] args) {//创建Collection对象// 因为Collection是接口，不能实例化，所有需要用到它的实现类Collection<String> c = new ArrayList<>();//添加元素 boolean add(E e)c.add("lmh");c.add("sm");c.add("lmh");System.out.println(c);//[lmh, sm, lmh]System.out.println("=======================");//删除元素，如果有重复元素，只删除第一个 boolean remove(Object o)c.remove("lmh");System.out.println(c);//[sm, lmh]System.out.println("=======================");//判断集合中是否包含某个元素 boolean contains(Object o)System.out.print("当前集合：");System.out.println(c);//当前集合：[sm, lmh]System.out.println(c.contains("sm"));//trueSystem.out.println("=======================");//判断集合是否为空 boolean isEmpty()System.out.println(c.isEmpty());//falseSystem.out.println("=======================");//获取集合中元素的个数 int size()System.out.println(c.size());//2System.out.println("=======================");//把集合转换成数组 Object[] toArray()Object[] arrObj = c.toArray();System.out.println(Arrays.toString(arrObj));//[sm, lmh]System.out.println(arrObj.getClass());//class [Ljava.lang.Object;//如果想用String类型的数组接收的方法String[] arrStr = c.toArray(new String[c.size()]);System.out.println(Arrays.toString(arrStr));System.out.println(arrStr.getClass());//class [Ljava.lang.String;System.out.println("=======================");//复制集合 void addAll(Collection c)Collection<String> c2 = new ArrayList<>();c2.add("ttt");c2.addAll(c);System.out.println(c2);//[ttt, sm, lmh]System.out.println("=======================");//清理集合 void clear()c.clear();System.out.println(c.isEmpty());//trueSystem.out.println("=======================");}
}

1.2 Collection遍历方式（可以被所有单列集合使用）

所有Collection集合的遍历方式均相同，也就是说该Collection遍历方式适用于所有单列集合

1.2.1 迭代器Iterator

• 迭代器是遍历集合的专用方式，数组没有迭代器
• 迭代器对象：Iterator

方法	说明
public Iterator iterator( )	属于Collection对象的实例方法，用于获取Iterator对象，该Iterator对象默认指向当前集合的第一个元素
public boolean hasNext( )	属于Iterator对象的实例方法，用于判断当前位置是否有元素，有元素返回true
public E next( )	属于Iterator对象的实例方法，用于获取Collection中当前位置的元素并将迭代器对象指向集合中的下一个元素出

public class Test2 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("lmh");c.add("sm");c.add("hhh");//使用迭代器遍历集合Iterator<String> iterator = c.iterator();while (iterator.hasNext()){String temp = iterator.next();System.out.println(temp);}}
}

1.2.2 增强for

• 可以用于遍历集合或数组

public class Test2 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("lmh");c.add("sm");c.add("hhh");//使用增强for循环遍历集合//小技巧：可以直接写变量名.for，然后回车for (String s : c) {String temp = s;System.out.println(temp);}}
}

1.2.3 Lambda表达式

• 只能用于遍历集合

方法	说明
default void forEach( Consumer action )	Collection对象的实例方法，结合Lambda表达式遍历集合

public class Test2 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("lmh");c.add("sm");c.add("hhh");//使用foreach遍历集合c.forEach(new Consumer<String>() {@Overridepublic void accept(String s) {System.out.println(s);}});//使用lambda表达式遍历集合c.forEach(s -> System.out.println(s));//System.out.println(s)相当于System.out的对象调用println实例方法，所以可以简写为c.forEach(System.out::println);//最终语句}
}

案例：遍历集合中的自定义对象

需求：展示多部电影信息

//实体类
public class Movie {private String name;private double price;private String director;//导演public Movie() {}public Movie(String name, double price, String director) {this.name = name;this.price = price;this.director = director;}@Overridepublic String toString() {return "Movies{" +"name='" + name + '\'' +", price=" + price +", director='" + director+'}' + '\n';}public String getName() {return name;}public double getPrice() {return price;}public String getDirector() {return director;}
}

//输出信息
public class Test3 {public static void main(String[] args) {Collection<Movie> movies = new ArrayList<>();movies.add(new Movie("肖申克的救赎", 9.6, "弗兰克·德拉邦特"));movies.add(new Movie("霸王别姬", 9.5, "陈凯歌"));movies.add(new Movie("这个杀手不太冷", 9.4, "吕克·贝松"));movies.add(new Movie("阿甘正传", 9.4, "罗伯特·泽米吉斯"));System.out.println(movies);System.out.println("==================================");for (Movie movie : movies) {System.out.print(movie.getName() + " ");System.out.print(movie.getPrice() + " ");System.out.println(movie.getDirector());}}
}
/*
[Movies{name='肖申克的救赎', price=9.6, director='弗兰克·德拉邦特}
, Movies{name='霸王别姬', price=9.5, director='陈凯歌}
, Movies{name='这个杀手不太冷', price=9.4, director='吕克·贝松}
, Movies{name='阿甘正传', price=9.4, director='罗伯特·泽米吉斯}
]
==================================
肖申克的救赎 9.6 弗兰克·德拉邦特
霸王别姬 9.5 陈凯歌
这个杀手不太冷 9.4 吕克·贝松
阿甘正传 9.4 罗伯特·泽米吉斯
*/

• 栈内存的主方法中会有Collection类型的movies变量，存的是堆内存中movies开辟的空间的地址
• 三个Movie类型的对象会在堆内存开辟三个空间，地址被堆内存中的movies开辟的空间分别存储

2. List(继承自Collection)

• 可以直接使用上文提到的Collection的常用方法和遍历方式

2.1 特点

List系列集合：有序、可重复、有索引

• ArrayList: 有序、可重复、有索引
• LinkedList: 有序、可重复、有索引

ArrayList与LinkedList的不同点在于底层数据结构的实现与应用场景不同

2.2 List集合的特有方法

List集合除了继承Collection的方法外，还会有一些自己独有的方法

方法	说明
public void add(int index, E element )	将元素element添加到List集合中的index处，原来index处的元素依次后移
public E remove( int index )	删除List集合中的index处的元素，并将该元素返回
public E get(int index )	返回List集合中index位置处的元素
public E set( int index, E element )	将List集合中index位置处的元素修改为传入的element，并返回原来index位置处的元素

public class Test1 {public static void main(String[] args) {//创建list对象List<String> list = new ArrayList<>();list.add("a");list.add("b");list.add("c");list.add("d");System.out.println(list);//[a, b, c, d]//根据索引插入元素list.add(2,"lmh");//在索引2处插入元素,原来的元素向后移动System.out.println(list);//[a, b, lmh, c, d]//根据索引删除元素list.remove(2);//删除索引2处的元素System.out.println(list);//[a, b, c, d]//根据索引获取元素String s = list.get(2);//获取索引2处的元素System.out.println(s);//c//根据索引修改元素System.out.println(list.set(2, "lmh"));//修改索引2处的元素,返回值为cSystem.out.println(list);//[a, b, lmh, d]}
}

2.3 List集合的遍历方式

因为List集合是带有索引的，所以除了Collection集合的三种遍历方式外，List集合也可以根据索引通过for循环遍历元素

• for循环
• 增强for
• 迭代器
• Lambda表达式

3. ArrayList(实现List接口)

3.1 特点

有序、可重复、有索引

3.2 底层原理

• 基于数组实现

• 具体实现

  1. 利用无参构造器创建的集合，会在底层创建一个默认长度为0的数组
  2. 添加第一个元素时，底层会创建一个新的长度为10的数组，并将地址赋给ArrayList变量
  3. 当当前数组存满时，会基于当前长度扩容1.5倍( 10 * 1.5 = 15)
  4. 如果一次添加多个元素，即通过addAll( )等方法将一个长度为15的list1直接加到当前的数组，此时数组的1.5倍长度仅仅为15，并不足以将新的15个元素都放入当前数组中，因为当前的数组并不是空的。假设当前数组中有9个元素，则(9 + 15 > 15)，此时就不能只扩容1.5倍，而是以能存下所有元素为基础进行扩容，即长度应该扩容为24。

• 特点：根据索引查询速度快、增加和删除元素慢

  • 查询速度快：查询数据通过地址值和索引定位，查询任意位置数据耗时相同。

  • 删除效率低：删除后要把后面的元素全部向前移动

  • 添加效率极低：在指定位置插入元素时要先将当前位置的以及后面的元素全部后移后再添加元素；如果容量不足，还要先进行扩容

3.3 应用场景

• 适用于根据索引查询数据的情况
  • 根据随机索引取数据，使用ArrayList会十分高效
  • 数据量不大时也可以使用ArrayList
• 不适用于数据量大的同时要进行频繁的增加和删除操作的情况

总的来说适合查询操作，会十分高效，数据量较小时候的增删勉强可以使用；不适用于增删数据量大的增删操作

4. LinkedList(实现List接口)

4.1 特点

有序、可重复、有索引

4.2 底层原理

• 基于双链表实现
  

• 特点：查询慢，增删相对较快，但对首尾进行增删改查的速度极快

  • 对头部添加元素：将指向头结点的指针指向待插入元素，待插入元素指向原来的头结点
  • 删除头部元素：将指向头结点的指针指向当前头结点指向的元素
  • 对尾部添加元素：将原来的尾结点指向待插入元素，指向尾结点的指针指向待插入元素
  • 删除尾部元素：将尾指针指向当前尾结点指向的元素

对首尾操作的特有方法

方法	说明
public void addFirst( E e )	在该链表的头部插入指定的元素
public void addLast(Ee)	在该链表的尾部插入指定的元素
public E getFirst( )	返回此链表中的头部元素
public E getLast( )	返回此链表中的尾部元素
public E removeFirst( )	将此链表的头结点删除并返回头结点
public E removeLast( )	将此链表的尾结点删除并返回尾结点

public class Test4 {public static void main(String[] args) {LinkedList<String> list = new LinkedList<>();list.add("a");list.add("b");System.out.println(list);//[a, b]//在头部添加元素list.addFirst("c");System.out.println(list);//[c, a, b]//在尾部添加元素list.addLast("d");System.out.println(list);//[c, a, b, d]//获取头部元素String first = list.getFirst();System.out.println(first);//c//获取尾部元素String last = list.getLast();System.out.println(last);//d//删除头部元素并返回头部元素System.out.println(list.removeFirst());//c//删除尾部元素并返回尾部元素System.out.println(list.removeLast());//d}
}

4.3 应用场景

4.3.1 用于设计队列

先入先出

• 入队：每次入队相当于在链表的尾部插入元素
• 出队：每次出队相当于删除链表头部的元素并返回

public class Test2 {public static void main(String[] args) {//创建队列LinkedList<String> queue = new LinkedList<>();//入队，每次在链表尾部添加元素queue.addLast("a");queue.addLast("b");queue.addLast("c");System.out.println(queue);//[a, b, c]//出队，每次从链表头部获取元素System.out.println(queue.removeFirst());//aSystem.out.println(queue.removeFirst());//bSystem.out.println(queue);//[c]}
}

4.3.2 用于设计栈

先入后出

• 入栈(push)：每次入栈就相当于在链表的头部插入元素
• 出栈(pop)：每次出栈就相当于在删除链表头部的元素并返回

public class Test2 {public static void main(String[] args) {//创建栈LinkedList<String> stack = new LinkedList<>();//入栈，每次在链表头部添加元素stack.push("a");stack.push("b");stack.push("c");/*stack.push("a")等价于stack.addFirst("a")stack.push(E e)内部实现：public void push(E e) {addFirst(e);}*/"====================================================================================="//出栈，每次从链表头部获取元素System.out.println(stack.pop());//cSystem.out.println(stack.pop());//b/*stack.pop()等价于stack.removeFirst()stack.pop()内部实现：public E pop() {return removeFirst();}*/}
}

5. Set(继承自Collection)

5.1 特点

Set系列集合：无序、不重复、无索引

• HashSet：无序、不重复、无索引
• LinkedHashSet：有序、不重复、无索引
• TreeSet：排序、不重复、无索引

1. 无序：添加数据的顺序与获取数据的顺序不一致

2. 不重复：没有相同的数据

3. 无索引：无法通过索引查找数据

public class Test1 {public static void main(String[] args) {// HashSet//无序、不重复、无索引Set<Integer> set1 = new HashSet<>();set1.add(344);set1.add(99);set1.add(2);set1.add(2);set1.add(2);set1.add(1);set1.add(1);set1.add(3);System.out.println(set1);//[1, 2, 99, 3, 344]，与添加顺序无关，所以为无序并且不重复
//        set1.get();会报错，因为没有索引System.out.println("====================================");// LinkedHashSet//有序、不重复、无索引Set<Integer> set2 = new LinkedHashSet<>();set2.add(344);set2.add(99);set2.add(3);set2.add(2);set2.add(2);set2.add(2);set2.add(1);set2.add(3);System.out.println(set2);//[344, 99, 3, 2, 1]//与添加顺序相同，所以为有序并且不重复
//        set2.get();会报错，因为没有索引System.out.println("====================================");// TreeSet//排序、不重复、无索引Set<Integer> set3 = new TreeSet<>();set3.add(344);set3.add(99);set3.add(1);set3.add(2);set3.add(2);set3.add(2);set3.add(1);set3.add(3);System.out.println(set3);//[1, 2, 3, 99, 344]按照大小顺序排列，所以为排序并且不重复
//        set3.get();会报错，因为没有索引}
}

5.2 常用方法

Set集合继承了Collection集合的方法，除去Collection集合的方法外，几乎没有额外的常用方法

5.3 哈希值

5.3.1 哈希值概念

• 一个int类型的数值，java中每个对象都会有一个哈希值
• java中的所有对象都可以调用Object类提供的hashCode方法来获取自己的哈希值
  • public int hashCode( )：返回对象的哈希值

5.3.2 对象哈希值特点

• 同一个对象多次调用hashCode( )方法返回的哈希值是相同的
• 不同的对象的哈希值一般情况下是不相同的，但是由于int类型能表示的范围大约是43亿左右，所有还是会出现特殊情况导致不同对象的哈希值有可能相同

public class Test2 {public static void main(String[] args) {String s1 = "abc";String s2 = "cf";System.out.println(s1.hashCode());//96354System.out.println(s1.hashCode());//96354//两次调用hashCode()方法得到的结果是一样的System.out.println(s2.hashCode());//3105//s1与s2的hashCode()方法得到的结果不一样，所以一般情况下每个对象的哈希值都是不一样的//特殊情况：不同对象的哈希值可能是一样的String s3 = "abc";String s4 = "acD";System.out.println(s3.hashCode());//96354System.out.println(s4.hashCode());//96354}
}

6. HashSet(实现Set接口)

6.1 HashSet集合的底层原理

• 基于哈希表实现（也是基于HashMap实现，HashSet中的值也就是HashMap中的键）

• 无序、不重复、无索引

  • 因为基于哈希表，所以无序且无索引

• 由于基于哈希表，所以HashSet是一种增删改查数据性能都比较好的集合

• 哈希表

  • JDK8之前，哈希表 = 数组 + 链表
  • JDK8之后，哈希表 = 数组 + 链表 + 红黑树(自平衡二叉树)

• 红黑树

  • 自平衡的二叉树，左子树元素小于根节点，右子树元素大于根节点，不会包含重复的元素
  • 使用前序遍历来遍历红黑树，会得到一个递增的序列，这也是TreeSet的原理
  • 红黑树是一种增删改查数据性能都比较好的数据结果
  • 

6.1.1 JDK8之前的哈希表实现HashSet集合

哈希表 = 数组 + 链表

(1) 详细实现步骤

1. 创建一个默认长度为16的数组，默认加载因子为0.75，数组名为table
2. 使用待插入元素的哈希值对数组长度求余，结果为待插入的索引位置(也是查询的原理)
3. 如果待插入位置为null，即还没有元素，则直接将该元素插入
4. 如果不为null，则当前位置有元素，调用Object类的equals方法将待插入元素与现有的所有元素依次比较（默认的equals方法比较的是两个对象的地址）
   • 如果相等，则待插入元素不用再存储在数组中
   • 如果不相等，则将待插入元素使用链表形式存入数组中
     • 存入链表中方式：新元素占据原来元素在链表中的位置，老元素挂在新元素的下方

(2) 问题：查询效率不高

虽然使用数组+链表提高了增删改查的速度，但是当数组的16个位置全部被占满并且每个位置的链表过长时，会导致查询的速度明显下降

(3) 解决方案：扩容

• 扩容的前提条件
  • 如果当前数组中已经插入元素的位置 > (当前数组的长度*加载因子)时，就会扩容，不会等到原数组的所有位置都有元素后扩容。
• 扩容后的操作
  • 扩容的长度大概是当前数组长度的二倍，并将原数组的所有数据按照上文的步骤重新依次插入到新的数组中。
• 扩容的目的
  • 通过将元素插入到扩容后的新数组可以达到使链表的链子变短的目的，因为原来的数组长度计算出的索引位置与新数组的长度计算出的索引位置大概率不同，也就达到了优化查询速度的目的。
• 扩容后的问题
  • 扩容后原数组中的元素虽然与新数组中元素位置有大概率不同，但是也可能出现几个位置链表过长的问题，无法有效的优化查询速度，该问题会在下文JDK8之后的哈希表实现HashSet中得到解决

6.1.2 JDK8之后的哈希表实现HashSet

哈希表 = 数组 + 链表 + 红黑树

(1) 详细实现步骤

（与JDK8之前的哈希表实现除了向链表中插入元素方式不同外，其余步骤一致）

1. 创建一个默认长度为16的数组，默认加载因子为0.75，数组名为table
2. 使用待插入元素的哈希值对数组长度求余，结果为待插入的索引位置(也是查询的原理)
3. 如果待插入位置为null，即还没有元素，则直接将该元素插入
4. 如果不为null，则当前位置有元素，调用Object类的equals方法将待插入元素与现有的所有元素依次比较（默认的equals方法比较的是两个对象的地址）
   1. 如果相等，则待插入元素不用再存储在数组中
   2. 如果不相等，则将待插入元素使用链表形式存入数组中
      1. 存入链表中方式：新元素直接挂在老元素的下方

(2) 引入红黑树的目的

解决上文中JDK8之前的HashSet实现中扩容后仍然无法有效解决查询效率不高的问题

虽然通过扩容可以一定程度上解决链表过长导致的查询性能降低的问题，但是也不能保证将原数组中的元素放入新数组后一定可以保证每个元素的插入位置都发生改变。如果出现某几个链子无论如果扩容都无法有效的缩短其长度从而达到优化查询的目的，就只能使用红黑树代替原来的链表，因为红黑树相比于链表，是一种增删改查性能都比较优秀的数据结构。

(3) 将链表转为红黑树的条件

1. 数组的长度 >= 64
2. 某一个位置的链表长度 > 8，则将该位置的链表转为红黑树从而优化查询效率

6.2 HashSet集合的去重机制

HashSet集合默认无法对两个内容一样的不同对象去重

• 因为HashSet去重的原理是基于哈希值和Objects的默认的equals方法

  • 哈希值用于确定在数组中的存储位置，两个对象的哈希值不同，最终不一定会放在数组的同一个位置，也就无法满足去重的前提条件

  • 即使放入了同一个位置，去重的原理是使用Object类的equals方法，没有重写前的equals方法会比较两个对象的地址值，地址不同即使内容相同也无法判定为相同，即会直接放入链表中

//初始的Student类
public class Student {String name;int age;double score;public Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{name='" + name + '\'' +", age=" + age +", score=" + score+"}";}
}

public class Test3 {public static void main(String[] args) {Set<Student> students = new HashSet<>();students.add(new Student("lmh", 18, 100));students.add(new Student("lmh1", 18, 90));students.add(new Student("lmh", 18, 100));System.out.println(students);//[{name='lmh', age=18, score=100.0}, //{name='lmh1', age=18, score=90.0}, //{name='lmh', age=18, score=100.0}]//两条相同的数据由于是不同的对象，所以并没有去重//如果想要去重，需要在Student类中重写hashCode()和equals()方法}
}

使HashSet集合认为内容相同的两个对象是重复的方法

重写对象的hashcode和equals方法

//重写hashCode()和equals()方法的Student类
public class Student {String name;int age;double score;//重写equals()方法，使得HashSet中的元素不重复//只有当两个对象的name、age、score都相等时，才认为这两个对象相等，不看地址@Overridepublic 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 && Double.compare(score, student.score) == 0 && Objects.equals(name, student.name);}//重写hashCode()方法，使得HashSet中的元素不重复//使用所有属性计算出的作为返回值//保证属性相同的对象返回值一样，不看地址，也就保证了插入在数组的同一个位置@Overridepublic int hashCode() {return Objects.hash(name, age, score);}public Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{name='" + name + '\'' +", age=" + age +", score=" + score+"}";}
}

public class Test3 {public static void main(String[] args) {Set<Student> students = new HashSet<>();students.add(new Student("lmh", 18, 100));students.add(new Student("lmh1", 18, 90));students.add(new Student("lmh", 18, 100));System.out.println(students);//[{name='lmh1', age=18, score=90.0}, {name='lmh', age=18, score=100.0}]//重写了equals()方法和hashCode()方法后，HashSet中的元素不重复}
}

7. LinkedHashSet(实现Set接口)

• 基于哈希表 = 数组 + 链表 + 红黑树实现
• （也是基于LinkedHashMap实现，LinkedHashSet中的值也就是LinkedHashMap中的键）
  • 与HashSet的不同之处就在于 LinkedHashSet是有序的，输入与输出顺序相同
  • 原因在于新增了双链表的机制来记录前后位置，也就是通过占用内存来达到有序
• 特点：有序、不重复、无索引

7.1 底层实现原理

底层实现原理与HashSet基本相同，只是在存入元素时新增了双链表记录位置来达到有序的目的。

• 经过哈希值确定插入位置后，同HashSet相同，如果当前位置有元素，就判断是否相同，不相同以链表形式存储。但是在插入时使用了双链表来记录位置。

7.1.1 双链表机制

1. 如果是第一个元素插入，则会有头指针和尾指针指向当前待插入元素，并且当前元素的left和right都为null。

2. 下一个元素插入时，头指针仍然指向第一个元素，但是尾指针指向的元素的right会存储当前待插入元素的地址，当前待插入元素的left也会存储尾指针指向元素的地址值，当前待插入元素的right置为null，最后插入元素，并且尾指针指向当前插入的元素。

3. 依次重复2过程

4. 取出元素时会从头指针指向的元素开始取，直到取到尾指针指向的元素。以占用内存为代价达到了有序的目的

8. TreeSet(实现Set接口)

8.1 特点

不重复、无索引、可排序

• 可排序是指对于输入的元素默认按照升序排序

public class Test4 {public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(344);set.add(99);set.add(1);set.add(2);System.out.println(set);//[1, 2, 99, 344]已经实现了排序}
}

8.2 底层实现原理

基于红黑树（也是基于 TreeMap实现， TreeSet中的值也就是 TreeMap中的键）

• 插入元素
  • 第一次插入的元素作为根节点
  • 之后每次插入元素根据左小右大的原则
    • 左子树都比根节点小，右子树都比根节点大，重复元素不插入
• 删除元素
  • 删除元素时也会从根结点开始查找并删除元素
    • 数值比根节点小则往左子树找，比根节点大则找右子树，直至找到元素并删除
    • 删除后遭到破坏的二叉树会重新调整树为平衡二叉树
• 查找元素
  • 从根结点开始查找
    • 数值比根节点小则往左子树找，比根节点大则找右子树，直至找到元素
• 输出所有元素
  • 此时集合中所有元素都已经被构建为红黑树，将红黑树按照前序遍历即为升序的数组

8.3 排序的注意事项

• 对于Integer、Double的数据类型，默认按照数值本身的大小进行升序排序。
• 对于字符串类型：默认按照首字符的SACll码值升序排序，首位相同比较次位，以此类推。
• 对于自定义类型如Studenti对象，TreeSet默认是无法直接排序
  • 因为自定义的实体类中存在多个属性，TreeSet不知道根据哪个属性排序

public class Student {String name;int age;double score;public Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{name='" + name + '\'' +", age=" + age +", score=" + score+"}";}
}

public class Test5 {public static void main(String[] args) {Set<Student> set = new TreeSet<>();//对于自定义类型对象无法直接排序Student s1 = new Student("lmh", 18, 100);Student s2 = new Student("lmh1", 18, 90);Student s3 = new Student("lmh2", 28, 100);set.add(s1);set.add(s2);set.add(s3);System.out.println(set);}
}

8.3.1 使TreeSet可以排序自定义类型的对象的方法

(1)自定义排序规则(共两种方式)

方式一：

• 让自定义的类（如学生类）实现Comparable接口，重写里面的compareTo方法来指定比较规则

//方式一：重写Comparable接口中的compareTo方法
public class Student implements Comparable<Student> {String name;int age;double score;//重写compareTo()方法，使得TreeSet中的元素可以根据score从小到大排序，重复元素不插入@Overridepublic int compareTo(Student o) {return Double.compare(this.score, o.score);}public Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{name='" + name + '\'' +", age=" + age +", score=" + score+"}";}
}

public class Test5 {public static void main(String[] args) {Set<Student> set = new TreeSet<>();Student s1 = new Student("lmh", 18, 100);Student s2 = new Student("lmh1", 18, 90);Student s3 = new Student("lmh2", 28, 100);set.add(s1);set.add(s2);set.add(s3);System.out.println(set);}
}
//因为是根据score排序，所以只要score相同就不插入，不考虑对象中的其他属性
/*
[{name='lmh1', age=18, score=90.0}, {name='lmh', age=18, score=100.0}]
*/

方式二：

• 通过调用TreeSet集合的有参构造器，以Comparator对象作为入参
  • public TreeSet( Comparator comparator )
  • TreeSet集合的有参数构造器的入参Comparator对象用于自定义排序规则，同ArrayLiist使用sort方法排序自定义数据类型的对象时传入的参数相同，都是一个匿名内部类，可以使用Lambda表达式简化

public class Student {String name;int age;double score;public Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{name='" + name + '\'' +", age=" + age +", score=" + score+"}";}
}

public class Test5 {public static void main(String[] args) {//方式二：使用匿名内部类的方式，创建了一个Comparator接口的实现类对象Set<Student> set = new TreeSet<>((o1, o2)-> o1.age - o2.age);Student s1 = new Student("lmh", 18, 100);Student s2 = new Student("lmh1", 18, 90);Student s3 = new Student("lmh2", 28, 100);set.add(s1);set.add(s2);set.add(s3);System.out.println(set);}
}
/*
[{name='lmh', age=18, score=100.0}, {name='lmh2', age=28, score=100.0}]
*/

比较规则同sort方法：

• 如果认为第一个元素 > 第二个元素返回正整数
• 如果认为第一个元素 < 第二个元素返回负整数
• 如果认为第一个元素 = 第二个元素返回0

(2)同时使用两种方式定义排序规则的优先原则

如果既在自定义的类实现Comparable接口，也调用了TreeSet集合的有参构造器，即同时使用了两种方式来自定义排序规则，那么以TreeSet集合的有参构造器定义的排序规则为准(以方式二的排序规则为准)。自带的比较器的优先级高于自定义的类中定义的函数。

//方式一：重写Comparable接口中的compareTo方法定义根据score排序
public class Student implements Comparable<Student> {String name;int age;double score;//重写compareTo()方法，使得TreeSet中的元素可以根据score从小到大排序，重复元素不插入@Overridepublic int compareTo(Student o) {return Double.compare(this.score, o.score);}public Student(String name, int age, double score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{name='" + name + '\'' +", age=" + age +", score=" + score+"}";}
}

public class Test5 {public static void main(String[] args) {//方式二：使用匿名内部类的方式，创建了一个Comparator接口的实现类对象根据age排序Set<Student> set = new TreeSet<>((o1, o2)-> o1.age - o2.age);Student s1 = new Student("lmh", 18, 100);Student s2 = new Student("lmh1", 18, 90);Student s3 = new Student("lmh2", 28, 100);set.add(s1);set.add(s2);set.add(s3);System.out.println(set);}
}
//两种方式同时实现，以TreeSet的有参构造器为准，根据age比较
/*
[{name='lmh', age=18, score=100.0}, {name='lmh2', age=28, score=100.0}]
*/

使用场景总结

1. 如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？
   • 用ArrayList:集合（有序、可重复、有索引)，底层基于数组的。（常用)
2. 如果希望记住元素的添加顺序，且增删首尾数据的情况较多？
   • 用LinkedList集合（有序、可重复、有索引)，底层基于双链表实现的。
3. 如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快？
   • 用HashSet:集合（无序，不重复，无索引），底层基于哈希表实现的。（常用）
4. 如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快？
   • 用LinkedHashSet:集合（有序，不重复，无索引)，底层基于哈希表和双链表。
5. 如果要对元素进行排序，也没有重复元素需要存储，且希望增删改查都快？
   • 用TreeSet集合，基于红黑树实现。

注意事项：集合的并发修改异常

1. 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。

2. 由于增强fo循环遍历集合就是迭代器遍历集合的简化写法，因此，使用增强fo循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误

Iterator<String> iterator = list1.iterator();
while (iterator.hasNext()){String next = iterator.next();if (next.startsWith("刘")){list1.remove(next);//会出现并发修改异常}
}

避免出现并发修改异常的方法

1. 使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可。
2. 如果能用fo循环遍历时**(有索引的集合)**：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做ⅰ-操作。
3. 增强for和Lambda表达式的并发修改问题无法解决

public class Test6 {public static void main(String[] args) {List<String> list1 = new ArrayList<>();list1.add("刘明");list1.add("刘明1");list1.add("刘明2");list1.add("李明");list1.add("李明1");list1.add("刘明3");System.out.println(list1);//[刘明, 刘明1, 刘明2, 李明, 李明1, 刘明3]List<String> list2 = new ArrayList<>(list1);System.out.println(list2);//[刘明, 刘明1, 刘明2, 李明, 李明1, 刘明3]//1. 使用for循环解决遍历并删除集合中姓刘的元素时的并发修改异常for (int i = 0; i < list1.size(); i++) {if (list1.get(i).startsWith("刘")) {list1.remove(i);i--;//删除元素后，后面的元素会向前移动，所以要i--，否则会漏掉一个元素,解决修改异常问题}}System.out.println(list1);//[李明, 李明1]//2. 使用迭代器解决遍历并删除集合中姓刘的元素时的并发修改异常Iterator<String> iterator = list2.iterator();while (iterator.hasNext()){String next = iterator.next();if (next.startsWith("刘")){iterator.remove();//使用迭代器自带的remove方法删除元素，解决修改异常问题}}System.out.println(list2);//[李明, 李明1]}
}

补充知识

1. 可变参数

概念

一种特殊的形参，定义在方法、构造器的形参列表里，格式为：数据类型.…参数名称

特点

可以不传数据给它；可以传一个或者同时传多个数据给它；也可以传一个数组给它

    public static void main(String[] args) {//可以不传数据给可变参数test();//可以传一个数据给可变参数test(1);//可以同时传多个数据给可变参数test(1, 2, 3);//可以传一个数组给可变参数int[] a = {1, 2, 3};test(a);}public static void test(int... a) {}

好处

常常用来灵活的接收数据

注意事项

1. 可变参数在方法内部就是一个数组
2. 一个形参列表中可变参数只能有一个
3. 可变参数必须放在形参列表的最后面

public class Test1 {public static void main(String[] args) {test("hello",1,2,3,4,5,6,7,8,9,10);}public static void test(String s,int b, int... a) {System.out.println(s);System.out.println(b);// 可变参数在方法中本质上是一个数组System.out.println(a.length);for (int ele : a) {System.out.print(ele);}}/*会报错，因为一个形参列表中可变参数只能有一个public static void test(int... a,String... b) {}*//*会报错，因为可变参数必须放在形参列表的最后面public static void test(int... a,int b) {}*/
}
/*
result：hello192345678910
*/

2. Collections工具类

用于操作集合的工具类

Collections常用静态方法

方法	说明
public static boolean addAll( java.util.Collection c, T… elements )	给集合c批量添加元素
public static void reverse( java.util.List list )	打乱list集合中元素的顺序
public static void shuffle( java.util.List list )	反转list集合
public static > void sort( java.util.List list )	对list集合中的元素进行升序排序
public static void sort(@NotNull java.util.List list, java.util.Comparator c )	对list集合中元素根据比较器自定义排序规则进行排序

public class Test2 {public static void main(String[] args) {List<Integer> list1 = new ArrayList<>();list1.add(1);list1.add(10);list1.add(2);list1.add(3);System.out.println(list1);//[1, 10, 2, 3]//Collections工具类常用方法//1.添加元素Collections.addAll(list1, 4, 5, 6, 7, 8, 9);System.out.println(list1);//[1, 10, 2, 3, 4, 5, 6, 7, 8, 9]//2.反转Collections.reverse(list1);System.out.println(list1);//[9, 8, 7, 6, 5, 4, 3, 2, 10, 1]//3.随机排序Collections.shuffle(list1);System.out.println(list1);//[5, 10, 9, 7, 8, 2, 6, 4, 1, 3]//4.排序Collections.sort(list1);System.out.println(list1);//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]}
}

自定义排序规则

1. 自定义类实现Comparable接口

public class Student implements Comparable<Student> {String name;int age;double score;//实现Comparable接口@Overridepublic int compareTo(Student o) {return Double.compare(this.score, o.score);}public Student(String name, int age, int score) {this.name = name;this.age = age;this.score = score;}@Overridepublic String toString() {return "{" +"name='" + name + '\'' +", age=" + age +", score=" + score +'}';}
}

public class Test2 {public static void main(String[] args) {List<Student> list2 = new ArrayList<>();list2.add(new Student("lmh", 18, 100));list2.add(new Student("lmh1", 15, 90));list2.add(new Student("lmh2", 50, 80));list2.add(new Student("lmh3", 19, 80));System.out.println(list2);//[{name='lmh', age=18, score=100.0}, {name='lmh1', age=15, score=90.0},// {name='lmh2', age=50, score=80.0}, {name='lmh3', age=19, score=80.0}]//1.自定义对象类实现Comparable接口Collections.sort(list2);System.out.println(list2);//[{name='lmh1', age=15, score=90.0}, {name='lmh3', age=19, score=80.0},// {name='lmh', age=18, score=100.0}, {name='lmh2', age=50, score=80.0}]}
}

2. Collections.sort方法实现比较器接口的匿名内部类

public class Test2 {public static void main(String[] args) {List<Student> list2 = new ArrayList<>();list2.add(new Student("lmh", 18, 100));list2.add(new Student("lmh1", 15, 90));list2.add(new Student("lmh2", 50, 80));list2.add(new Student("lmh3", 19, 80));System.out.println(list2);//[{name='lmh', age=18, score=100.0}, {name='lmh1', age=15, score=90.0},// {name='lmh2', age=50, score=80.0}, {name='lmh3', age=19, score=80.0}]//2.使用Collections.sort(list,comparator)方法Collections.sort(list2,((o1, o2) -> Double.compare(o1.score,o2.score)));System.out.println(list2);//[{name='lmh2', age=19, score=80.0}, {name='lmh3', age=50, score=80.0},// {name='lmh1', age=15, score=90.0}, {name='lmh', age=18, score=100.0}]}
}

3. 综合案例：斗地主

业务需求分析

• 业务：总共有54张牌

• 点数：“3”, “4”, “5”, “6”, “7”, “8”, “9”, “10”, “J”, “Q”, “K”, “A”, “2”

• 花色：“♠”, “♥”, “♣”, “♦”

• 大小王：“🃏”，“🤴”

• 点数分别要组合4种花色，大小王各一张。

• 斗地主：发出51张牌，剩下3张作为底牌。

实现

1. 启动房间，初始化54张牌
2. 洗牌
3. 发牌
4. 对牌进行排序
5. 看牌

//牌类
public class Card{private String number;//点数private String color;//花色private int size;//点数大小public Card() {}public Card(String number, String color, int size) {this.number = number;this.color = color;this.size = size;}public String getNumber() {return number;}public void setNumber(String number) {this.number = number;}public String getColor() {return color;}public void setColor(String color) {this.color = color;}public int getSize() {return size;}public void setSize(int size) {this.size = size;}@Overridepublic String toString() {return  color + number + " ";}
}

//斗地主房间类
public class Room {private final List<Card> cards = new ArrayList<>();//牌组private final List<Card> player1 = new ArrayList<>();//玩家1private final List<Card> player2 = new ArrayList<>();//玩家2private final List<Card> player3 = new ArrayList<>();//玩家3private List<Card> bottom = new ArrayList<>();//底牌public Room() {//初始化牌组String[] numbers = {"3","4","5","6","7","8","9","10","J","Q","K","A","2"};String[] colors = {"♠","♥","♣","♦"};for (int i = 0; i < numbers.length; i++) {for (String color : colors) {cards.add(new Card(numbers[i], color, i));}}cards.add(new Card("", "🃏", 13));cards.add(new Card("", "🤴", 14));System.out.println("牌组初始化完成！");System.out.println(cards);}// 洗牌,分牌，排序，看牌public void start(){shuffle();divide();sort();}//洗牌public void shuffle(){Collections.shuffle(cards);System.out.println("洗牌完成！");System.out.println(cards);}//分牌public void divide(){for(int i = 0; i < cards.size() - 3; i++) {if (i % 3 == 0)player1.add(cards.get(i));else if (i % 3 == 1)player2.add(cards.get(i));elseplayer3.add(cards.get(i));}System.out.println("分牌完成！");System.out.println("玩家1：" + player1);System.out.println("玩家2：" + player2);System.out.println("玩家3：" + player3);bottom = cards.subList(cards.size() - 3, cards.size());//根据索引划分集合，包含头不包含尾System.out.println("底牌：" + bottom);}//排序并看牌public void sort(){Collections.sort(player1,(o1, o2) -> Integer.compare(o1.getSize(), o2.getSize()));//根据牌的大小排序Collections.sort(player2,(o1, o2) -> Integer.compare(o1.getSize(), o2.getSize()));Collections.sort(player3,(o1, o2) -> Integer.compare(o1.getSize(), o2.getSize()));System.out.println("排序完成！");System.out.println("玩家1：" + player1);System.out.println("玩家2：" + player2);System.out.println("玩家3：" + player3);}
}

public class Game {/*业务需求分析：业务：总共有54张牌。点数："3","4","5","6","7","8","9","10","J","Q","K","A","2"花色："♠","♥","♣","♦"大小王："🃏"，"🤴"点数分别要组合4种花色，大小王各一张。斗地主：发出51张牌，剩下3张作为底牌。*/public static void main(String[] args) {Room room = new Room();room.start();}
}

二. Map集合

Map集合概述

概念

• Map集合称为双列集合，格式：{key1 = value1, key2 = value2, key3 = value3, …},一次需要存一对数据做为一个元素
• Map集合的每个元素“key = value”称为一个键值对/键值对对象/一个Entry对象，Map集合也被叫做“键值对集合”
• Mp集合的所有键是不允许重复的，但值可以重复，键和值是一一对应的，每一个键只能找到自己对应的值

使用场景

需要存储一一对应的数据时，就可以考虑使用Mp集合来做

• 例：购物车的商品作为键，数量作为值

Map集合体系

Map集合体系特点

• HashMap：无序、不重复、无索引 (用的最多)
• LinkedHashMap：由键决定的特点：有序、不重复、无索引
• TreeMap：按照大小默认升序排序、不重复、无索引

所有的特点都是基于键的

• 有序、无序或升序都是指键的有序、无序或升序，值只是键的附属品，随着键移动
• 不重复也是指键的不重复，值可以重复
• 所谓的不重复是指如果键相同，后插入的会覆盖原来的元素

public class Test1 {public static void main(String[] args) {//HashMap：无序、不重复、无索引Map map1 = new HashMap<>();map1.put("lmh",18);map1.put("lmh",19);map1.put("sm",20);map1.put("lm",20);System.out.println(map1);//{lm=20, lmh=19, sm=20}//无序，键不重复，值可以重复，无索引//如果键相同，后插入的会覆盖原来的元素//LinkedHashMap：由键决定的特点：有序、不重复、无索引Map map2 = new LinkedHashMap<>();map2.put("lmh",18);map2.put("lmh",19);map2.put("sm",20);map2.put("lm",20);System.out.println(map2);//{lmh=19, sm=20, lm=20}//有序，放入与取出顺序相同，// 键不重复，值可以重复，无索引//如果键相同，后插入的会覆盖原来的元素//TreeMap：按照大小默认升序排序、不重复、无索引Map map3 = new TreeMap<>();map3.put("a",22);map3.put("b",21);map3.put("c",20);map3.put("c",21);System.out.println(map3);//{a=18, b=19, c=21}//有序，按照键的大小排序,String类型按照ASCII码排序// 键不重复，值可以重复，无索引//如果键相同，后插入的会覆盖原来的元素}
}

1. Map

1.1常用方法（所有的双列集合都可以使用）

方法	说明
public V put(K key V value)	添加元素,返回值为被替换的value
public int size()	获取集合大小
public V get(Object key)	根据key获取value
public V remove(Object key)	根据key删除元素,返回值为被删除的value
public boolean containsKey(Object key)	判断是否包含某个key
public boolean containsValue(Object value)	判断是否包含某个value
public Set keySet()	获取所有的key
public Collection values()	获取map中所有的value
public void clear()	清空集合
public boolean isEmpty()	判断集合是否为空
public void putAll(Map m)	将其他map集合中的元素添加到当前map集合中
public Set> entrySet()	获取所有的entry对象，每个entry对象包含key和value

public class Test {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();// 添加元素//public V put(K key V value)//返回值为被替换的value,如果没有被替换的value,则返回nullSystem.out.println(map.put("Java", 1));//nullSystem.out.println(map.put("Java", 2));//1map.put("Linux", 2);map.put("MySQL", 3);System.out.println(map);//获取集合大小//public int size()int size = map.size();//3System.out.println(size);//根据key获取value//public V get(Object key)int value = map.get("Java");System.out.println(value);//2//根据key删除元素//public V remove(Object key)//返回值为被删除的value,如果没有被删除的value,则返回nullmap.remove("MySQL");System.out.println(map);//{Java=2, Linux=2}//判断是否包含某个key//public boolean containsKey(Object key)boolean flag = map.containsKey("Java");System.out.println(flag);//true//判断是否包含某个value//public boolean containsValue(Object value)boolean flag2 = map.containsValue(2);System.out.println(flag2);//true//获取所有的key//public Set keySet()//因为键不重复，所以返回值为Set集合Set<String> keys = map.keySet();System.out.println(keys);//[Java, Linux]//获取map中所有的value//public Collection values()//因为值可以重复，所以返回值为Collection集合Collection<Integer> values = map.values();System.out.println(values);//[2, 2]//清空集合//public void clear()map.clear();//判断集合是否为空//public boolean isEmpty()System.out.println(map.isEmpty());//true//将其他map集合中的元素添加到当前map集合中//public void putAll(Map m)Map<String,Integer> map2 = new HashMap<>();map2.put("Java", 1);map2.put("Linux", 2);map2.put("MySQL", 3);Map<String,Integer> map3 = new HashMap<>();map3.put("s", 1);map3.put("b", 2);map3.put("c", 3);map2.putAll(map3);System.out.println(map2);//{Java=1, b=2, s=1, c=3, Linux=2, MySQL=3}//整体无序//获取所有的entry对象，每个entry对象包含key和value//public Set> entrySet()Set<Map.Entry<String, Integer>> entries = map2.entrySet();System.out.println(entries);//[Java=1, b=2, s=1, c=3, Linux=2, MySQL=3]for (Map.Entry<String, Integer> entry : entries) {System.out.println(entry);}//Java=1//b=2//s=1//c=3//Linux=2//MySQL=3}
}

1.2 遍历方式（所有的双列集合都可以使用）

1. 通过键寻找值：先获取Map集合全部的键，再通过遍历键来找值
2. 键值对：把“键值对“看成一个整体即entry对象进行遍历
3. Lambda表达式

1.2.1 键找值

public class Test2 {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("Java", 1);map.put("Linux", 2);map.put("MySQL", 3);System.out.println(map);//{Java=1, Linux=2, MySQL=3}//通过键寻找值遍历mapSet<String> keys = map.keySet();for (String key : keys) {int value = map.get(key);System.out.println(key + "=====>" + value);//Java=====>1//Linux=====>2//MySQL=====>3}}
}

1.2.2 键值对

1. 通过Map提供的entrySet()方法获取所有的entry对象
2. 通过entry对象提供的 K getKey( ) 和 V getValue( )方法获取键和值

public class Test2 {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("Java", 1);map.put("Linux", 2);map.put("MySQL", 3);System.out.println(map);//{Java=1, Linux=2, MySQL=3}//通过键值对对象遍历mapSet<Map.Entry<String, Integer>> entries = map.entrySet();for (Map.Entry<String, Integer> entry : entries) {String key = entry.getKey();int value = entry.getValue();System.out.println(key + "=====>" + value);//Java=====>1//Linux=====>2//MySQL=====>3}}
}

1.2.3 Lambda表达式

通过Map集合的default void forEach(BiConsumer action)方法遍历map集合

public class Test2 {public static void main(String[] args) {Map<String,Integer> map = new HashMap<>();map.put("Java", 1);map.put("Linux", 2);map.put("MySQL", 3);System.out.println(map);//{Java=1, Linux=2, MySQL=3}//通过匿名内部类遍历mapmap.forEach(new BiConsumer<String, Integer>() {@Overridepublic void accept(String s, Integer integer) {System.out.println(s + "=====>" + integer);//Java=====>1//Linux=====>2//MySQL=====>3}});//通过Lambda表达式简化遍历mapmap.forEach((s,i)-> System.out.println(s + "=====>" + i));//Java=====>1//Linux=====>2//MySQL=====>3}
}

//forEach方法的底层源代码default void forEach(BiConsumer<? super K, ? super V> action) {Objects.requireNonNull(action);for (Map.Entry<K, V> entry : entrySet()) {K k;V v;try {k = entry.getKey();v = entry.getValue();} catch(IllegalStateException ise) {// this usually means the entry is no longer in the map.throw new ConcurrentModificationException(ise);}action.accept(k, v);}}

1.3 案例：统计投票人数

需求

某个班级80名学生，现在需要组织秋游活动，班长提供了四个景点依次是(A、B、C、D),每个学
生只能选择一个景点，请统计出最终哪个景点想去的人数最多。

分析

1. 将80个学生选择景点的投票结果拿到程序中去 [A,A,B,A,B,C,D …]
2. 准备一个Map集合用于存储统计的结果，Map,键是景点，值代表投票数量。
3. 遍历80个学生选择的景点，每遍历一个景点，就看Mp集合中是否存在该景点
   1. 如果不在存在则存入“景点=1"
   2. 如果存在则通过key找到对应的value并+1

public class Test3 {public static void main(String[] args) {//准备80名学生的选择List<String> choices = new ArrayList<>();String[] select = {"A", "B", "C", "D"};Random random = new Random();for (int i = 0; i < 80; i++) {int i1 = random.nextInt(4);//0,1,2,3中的一个choices.add(select[i1]);}//创建一个Map集合，key是景点，value是学生选择Map<String,Integer> result = new HashMap<>();for (String choice : choices) {//如果存在，就修改valueif (result.containsKey(choice)){int value = result.get(choice);result.put(choice, value + 1);}else {//如果不存在，就添加进去result.put(choice, 1);}}System.out.println(result);}
}

2. HashMap

都是基于键，因为键不能重复

2.1 底层实现原理

• HashMap跟HashSet的底层原理是一模一样的，都是基于哈希表实现的。
  • JDK8之前的哈希表 = 数组 + 链表
  • JDK8之后的哈希表 = 数组 + 链表 + 红黑树
• HashMap的键可以看作是HashSet的整个元素，HashMap的实现都是基于键，与值无关。无论是计算哈希值还是判断是否重复都是基于键，与值毫无关系，值在实现哈希表过程中毫无作用。
• 实际上：HashSet集合的底层就是基于HashMap实现的，只是HashSet集合中的元素只要键数据，不要值数据而已。

2.2 特点

• HashMap:集合是一种增删改查数据，性能都较好的集合

• 无序，不能重复，没有索引支持的（由键决定特点）

• HashMap的键依赖hashCode方法和equals方法保证键的唯一

• 如果键存储的是自定义类型的对象，无论值存储的是何种数据类型，都可以通过重写键存储的对象对应的类的hashCode和equals方法，使得HashMap集合认为内容一致的对象就是重复的，而不是默认比较两个键的自定义对象的地址

  public class Student implements Comparable<Student> {private String name;private int age;private double score;//重写hashCode()方法和equals()方法保证key的内容相同时就判定为重复，而不是比较地址@Overridepublic 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 && score == student.score && Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(name, age, score);}public Student(String name, int age, int score) {this.name = name;this.age = age;this.score = score;}public String toString() {return "[" + name + ", " + age + ", " + score + "]";}
  }
  

  public class Test4 {public static void main(String[] args) {Map<Student, String> map = new TreeMap<>();map.put(new Student("Jack", 18, 100), "广州");map.put(new Student("Rose", 22, 99), "广州");map.put(new Student("Jack", 18, 100), "深圳");System.out.println(map);//[Rose, 22, 99.0]=广州, [Jack, 18, 100.0]=深圳}//重写了equals()方法和hashCode()方法后，TreeMap中的key就根据内容判断是否重复，而不是比较地址//第一个和第三个key的内容相同，所以第三个key的value覆盖了第一个key的value}
  }
  

3. LinkedHashMap

3.1 底层实现原理

哈希表 = 数组

• 底层数据结构依然是基于哈希表实现的，与LinkedHashSet基本相同，只是LinkedHashSet中的元素变成了entry对象，并且所有构建哈希表的规则不是基于整个entry对象，而是基于entry对象中的键。
• 与HashMap的区别在于新增了双链表的机制来记录每个entry对象插入的位置来保证有序，规则与LinkedHashSet的规则一致，插入的是整个entry对象，但是插入规则都是基于键，与值毫无关系
• 实际上LinkedHashSet集合的底层原理就是LinkedHashMap，只不过只要键，丢弃值

4. TreeMap

4.1 特点

不重复、无索引、可排序（按照键的大小默认升序排序，只能对键排序）

4.2 底层实现原理

TreeMap跟TreeSet集合的底层原理是一样的，都是基于红黑树实现的排序。

TreeMap是对键进行排序，值只是一个附属

4.3 自定义排序规则的两种方式

4.3.1 让键对应的自定义类实现Comparable接口来自定义排序规则

//实现Comparable接口使得Student类可以根据自定义规则供TreeMap用来排序
public class Student implements Comparable<Student> {private String name;private int age;private double score;//重写compareTo()方法使得TreeMap可以按照分数升序排序@Overridepublic int compareTo(Student o) {return Double.compare(this.score, o.score);}public Student(String name, int age, int score) {this.name = name;this.age = age;this.score = score;}public String toString() {return "[" + name + ", " + age + ", " + score + "]";}public int getAge() {return age;}
}

public class Test4 {public static void main(String[] args) {Map<Student, String> map = new TreeMap<>();map.put(new Student("Jack", 18, 100), "广州");map.put(new Student("Rose", 22, 99), "广州");map.put(new Student("mack", 21, 100), "深圳");System.out.println(map);//{[Rose, 22, 99.0]=广州, [Jack, 18, 100.0]=深圳}//在键的自定义类中实现Comparable接口使得TreeMap可以按照分数升序排序，相同的分数会被判定为重复并覆盖}
}

4.3.2 使用TreeMap集合的有参构造器，入参为Comparator比较器对象，用于自定义比较规则

public class Test4 {public static void main(String[] args) {//TreeMap的有参构造方法可以传入一个Comparator对象，用于指定按照age升序排序Map<Student, String> map = new TreeMap<>((o1, o2) ->Integer.compare(o1.getAge(), o2.getAge()));map.put(new Student("Jack", 18, 100), "广州");map.put(new Student("Rose", 22, 99), "广州");map.put(new Student("mack", 21, 100), "深圳");System.out.println(map);//{[Jack, 18, 100.0]=广州, [mack, 21, 100.0]=深圳, [Rose, 22, 99.0]=广州}}
}

补充知识：集合的嵌套

集合中的元素还是一个集合

案例

需求

要求在程序中记住如下省份和其对应的城市信息，记录成功后，要求查询出湖北省的城市信息。

• 江苏省=南京市，扬州市，苏州市，无锡市，常州市
• 湖北省=武汉市，孝感市，十堰市，宜昌市，鄂州市
• 河北省=石家庄市，唐山市，邢台市，保定市，张家口市

分析

1. 定义一个Mp集合，键用表示省份名称，值表示城市名称(值应该是一个list集合)
2. 根据“湖北省”这个键找到对应的值并展示

public class Test5 {public static void main(String[] args) {//创建Map集合Map<String, List<String>> map = new HashMap<>();List<String> list1 = new ArrayList<>();Collections.addAll(list1,"南京市","扬州市","苏州市","无锡市","常州市");List<String> list2 = new ArrayList<>();Collections.addAll(list2,"武汉市","孝感市","十堰市","宜昌市","鄂州市");List<String> list3 = new ArrayList<>();Collections.addAll(list3,"石家庄市","唐山市","邢台市","保定市","张家口市");map.put("江苏省",list1);map.put("湖北省",list2);map.put("河北省",list3);//找到湖北省对应的值List<String> province = map.get("湖北省");//遍历输出province.forEach(s -> System.out.print(s + " "));//武汉市 孝感市 十堰市 宜昌市 鄂州市}
}

三、JDK8新特性：Stream

1.Stream流概述

1.1 概念

也叫Stream流，用于操作集合或者数组的数据。

1.2 优点

Stream流大量的结合了Lambda的语法风格来编程，提供了一种更加强大，更加简单的方式操
作集合或者数组中的数据，代码更简洁，可读性更好。

1.2 初体验案例

//需求：将下面的list1集合中所有以“张”开头，且是3个字的元素存储到一个新集合中。
public class Test1 {public static void main(String[] args) {List<String> list1 = new ArrayList<>();Collections.addAll(list1, "张无忌", "周芷若", "赵敏", "张强", "张三丰","张三", "李四");System.out.println(list1);//[张无忌, 周芷若, 赵敏, 张强, 张三丰, 张三, 李四]//不使用stream流List<String> list2 = new ArrayList<>();for (String s : list1) {if (s.startsWith("张") && s.length() == 3) {list2.add(s);}}System.out.println(list2);//[张无忌, 张三丰]//使用stream流，极大的简化了代码List<String> list3 = list1.stream().filter(s -> s.startsWith("张")&& s.length() == 3).collect(Collectors.toList());System.out.println(list3);//[张无忌, 张三丰]}
}

2. Stream的使用步骤

1. 获取Stream流：创建一条流水线并与要处理的(数组或集合)数据源建立连接
2. 调用中间方法：通过调用各种中间方法对流上的数据进行处理
   1. 只要流没有经过终结方法的处理，就可以无限次调用中间方法进行处理，支持链式编程
3. 调用终结方法：是流水线上的最后一个操作，用于获取处理后的结果。

• 一旦调用终结方法就表示该Stream流已经结束了，不能再调用中间方法对流上的数据进行处理，如果还想继续处理，只能重新获取流。

2.1 获取Stream流常用方法

2.1.1 获取集合的Stream流

Collection提供的方法	说明
default stream stream( )	获取当前集合对象的Stream流

public class Test3 {public static void main(String[] args) {//1.获取List集合的Stream流List<String> list = new ArrayList<>();Collections.addAll(list, "张三丰", "张无忌", "周芷若", "赵敏", "张翠山");Stream<String> stream1 = list.stream();//2.获取Set集合的Stream流Set<String> set = new HashSet<>();Collections.addAll(set, "张三丰", "张无忌", "周芷若", "赵敏", "张翠山");Stream<String> stream2 = set.stream();//3.获取Map集合的Stream流Map<String,Integer> map = new HashMap<>();map.put("张三丰",100);map.put("张无忌",200);map.put("周芷若",300);map.put("赵敏",400);//3.1获取key的Stream流//先获取key的Set集合，再获取Set集合的Stream流Stream<String> keyStream = map.keySet().stream();//3.2获取value的Stream流//先获取value的Collection集合，再获取Collection集合的Stream流Stream<Integer> valueStream = map.values().stream();//3.3获取entry对象的的Stream流//先获取entry对象的Set集合，再获取Set集合的Stream流Set<Map.Entry<String, Integer>> entries = map.entrySet();Stream<Map.Entry<String, Integer>> entryStream = entries.stream();}
}

2.2.2 获取数组的Stream流

Arrays类提供的方法	说明
public static Stream stream(T[ ] array)	获取当前数组的Stream流

Stream类提供的方法	说明
public static Stream of(T… values)	获取当前可变参数的Stream流

public class Test2 {public static void main(String[] args) {String[] name = {"lmh", "lmh2", "lmh3"};// 1. 通过Arrays.stream,参数为数组Stream<String> stream1 = Arrays.stream(name);// 2. 通过Stream.of,参数为数组元素，接收的参数为可变参数//可以不传，也可以传一个或多个，或直接传入数组Stream<String> stream2 = Stream.of(name);Stream<String> stream3 = Stream.of("lmh", "lmh2", "lmh3");Stream<String> stream4 = Stream.of();Stream<String> stream5 = Stream.of("lmh");}
}

2.2 Stream流常用的中间方法

中间方法是指调用完成后会返回新的Stream流，可以继续对流进行操作，支持链式编程

中间方法	说明
Stream filter(Predicate predicate)	对流中的数据进行过滤，相当于if，参数为匿名内部类
Stream sorted( )	对元素进行升序排序
Stream sorted(Comparator comparator)	按照指定规则排序，参数为匿名内部类
Stream limit( long maxSize )	获取前maxSize个元素
Stream skip( long n )	获取除去前n个元素外其他元素
Stream distinct( )	去除流中重复的元素，默认比较地址是否重复，如果相比较内容要重写equals和hashCode方法
Stream map(Function mapper)	对元素进行加工，将当前元素映射(转换)为其他类型元素并返回新的流，之后的操作都对两个元素一起操作，参数为匿名内部类
static Stream concat(Stream a, Stream b)	合并a和b为新的流，即新的流进行操作时会同时处理a和b中的所有元素

//需求1：找出成绩大于等于80的所有成绩，升序后输出
public class Test4 {public static void main(String[] args) {List<Double> scores = new ArrayList<>();Collections.addAll(scores, 89.5, 78.5, 99.0, 80.0, 66.5, 82.0, 76.0);//需求1：找出成绩大于等于80的所有成绩，升序后输出scores.stream().filter(s -> s >= 80).sorted().forEach(s -> System.out.print(s + " "));//80.0 82.0 89.5 99.0}
}

//需求2：找出年龄大于等于23，且年龄小于等于30岁的学生，并按照年龄降序输出.
public class Test4 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//需求2：找出年龄大于等于23，且年龄小于等于30岁的学生，并按照年龄降序输出.students.stream().filter(s -> s.age >= 23 && s.age <= 30).sorted((s1, s2) -> Integer.compare(s2.age, s1.age)).forEach(s -> System.out.print(s + " "));//{alice, 30, 1.93} {james, 26, 1.98} {tom, 23, 1.68}}
}

//需求3：取出身高最高的前3名学生，并输出。
public class Test4 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));students.stream().sorted((s1, s2) -> Double.compare(s2.height, s1.height)).limit(3).forEach(s -> System.out.print(s + " "));//{james, 26, 1.98} {james, 31, 1.95} {alice, 30, 1.93} }
}

//需求4：取出身高倒数的2名学生，并输出。
public class Test4 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//需求4：取出身高倒数的2名学生，并输出。students.stream().sorted((s1, s2) -> Double.compare(s2.height, s1.height)).skip(students.size() - 2).forEach(s -> System.out.print(s + " "));//等价于students.stream().sorted((s1, s2) -> Double.compare(s1.height, s2.height)).limit(2).forEach(s -> System.out.print(s + " "));//{tom, 23, 1.68} {jack, 22, 1.78} }
}

//需求5：找出身高超过1.78的学生叫什么名字，要求去除重复的名字，再输出。
public class Test4 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//需求5：找出身高超过1.78的学生叫什么名字，要求去除重复的名字，再输出。/*map映射相当于进行加工，上面相当于把Student对象的流换成name的流，之后的所有操作都是基于name，把流上原来的数据换成另外的数据放上去下面代码中将student映射成了student.height，之后都操作heightdistance默认比较内容是比较对象的地址，如果想要比较内容需要重写equals和hashcode方法下面代码可以去重是因为此时流中为String类型，String已经重写了equals和hashcode方法*/students.stream().filter(student -> student.height > 1.78).map(student -> student.name).distinct().forEach(s -> System.out.print(s + " "));System.out.println();//milan james alice }
}

//需求6：合并两个流的数据并一起输出
public class Test4 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//需求6：合并两个流的数据并一起输出List<Student> students2 = new ArrayList<>();students2.add(new Student("a", 22, 1));students2.add(new Student("b", 23, 2));Stream<Student> stream1 = students.stream();Stream<Student> stream2 = students2.stream();Stream.concat(stream1, stream2).forEach(s -> System.out.print(s + " "));//{jack, 22, 1.78} {tom, 23, 1.68} {milan, 20, 1.88} //{james, 26, 1.98} {james, 31, 1.95} {alice, 30, 1.93} //{a, 22, 1.0} {b, 23, 2.0} }
}

2.3 Stream流常用的终结方法

终结方法调用完成后不会再返回新的Stream流，当前流已经结束，无法再进行操作

2.3.1 常用方法(不包括收集流)

Stream提供的常用终结方法（不包括收集流）	说明
void forEach(Consumer action)	遍历流中元素，入参为匿名内部类
long count()	返回当前流中元素个数
Optional max(Comparator< ? super T> comparator)	获取当前流的最大值元素,入参为匿名内部类,返回值为Optional类型，需要获取后使用该对象的get方法获取当中的元素
Optional min(Comparator< ? super T> comparator)	获取当前流的最小值元素，入参为匿名内部类,返回值为Optional类型，需要获取后使用该对象的get方法获取当中的元素

public class Test5 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//1.输出身高超过1.9米的学生信息students.stream().filter(student -> student.height > 1.9).forEach(student -> System.out.print(student + " "));//{james, 26, 1.98} {james, 31, 1.95} {alice, 30, 1.93}System.out.println();//2.输出身高超过1.9米的学生人数long count = students.stream().filter(student -> student.height > 1.9).count();System.out.println("身高超过1.9米的学生人数 = " + count);//身高超过1.9米的学生人数 = 3//3.找到年龄最大的学生Optional<Student> max = students.stream().max((s1, s2) -> Integer.compare(s1.age, s2.age));Student student = max.get();System.out.println("年龄最大的学生 = " + student);//年龄最大的学生 = {james, 31, 1.95}//4.找到年龄最小的学生Student student1 = students.stream().min((s1, s2) -> Integer.compare(s1.age, s2.age)).get();System.out.println("年龄最小的学生 = " + student1);//年龄最小的学生 = {milan, 20, 1.88}}
}

收集流的常用方法

Stream提供的常用收集流的终结方法	说明
R collect(Collector collector)	把流处理后的结果收集到一个指定的集合中去
Object[ ] toArray( )	把流处理后的结果收集到一个数组中去，返回值为Object[ ] 类型，如果想返回指定类型，需要传入参数，实例见下面代码

Collectors工具类提供的具体的收集方式	说明
public static Collector toList( )	把元素收集到List集合中
public static Collector toSet( )	把元素收集到set集合中
public static Collector toMap(Function keyMapper, Function valueMapper)	把元素收集到Map集合中，传入参数实例见下面代码

public class Test6 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//1.将年龄大于30的学生作为一个新的List返回List<Student> list = students.stream().filter(student -> student.age > 30).collect(Collectors.toList());System.out.println(list);//[{james, 31, 1.95}]//2.将年龄大于30的学生作为一个新的Set返回Set<Student> set = students.stream().filter(student -> student.age > 30).collect(Collectors.toSet());System.out.println(set);//[{james, 31, 1.95}]//3.将年龄大于30的学生作为一个新的Map返回，key是名字，value是年龄Map<String, Integer> map = students.stream().filter(student -> student.age > 30).collect(Collectors.toMap(student -> student.name, student -> student.age));System.out.println(map);//{james=31}//4. 将身高大于1.8的学生作为一个新的数组返回Object[] array = students.stream().filter(student -> student.height > 1.8).toArray();System.out.println(Arrays.toString(array));//如果想将返回的数组类型指定为Student[]，可以使用方法引用，告诉编译器Student[]::newStudent[] array1 = students.stream().filter(student -> student.height > 1.8).toArray(Student[]::new);System.out.println(Arrays.toString(array1));//[{milan, 20, 1.88}, {james, 26, 1.98}, {james, 31, 1.95}, {alice, 30, 1.93}]}
}

处理后的结果收集到一个数组中去，返回值为Object[ ] 类型，如果想返回指定类型，需要传入参数，实例见下面代码 |

Collectors工具类提供的具体的收集方式	说明
public static Collector toList( )	把元素收集到List集合中
public static Collector toSet( )	把元素收集到set集合中
public static Collector toMap(Function keyMapper, Function valueMapper)	把元素收集到Map集合中，传入参数实例见下面代码

public class Test6 {public static void main(String[] args) {List<Student> students = new ArrayList<>();students.add(new Student("jack", 22, 1.78));students.add(new Student("tom", 23, 1.68));students.add(new Student("milan", 20, 1.88));students.add(new Student("james", 26, 1.98));students.add(new Student("james", 31, 1.95));students.add(new Student("alice", 30, 1.93));//1.将年龄大于30的学生作为一个新的List返回List<Student> list = students.stream().filter(student -> student.age > 30).collect(Collectors.toList());System.out.println(list);//[{james, 31, 1.95}]//2.将年龄大于30的学生作为一个新的Set返回Set<Student> set = students.stream().filter(student -> student.age > 30).collect(Collectors.toSet());System.out.println(set);//[{james, 31, 1.95}]//3.将年龄大于30的学生作为一个新的Map返回，key是名字，value是年龄Map<String, Integer> map = students.stream().filter(student -> student.age > 30).collect(Collectors.toMap(student -> student.name, student -> student.age));System.out.println(map);//{james=31}//4. 将身高大于1.8的学生作为一个新的数组返回Object[] array = students.stream().filter(student -> student.height > 1.8).toArray();System.out.println(Arrays.toString(array));//如果想将返回的数组类型指定为Student[]，可以使用方法引用，告诉编译器Student[]::newStudent[] array1 = students.stream().filter(student -> student.height > 1.8).toArray(Student[]::new);System.out.println(Arrays.toString(array1));//[{milan, 20, 1.88}, {james, 26, 1.98}, {james, 31, 1.95}, {alice, 30, 1.93}]}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！