Java集合

集合基础

• 集合是一种容器，用来装数据的，类似于数组
• 数组定义完成并启动后，长度就固定了
• 集合大小可变，开发中使用频率更多

ArrayList长度可变原理：

1. 当创建ArrayList集合容器的时候，底层会存在一个长度为10个大小的空数组
2. 当存储的数据长度超过了10，会扩容原数组1.5倍大小的新数组
3. 将原数组数据，拷贝到新数组中
4. 将新元素添加到新数组

集合和数组的使用选择：

• 数组：存储的元素个数固定不变
• 集合：存储的元素个数经常发生改变

创建集合

1. 空参构造创建集合格式：

   ArrayList list new ArrayList();
   list.add(1);
   list.add(12.3);
   list.add('a');
   list.add("abc");
   list.add(false);

   以上方式创建的集合可以存储任意类型的数据，但是这会导致集合中类型混乱，如果没有特殊需求，不推荐使用这种方式

2. 通过泛型指定集合中元素类型：

   ArrayList<String> list = new ArrayList<>();
   list.add(1);		// 报错
   list.add(12.3);		// 报错
   list.add('a');		// 报错
   list.add("abc");	
   list.add(false);	// 报错

   创建集合的时候加入泛型，可以使数据严谨和规范，推荐使用这种方式创建集合

   泛型的细节：只能编写引用数据类型，如果要存储int、double、float…需要使用包装类

基本数据类型包装类

数据类型	包装类名
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
boolean	Boolean
char	Character

只需要记住int => Integer和char => Character，其他都是首字母大写

常用的成员方法

ArrayList中的常见成员方法：

方法名	说明
public boolean add(E e);	将指定元素添加到此集合的末尾，添加成功返回true，否则返回false
public void add(int index， E element);	在此集合中的指定位置插入指定的元素
public E get(int index);	返回指定索引处的元素
public int size();	返回集合中元素的个数
public E remove(int index);	删除指定索引处的元素，返回被删除的元素
public boolean remove(Object o);	删除指定的元素，返回删除是否成功
public E set(int index,E element);	修改指定索引处的元素，返回被修改的元素

当指定元素插入的位置大于集合中最后一个元素的索引位置，会报错

删除指定位置元素不仅可以对原集合进行操作，还可以返回被删除的元素

当删除指定元素时，只会删除集合中找到的第一个匹配元素（最小索引），如果不存在指定元素则返回false

集合高级

集合分为两类：单列集合和双列集合

单列集合：

• 一次添加一个元素。
• 单列集合添加元素的方式：单列集合.add(元素1);
• 常见的单列集合：ArrayList、LinkedList、TreeSet、HashSet、LinkedHashSet
• 所有单列集合实现了Collection接口
• ArrayList、LinkedList实现了List接口，List是Collection的子接口
  • List接口：存取有序，有索引，可以存储重复值
• HashSet、LinkedHashSet实现了Set接口，Set是Collection的子接口
  • Set接口：存取无序，没有索引，不可以存储重复值

双列集合：

• 一次添加两个元素。
• 双列集合添加元素的方式：双列集合.put(元素1,元素2);
• 常见的双列集合：TreeMap、HashMap、LinkedHashMap
• 所有双列集合实现了Map接口

Collection接口

该接口提供了以下方法：

方法名称	说明
public boolean add(E e);	把给定的对象添加到当前集合中
public void clear();	清空集合中所有的元素
public boolean remove(E e);	把给定的对象在当前集合中删除
public boolean contains(Object obj);	判断当前集合中是否包含给定的对象
public boolean isEmpty();	判断当前集合是否为空
public int size();	返回集合中元素的个数/集合的长度

add方法注意事项：

/*
    add方法的设计思想：
    1. 在List中，add方法的返回值始终为true
    2. 但是在Set中，由于不允许添加重复值，所以是有可能出现false结果的
    3. 所以，为了接口的泛用性，将add方法设计成了带有布尔类型的返回值
*/
Collection<String> c1 = new ArrayList<>();
Collection<String> c2 = new HashSet<>();

boolean b1 = c1.add("张三");
boolean b2 = c1.add("张三");
boolean b3 = c1.add("张三");
System.out.println(c1);
System.out.println("b1：" + b1 + " b2：" + b2 + " b3：" + b3);     // b1：true b2：true b3：true

b1 = c2.add("张三");
b2 = c2.add("张三");
b3 = c2.add("张三");
System.out.println(c2);
System.out.println("b1：" + b1 + " b2：" + b2 + " b3：" + b3);     // b1：true b2：false b3：false

contains方法注意事项：

Collection<Student> c1 = new ArrayList<>();
c1.add(new Student("张三",18));
c1.add(new Student("李四",20));
c1.add(new Student("王五",19));
System.out.println(c1.contains(new Student("李四", 18)));     // true
System.out.println(c1.contains(new Student("李四", 20)));     // false

当对象中没有重写equals方法时，即使创建了数据相同的对象，contains也会返回false，因为contains底层就是调用equals方法进行比较的

equals不重写，说明比较的是地址值，即使对象的数据和查询的数据相同，也无法得到正确的答案

remove方法也是同理，要找到指定的对象，需要在类中重写equals方法

List接口

• List因为支持索引，所以多了很多索引操作的独特api
• List遍历方式有：迭代器、增强For、forEach、普通For循环、列表迭代器

列表迭代器（了解即可）：

List<String> list = new ArrayList<>();
list.add("001");
list.add("002");
list.add("003");
list.add("001");
list.add("005");

System.out.println("正序遍历：");
ListIterator<String> li = list.listIterator();
while (li.hasNext()) {
    System.out.print(li.next()  + " ");		// 001 002 003 001 005 
}

System.out.println();
System.out.println("倒序遍历：");
while (li.hasPrevious()) {
    System.out.print(li.previous() + " ");	// 005 001 003 002 001 
}

倒序遍历之前，必须将迭代器置于ArrayList的尾部元素

ArrayList类

• ArrayList底层是基于数组实现，所以查询操作快，增删操作相等较慢
• 使用空参构造器创建的集合，在底层创建一个默认长度为0的数组
• 添加第一个元素时，底层会创建一个新的长度为10的数组
• 存满时，再创建一个新的数组（大小为原数组的1.5倍）存放数据
• 1.5倍（即默认长度第一次扩容倍数）的扩容机制实际上是旧数组长度 + 旧数组长度/2

LinkedList类

• LinkedList底层基于双链表实现的，查询元素慢，增删首尾元素是非常快的

特有方法	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表中的第一个元素
public E getLast()	返回此列表中的最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

补充说明：

1. 虽然底层是双链表，但是可以通过get方法（根据索引）获取元素
2. 实际上，并不是直接通过索引就能直接找到，而是在底层，通过循环遍历依次查询的

示例：

LinkedList<String> list = new LinkedList<>();
list.add("张三");
list.add("李四");
list.add("王五");
list.add("赵六");

System.out.println(list.get(1));

源码如下：

// LinkedList.get(int index) 的核心逻辑
Node<E> node(int index) {
    if (index < (size >> 1)) { // 当索引数小于链表长度的一半，则从头部开始
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { // 从尾部开始
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Set接口

• 存取无序，无索引，不可以存储重复值
• 增删改查方法：Collection接口中的方法
• 遍历方式：三种通用遍历方式

名称	无索引	去重	存取无序	数据排序
TreeSet	✓	✓	✓	✓
HashSet	✓	✓	✓
LinkedHashSet	✓	✓

LinkedHashSet是所有Set集合中最特殊的一个，因为它存取有序

TreeSet集合

• 作用：对集合中的元素进行排序操作（底层红黑树实现）
• 红黑树是一种自平衡的二叉树，增删改查性能都很好

二叉树特点：

1. 任意节点开始，左边的节点都比当前的节点小，右边的节点都比当前节点大
2. 每次添加节点，都从根节点开始比大小，小的左边走，大的右边走，一样的不存

TreeSet自然排序

当TreeSet存储数据时，会自动进行排序。但是，如果存储的是自定义数据类型，底层就不知道该如何排序了：

TreeSet<Student> set = new TreeSet<>();     // 警告：Construction of sorted collection with non-comparable elements
set.add(new Student("张三",20));
set.add(new Student("李四",21));
set.add(new Student("王五",23));
set.add(new Student("张三",20));

解决方法：类需要实现Comparable接口，重写compareTo方法：

public class Student implements Comparable<Student>{
    private String name;
    private int age;

    public Student(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 "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        // 对年龄进行排序：
        return this.age - o.age;    // 正序排序：this - o，倒序排序：o - this
    }
}

底层原理：

第一次比较得出的结果虽然是零，但是因为它是树根，所以还是会被存储

记住规律：正序排序this - o，倒序排序o - this

以上案例，只比较了年龄，但是当有学生年龄相同时，就不会存储重复的年龄的对象，这不符合实际需求。

所以，只比较一个成员属性是不够的，还需要对姓名（字符串）进行比较：

字符串不能直接通过-操作符进行比较，但是字符串的底层实现了CompareTo接口，所以字符串的比较方式如下：

String s1 = "张";
String s2 = "李";
System.out.println(s1.compareTo(s2));   // -2094，说明张比李小

字符串比较规则：根据ASCII码按位比较，按位比较得不出结果再按长度比较

完善Student类中的compareTo方法：

@Override
public int compareTo(Student o) {
    // 倒序排序
    // 根据年龄为主要排序条件，姓名为次要排序条件，同姓名同年龄保留
    if (this.age != o.age) {
        return o.age - this.age;
    } else if (!this.name.equals(o.name)) {
        return o.name.compareTo(this.name);
    } else {
        return 1;
    }
}

// 测试
TreeSet<Student> set = new TreeSet<>();
set.add(new Student("张三",20));
set.add(new Student("李四",21));
set.add(new Student("王五",23));
set.add(new Student("张三",20));
set.add(new Student("李四四", 21));

System.out.println(set);
// [Student{name='王五', age=23}, Student{name='李四四', age=21}, Student{name='李四', age=21}, Student{name='张三', age=20}, Student{name='张三', age=20}]

TreeSet比较器排序

如果有的时候无法直接通过修改类里面的compareTo()方法，达到自己希望的排序方式：

Set<Integer> set = new TreeSet<>();
set.add(222);
set.add(111);
set.add(555);
set.add(444);
set.add(333);

System.out.println(set);    // [111, 222, 333, 444, 555]，如果希望倒序排序呢？

这时候，就需要用到比较器排序了

如果同时具备自然排序和比较器排序，优先按照比较器排序的规则进行操作

示例：

Set<Integer> set = new TreeSet<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});

set.add(222);
set.add(111);
set.add(555);
set.add(444);
set.add(333);

System.out.println(set);    // [555, 444, 333, 222, 111]

规则和自然排序类似，如果比较结果为0不会被存储

正序比较：o1 - o2，倒序比较：o2 - o1

也可以利用lambda表达式进行简写

自然排序 VS 比较器排序

个人理解：

• 自然排序的覆盖范围更广。只要在类中实现了Comparable接口且重写了compareTo方法，那么通过该类创建的所有对象都会按照compareTo方法进行排序
• 比较器排序则更精准。如果想要特定的集合遵循特定的排序方式，就需要在创建集合对象时，通过有参构造创建Comparator匿名内部类指定排序方式

HashSet集合

• HashSet集合底层采取哈希表存储数据，确保元素唯一性
• 哈希表是一种对增删改查数据性能都较好的结构

当类中没有重写equals和hashCode时，存储该类对象并不能去重：

HashSet<Person> set = new HashSet<>();
set.add(new Person("张三",23));
set.add(new Person("李四",24));
set.add(new Person("王五",25));
set.add(new Person("王五",25));
System.out.println(set);

// [Person{name='王五', age=25}, Person{name='张三', age=23}, Person{name='李四', age=24}, Person{name='王五', age=25}]

HashSet集合要保证元素唯一，需要在类中**同时重写hashCode和equals方法**

IDEA快速生成重写代码：

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age && Objects.equals(name, person.name);
}

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

当两个对象的hashCode相等，且调用equals方法也相同时（p1.hashCode() == p2.hashCode && p1.equals(p2)），就说明是同一个对象，需要去重

底层去重原理：

如果hashCode方法固定返回相同的值，数据都会挂在一个索引下面

hashCode方法

哈希值：

• 就是一个int类型的随机值，Java中每个对象都有一个哈希值

Object类的API

@IntrinsicCandidate
public native int hashCode();

• public int hashCode()：调用底层C++代码计算出的一个随机值（常被人称作地址值）
• 根据对象内容生成hash值，不同的对象，hash值也有可能会相等（哈希碰撞/哈希冲突）。比如：”重地”和”通话”

哈希表

• JDK8之前，哈希表 = 数组+链表
• JDK8开始，哈希表 = 数组+链表+红黑树
• 哈希表是一种增删改查数据，性能都较好的数据结构

JDK8版本之前：

存入数据位置：元素哈希值 % 数组长度 = 索引位置

扩容机制：

1. 当存入的元素数量（并非链表数量）达到16 * 0.75 = 12时，数组就会扩容，大小为原数组长度的两倍。

2. 重新计算元素的索引位置，最后再转移元素到新数组中

   • 因为元素哈希值 % 数组长度，当数组长度改变时，会导致元素位置发生改变

JDK8版本之后：

• 基本上的规则还是相同
• 但是，当链表长度超过8（超过8个结点），且数组长度>=64时，自动将链表转成红黑树

LinkedHashSet

• 依然是基于哈希表（数组、链表、红黑树）实现的
• 但是，它的每个元素都额外的多了一个双链表的机制记录它前后的元素（存取有序）
• 在性能方面，由于数据结构比较复杂，性能也会收到影响，效率不如HashSet高。没有特殊需求，不推荐使用LinkedHashSet。

Collections集合工具类

• java.utils,Collections：是集合工具类
• 作用：Collections并不属于集合，它是用来操作集合的工具类

方法名称	说明
public static <T> boolean addAll(Collection<? super T> c, T… elements)	给集合对象批量添加元素
public staic void shuffle(List<?> list)	打乱List集合元素的顺序
public static <T> max/min(Collection<T> coll)	根据默认的自然排序获取最大/最小值
public static <T> max/min(Collection<T> coll, Comparator<? super T> c)	根据指定的比较器排序获取最大/最小值
public static <T> void sort(List<T> list)	将集合中元素按照默认规则排序
public static <T> void sort(List<T> list, Comparator<? super T> c)	将集合中元素按照指定规则排序

查询自定义数据类型极值、排序，需要在类中具备自然排序条件（实现Comparable接口）

集合通用遍历方式

迭代器遍历

• Iterator 是 Java 集合框架中用于遍历集合（如 List、Set 等）元素的接口。
• 它提供了一种统一的方式来访问集合中的元素，而不需要关心集合的具体实现结构。

Collection<String> c = new ArrayList<>();
c.add("张三");
c.add("李四");
c.add("王五");

// 1. 通过集合对象，获取迭代器
Iterator<String> it = c.iterator();

// 2. 循环判断是否还有元素可以迭代
while (it.hasNext()) {
    // 3. 循环内部获取元素
    System.out.println(it.next());
}

ArrayList通过内部类实现了Iterator接口，所以可以直接通过集合.iterator()获取迭代器

hasNext()判断迭代器指向的集合位置是否有元素

next()获取迭代器指向的元素，并将迭代器向后移动一次

注意：在整个循环中next()方法最好只调用一次

增强for循环

• 简化迭代器的代码书写
• 它是JDK5之后出现的，其内部原理就是一个iterator迭代器（编译后生成的字节码文件会将增强for循环替换为迭代器遍历）

格式：

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

}

示例：

for (String s : list) {
	System.out.println(s);
}

forEach

方法名：default void forEach(Consumer<? super T> action);

示例：

Collection<String> c = new ArrayList<>();
c.add("张三");
c.add("李四");
c.add("王五");

StringBuilder namePlus1 = new StringBuilder();

c.forEach(s -> namePlus1.append(s));
System.out.println(namePlus1);  // 张三李四王五

还可以简化forEach中的代码：c.forEach(namePlus::append)，这个简化方式又称方法引用

所有的单列集合都可以用以上三种方式遍历

Map接口

• Map的实现类有：TreeMap，HashMap，LinkedHashMap（和Set集合类似）
• Map集合是一种双列集合，每个元素包含两个数据
• Map集合的每个元素的格式：key = value（键值对元素）
  • Key（键）：不允许重复
  • Value（值）：运行重复
  • 键和值是一一对应的，每个键只能找到自己对应的值
• Key+Value这个整体，我们称之为“键值对”或者“键值对对象”
  • 在Java中使用Entry对象表示
• 需要存储一一对应的数据时，可以考虑使用Map集合

Map集合实现类	特点
HashMap	元素按照键是无序，不重复，无索引，值不做要求
LinkedHashMap	元素按照键是有序，不重复，无索引，值不做要求
TreeMap	元素按照键是排序，不重复，无索引，值不做要求

Map常见API

• Map是双列集合的顶层接口，它的功能是全部双列集合都可以使用的

方法名称	说明
V put(K Key, V value)	添加元素。如果键已经存在，那键的旧值会被替换为新值（修改作用），并且返回旧值
V remove(Object key)	根据键删除键值对元素，返回被删除的值
void clear()	移除集合中所有键值对元素
boolean containsKey(Object key)	判断集合是否包含指定的键
boolean containsValue(Object value)	判断集合是否包含指定的值
boolean isEmpty()	判断集合是否为空
int size()	集合的长度，也就是集合中键值对的个数

Map集合遍历方式

1. 通过键找值
2. 通过键值对对象获取键和值
3. 通过forEach方法遍历

通过键找值

方法名称	说明
V get(Object key)	根据键查找对应的值
Set<K> keySet()	获取Map集合中所有的键

示例：

Map<Integer,String> map = new HashMap<>();
map.put(1,"张三");
map.put(2,"李四");
map.put(3,"王五");
map.put(4,"赵六");

Set<Integer> keySet = map.keySet();

for (Integer i : keySet) {
    System.out.println(map.get(i));
}

通过Entry获取键和值

方法名称	说明
Set<Map.Entry<K,V>> entrySet()	获取集合中所有的键值对对象

示例：

Map<Integer,String> map = new HashMap<>();
map.put(1,"张三");
map.put(2,"李四");
map.put(3,"王五");
map.put(4,"赵六");

Set<Map.Entry<Integer, String>> entries = map.entrySet();	// 获取所有Entry对象，用Set集合保存
for (Map.Entry<Integer, String> entry : entries) {
    System.out.println(entry.getKey() + "------" + entry.getValue());
}

Set集合中的泛型是Entry，Entry是Map中的一个内部接口，所以需要用Map.Entry

Map.Entry也需要指定泛型，且要与创建的Map集合中的泛型保持一致，所以最后的泛型结果为：Map.Entry<Integer, String>

通过forEach方法

方法名称	说明
default void forEach (BiConsumer<? super K, ? super V> action)	遍历Map集合，获取键值对

示例：

Map<Integer,String> map = new HashMap<>();
map.put(1,"张三");
map.put(2,"李四");
map.put(3,"王五");
map.put(4,"赵六");

// 匿名内部类
map.forEach(new BiConsumer<Integer, String>() {
    @Override
    public void accept(Integer integer, String s) {
        System.out.println(integer + "------" + s);
    }
});

// lambda
map.forEach((integer, s) -> System.out.println(integer + "------" + s));

Map的实现类

• TreeMap：键（红黑树）
• HashMap：键（哈希表）
• LinkedHashMap：键（哈希表 + 双向链表）

Map集合练习

第一题：字符串aababcabcbdabcde，统计字符串中每一个字符出现的次数，并按照以下格式输出a(5)b(4)c(3)d(2)e(1)

Scanner sc = new Scanner(System.in);
String str = sc.next();

Map<Character,Integer> map = new TreeMap<>();

for (int i = 0; i < str.length(); i++) {
    if (!map.containsKey(str.charAt(i))) {
        map.put(str.charAt(i),1);	// 当集合中不包含键时，初始化一个键值对
    } else {
        map.put(str.charAt(i), map.get(str.charAt(i)) + 1);		// 集合存在键时，将对应的值+1
    }
}

map.forEach((character, integer) -> System.out.println(character + "(" + integer + ")"));	// forEach遍历

方法引用

• 方法引用是JDK8开始出现，主要的作用，是对Lambda表达式进行进一步的简化

• 通过方法的名字来指向一个方法

  • 方法调用的方式一般为对象.方法名()或类.对象名()
  • 方法引用的方式一般为对象::方法名或类::对象名

• 示例：

• 核心特点：隐式传递参数，也就是说当符合条件时，可以省略参数的书写

• 条件：

  1. 方法引用的目标方法参数列表必须与函数式接口的抽象方法参数列表相匹配
  2. 方法引用只能在需要函数式接口的上下文中使用
  3. 方法必须是可访问的
  4. 方法引用不会显式传递参数，参数通过函数式接口自动传递，参数类型和数量必须精确匹配

方法调用和方法引用：

package com.norlcyan.methodReference;

import java.util.ArrayList;
import java.util.function.Consumer;

public class MethodReferenceDemo1 {
    public static void main(String[] args) {
        // 方法调用：MethodReferenceDemo1.change(s)
        // 方法引用：MethodReferenceDemo2::change
        ArrayList<String> list = new ArrayList<>();
        list.add("Hello");
        list.add("Hi Hello");
        list.add("niHao");
        
        // 方法调用：
        list.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                MethodReferenceDemo1.change(s);
            }
        });

        // 方法引用：
        list.forEach(MethodReferenceDemo1::change);
    }
    public static void change(String s) {
        System.out.println(s.toLowerCase());
    }
}

可推导可省略原则，省略参数

并发修改异常

• ConcurrentModificationException
• 说明：使用迭代器遍历集合的过程中，调用了集合对象的添加、删除方法，就会出现此异常
• 通俗理解：相当于两个人（多人）同时操作一个集合，就会导致冲突
• 示例：

List<String> list = new ArrayList<>();
list.add("张三");
list.add("李四");
list.add("王五");
list.add("赵六");

Iterator<String> it = list.listIterator();
while (it.hasNext()) {
    String name = it.next();
    if ("李四".equals(name)) {
        list.add("赵四");
    }
}

System.out.println(list);

以上代码表示：当遍历集合时，对集合进行了添加操作

解决方案：使用迭代器遍历时，不要使用集合中的添加或删除方法，而是用迭代器自身的添加或删除

List<String> list = new ArrayList<>();
list.add("张三");
list.add("李四");
list.add("王五");
list.add("赵六");

ListIterator<String>  li = list.listIterator();
while (li.hasNext()) {
    String name = li.next();
    if ("李四".equals(name)) {
        li.add("赵四");
    }
}

System.out.println(list);

要注意的是，普通迭代器中不存在增删方法，只有列表迭代器才支持add、remove方法

数据结构

• 数据结构是计算机底层存储、组织数据的方式，是指数据相互之间是以什么方式排列在一起的

• 通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

• 常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树、哈希表

栈

特点：数据先进后出，后进先出，如同弹夹压子弹一样（数据只有一个出口），数据进入的方式叫做压栈，出去的方式叫做弹栈

队列

特点：数据先进先出，后进后出，如同排队一样（数据有一个入口和一个出口）

数组

数组就是开辟一块连续的内存空间用于存放数据

特点：

• 查询速度快：查询数据通过地址值和索引定位，查询任意数据耗时相同
• 增、删效率低：新增或删除数据的时候，都有可能大批量的移动数组中其他的元素

链表

链表的最小单位是结点，单向链表的结点中通常存储数据+下一个结点的地址值，双向链表的结点中存储数据+上一结点的地址+下一个结点的地址值

当结点与结点之间相互链接起来后，形成的就是链表了

所以，链表与数组区别：

• 链表中的数据实际上在内存中是不连续的
• 每当查询链表中的某个数据，都要从链表的头结点依次往后查找，这就导致链表的查询速度比数组慢
• 但是，链表的增删相对更快（双向链表首尾结点操作极快）
  • 增：当在链表中的某个位置新增数据时，这个位置的前一个结点只需要更改下一个结点的地址值，并在新增的结点中添加下一个位置的结点地址值即可。整个操作只需要对两个结点进行操作，不影响其他位置的结点
  • 删：当需要删除链表中的某个数据时，把记录对应结点的地址值改为下下一个结点的地址值即可。比如：A(0x001) => B(0x002) => C(0x003)......，删除结点B，就变成了A(0x002) => C(0x003)......

泛型

• JDK5引入的，可以在编译阶段约束操作的数据类型，并进行检查
• 泛型的好处：
  • 统一数据类型
  • 将运行期的错误检查提升到了编译器
• 泛型中只能编写引用数据类型
• 泛型如果没有指定具体的类型，默认为Object

泛型类

示例：

public class GenericsDemo01 {
    /*
        泛型常见标识符：
            E ： Element 元素
            T ： Type    类型
            K ： Key     键
            V ： Value   值
    */
    public static void main(String[] args) {
        Student<String> s1 = new Student<>();
        s1.setName("张三");
        Student<Integer> s2 = new Student<>();
        s2.setName(123);
    }
}
class Student<E> {
    private E name;
    public Student() {
    }
    public Student(E name) {
        this.name = name;
    }
    public E getName() {
        return name;
    }
    public void setName(E name) {
        this.name = name;
    }
}

泛型方法

非静态方法：跟着类的泛型去匹配的。而类的泛型是在创建对象的时候确定到具体数据类型的

静态方法：调用方法的时候，根据传入实际的参数确定到具体数据类型

非静态方法参考上一章示例代码中的Get和Set方法

静态方法示例：

public class GenericDemo02 {
    public static void main(String[] args) {
        String[] arr1 = {"张三","李四","王五"};
        Integer[] arr2 = {1,2,3,4,5};
        Double[] arr3 = {1.1,2.2,3.3,4.4};

        printArray(arr1);
        printArray(arr2);
        printArray(arr3);
    }

    public static <T> void printArray(T[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println(arr[arr.length - 1] + "]");
    }
}

静态方法如果声明了泛型，必须声明出自己独立的泛型

泛型接口

1. 实现类实现接口的时候，确定到具体的类型
2. 实现类实现接口，没有指定具体类型，就让接口的泛型跟着类的泛型去匹配

public class GenericDemo03 {
    public static void main(String[] args) {
    	// 接口的泛型跟着类的泛型去匹配，所以这里接口的具体类型就是为String
        InterBImpl<String> ib = new InterBImpl<>();

        // 匿名内部类实现接口
        doInterface(new Inter<String>() {
            @Override
            public void show(String s) {
                System.out.println(s);
            }
        }, "HelloWorld");

        doInterface(new Inter<Integer>() {
            @Override
            public void show(Integer integer) {
                System.out.println(integer);
            }
        }, 123);
    }

    public static <E> void doInterface(Inter<E> i,E e) {
        i.show(e);
    }
}

@FunctionalInterface
interface Inter<E> {
    void show(E e);
}

// 实现接口时确定到具体类型
class InterAImpl implements Inter<String> {

    @Override
    public void show(String  s) {

    }
}

// 让接口的泛型跟着类的泛型去匹配
class InterBImpl<E> implements Inter<E> {

    @Override
    public void show(E e) {

    }
}

泛型通配符

• 泛型通配符的符号为?
• ?：可以传入任意类型
• ? extend E：可以传入的是E，或者是E的子类
• ? Super E：可以传入的是E，或者是E的父类

import java.util.ArrayList;

public class GenericsDemo04 {
    public static void main(String[] args) {
        ArrayList<Coder> list1 = new ArrayList<>();
        list1.add(new Coder());

        ArrayList<Manager> list2 = new ArrayList<>();
        list2.add(new Manager());

        ArrayList<String> list3 = new ArrayList<>();
        list3.add("");


        method(list1);
        method(list2);
        method(list3);  // 错误
    }

    public static void method(ArrayList<? extends Employee> list) {

    }
}

class Employee {
    String name;
    double salary;

    public Employee() {
    }

    public Employee(String name, double salary) {
        this.name = name;
        this.salary = salary;
    }
}

class Manager extends Employee{
    double prize;

    public Manager() {
    }

    public Manager(String name, double salary, double prize) {
        super(name, salary);
        this.prize = prize;
    }
}

class Coder extends Employee {
    String department;

    public Coder() {
    }

    public Coder(String name, double salary, String department) {
        super(name, salary);
        this.department = department;
    }
}

可变参数

• 可变参数用在形参中可以接收多个数据
• 可变参数的格式：数据类型... 参数名称
• 示例：public void showString(String... str)
• 可变参数本质上是一个数组

代码：

package com.norlcyan.args;

public class ArgsDemo {
    public static void main(String[] args) {
        System.out.println(getSum());
        System.out.println(getSum(1));
        System.out.println(getSum(1, 2));
        System.out.println(getSum(1, 2, 3));
        System.out.println(getSum(1, 2, 3, 4));
        System.out.println(getSum(1, 2, 3, 4, 5));
    }

    public static int getSum(int... nums) {
        if (nums.length == 0) {
            return 0;
        }

        int count = nums[0];

        for (int i = 1; i < nums.length; i++) {
            count += nums[i];
        }

        return count;
    }
}

1. 可变参数在方法中只能有一个
2. 如果方法中除了可变参数，还有其他的参数，需要将可变参数放在最后
3. 可变参数可以不传参数（getSum()），可传1个或多个参数，也可以传输一个数组

Stream流

• 配合Lambda表达式，简化集合和数组操作
• Stream流操作流程：
  1. 将数据到流中（获取流对象）
  2. 中间方法
  3. 终结方法

获取Stream流对象

集合获取Stream流对象

使用Collection接口中的默认方法

名称	说明
default Stream<E> stream()	获取当前集合对象的Stream流

示例：

// list
ArrayList<String> list = new ArrayList<>();
list.add("123");
list.add("132");
list.add("213");
list.add("231");
list.add("312");
list.add("321");
list.stream().forEach(System.out::println);
System.out.println("____________________________");

// set
Set<String> set = new HashSet<>();
set.add("123");
set.add("132");
set.add("213");
set.add("231");
set.add("312");
set.add("321");
set.stream().forEach(System.out::println);
System.out.println("____________________________");

// map => keySet()
Map<String,String> map = new HashMap<>();
map.put("123","1");
map.put("132","2");
map.put("213","3");
map.put("231","4");
map.put("312","5");
map.put("321","6");
map.keySet().stream().forEach(s -> System.out.println(s + "=" + map.get(s)));
System.out.println("____________________________");

// map => entrySet()
map.entrySet().stream().forEach(System.out::println);

数组获取Stream流对象

使用Arrays数组工具类中的静态方法

名称	说明
static <T> Stream<T> stream(T[] array)	将传入的数组封装到Stream流对象中

示例：

int[] arr = {11,22,33,44,55};
String[] str = {"张一","张二","张三","张四","张五"};

// 获取stream流对象
IntStream intStream = Arrays.stream(arr);
Stream<String> stringStream = Arrays.stream(str);
// 遍历打印
intStream.forEach(System.out::println);
stringStream.forEach(System.out::println);

// 简写
Arrays.stream(arr).forEach(System.out::println);
Arrays.stream(str).forEach(System.out::println);

零散数据获取Stream流对象

名称	说明
static <T> Stream<T> of(T… values)	把一堆零散的数据封装到Stream流对象中

示例：

// 获取流对象
Stream<String> stringStream = Stream.of("张三", "李四", "王五", "赵六");
Stream<Integer> integerStream = Stream.of(1, 2, 3, 4);
// 遍历打印
stringStream.forEach(System.out::println);
integerStream.forEach(System.out::println);

// 简写
Stream.of("张三", "李四", "王五", "赵六").forEach(System.out::println);
Stream.of(1, 2, 3, 4).forEach(System.out::println);

中间操作方法

• 对数据进行操作时，调用的方法返回Stream对象，就表示中间方法

名称	说明
Steam<T> filter(Predicate<? super ?> predicate)	用于对流中的数据进行过滤
Stream<T> limit(long maxSize)	获取前几个元素
Stream<T> skip(long n)	跳过前几个元素
Stream<T> distinct()	去除流中重复和元素依赖（hashCode和equals方法）
static <T> Stream<T> concat(Stream a, Stream b)	合并a和b两个流为一个流
Stream<R> map(Function<? super T, ? extends R> mapper)	对流中的每一个元素进行转换

过滤等简单操作：

ArrayList<String> list = new ArrayList<>();
list.add("123");
list.add("132");
list.add("213");
list.add("231");
list.add("312");
list.add("321");

// 将集合中以1开头的字符串打印到控制台中
list.stream().filter(s -> s.startsWith("1")).forEach(System.out::println);

// 获取集合中前三个字符串打印到控制台中
list.stream().limit(3).forEach(System.out::println);

// 跳过集合中前4个元素并将剩下的元素打印到控制台中
list.stream().skip(4).forEach(System.out::println);

// 拼接集合
ArrayList<String> newList = new ArrayList<>();
newList.add("张三");
newList.add("李四");
newList.add("王五");
Stream.concat(list.stream(),newList.stream()).forEach(System.out::println);

如果stream流对象调用过了终结方法（如forEach），就不能再继续调用了，需要重新获取流对象

map方法：

// 将元素转换为字符串形式，匿名内部类第一个泛型为自己，第二个泛型为目标类型
Stream.of(1, 2, 3, 4, 5).map(new Function<Integer, String>() {
    @Override
    public String apply(Integer integer) {
        return integer + "";
    }
}).forEach(System.out::println);

// 简写：
Stream.of(1, 2, 3, 4, 5).map(integer -> integer + "").forEach(System.out::println);

// 将每个元素 + 10：
Stream.of(1, 2, 3, 4, 5).map(i -> i + 10).forEach(System.out::println);

终结方法

名称	说明
void forEach(Consumer action)	对此流的每个元素执行遍历操作
long count()	返回此流中的元素个数

Stream收集操作

• Stream流操作，不会修改数据源

示例：

ArrayList<Integer> list = new ArrayList<>(List.of(1,2,3,4,5,6,7,8,9));
list.stream().filter(s -> s % 2 == 0).forEach(System.out::println);     // 2 4 6 8
System.out.println(list);   // 1 2 3 4 5 6 7 8 9

• 把Stream流操作后的结果数据转回到集合

名称	说明
R collect(Collector collector)	开始收集Stream流，指定收集器

• Collectors工具类提供了具体的收集方式

名称	说明
public static <T> Collector toList()	把元素收集到List集合中
public static <T> Collector toSet()	把元素收集到Set集合中
public static Collector toMap(Function keyMapper, Function valueMapper)	把元素收集到Map集合中

单列集合操作：

ArrayList<Integer> list = new ArrayList<>(List.of(1,2,3,4,5,6,7,8,9,10,10,10,10));

// toList
List<Integer> collect1 = list.stream().filter(s -> s % 2 == 0).collect(Collectors.toList());
System.out.println(collect1);   // [2, 4, 6, 8, 10, 10, 10, 10]

// toSet
Set<Integer> collect2 = list.stream().filter(s -> s % 2 == 0).collect(Collectors.toSet());
System.out.println(collect2);   // [2, 4, 6, 8, 10]

collect(Collectors.toList());在较新的JDK版本中可以直接写成toList()，但是Set不行

双列集合：

ArrayList<String> list = new ArrayList<>();
list.add("张三,23");
list.add("李四,24");
list.add("王五,25");

// 以名为键，以年龄为值
Map<String, String> map1 = list.stream().collect(Collectors.toMap(new Function<String, String>() {
    @Override
    public String apply(String s) {
        return s.split(",")[0];
    }
}, new Function<String, String>() {
    @Override
    public String apply(String s) {
        return s.split(",")[1];
    }
}));

// 简写
Map<String, String> map2 = list.stream().collect(Collectors.toMap(s -> s.split(",")[0], s -> s.split(",")[1]));
System.out.println(map2);	// {李四=24, 张三=23, 王五=25}

Stream综合案例

package com.norlcyan.stream;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Stream;

public class StreamTest {
    public static void main(String[] args) {
        ArrayList<String> manList = new ArrayList<>();
        manList.add("周润发");
        manList.add("成龙");
        manList.add("刘德华");
        manList.add("吴京");
        manList.add("周星驰");
        manList.add("李连杰");

        ArrayList<String> womanList = new ArrayList<>();
        womanList.add("林心如");
        womanList.add("张曼玉");
        womanList.add("林青霞");
        womanList.add("柳岩");
        womanList.add("林志玲");
        womanList.add("王祖贤");

        /*
            男演员只要名字为3个字的前两人
            女演员只要名字姓林的，且不要第一个
            把过滤后的男演员姓名和女演员姓名合并到一起
            将上一步操作后的元素作为构造方法的参数创建演员对象，遍历数据
        */
        Stream<String> manStream = manList.stream().filter(s -> s.length() == 3).limit(2);

        Stream<String> womanStream = womanList.stream().filter(s -> s.startsWith("林")).skip(1);
        Stream.concat(manStream,womanStream).map(Actor::new).forEach(System.out::println);
    }
}

class Actor {
    private String name;

    public Actor(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Actor{" +
                "name='" + name + '\'' +
                '}';
    }
}