2019.03.06 - Java集合（List, Set, Map）

集合的概念

集合：就是用来存放数据的一个容器

集合与数组的比较

为什么需要集合

• 数组

  • 长度是固定的，不能再去添加元素

  int[] a = {10, 20, 30};
  a[3] = 0;//报错，数组越界
  

• 集合类

  • 长度可以改变
  • 能存储任意的对象
  • 长度是随着元素的增加而增加

集合与数组的区别

1. 数组能存基本数据类型 和 引用数据类型
2. 集合当中只能存引用数据类型(对象)，也可存放基本数据类型（本质是 自动装箱）
3. 数组的长度是固定的，集合的长度可以改变

集合与数组的适用场合

• 如果元素个数是固定的，推荐使用数组
• 如果元素不固定，推荐使用集合

集合的集成体系

• Collection接口（父接口）
  • List接口（有序）
    • ArrayList实现类（数组）
    • LinkedList实现类（链表）
    • Vector实现类（数组）
  • Set接口（无序）
    • HashSet实现类（hash算法）
    • TreeSet实现类（二叉树）

继承关系图

Collection

Collection的特点

• List可以添加重复元素，而Set不能添加重复元素(如果添加重复时，其返回值为false)
• 可以添加基本数据类型（自动装箱）
• 添加任何对象
• 打印直接得到内容（List内部覆盖toString()）

Collection的常用方法

• add(元素)：追加对象，其返回值永远是true
• remove(元素)：移除指定的元素
• size()：判断集合的长度（有几个元素）
• clear()：清空集合
• isEmpty()：验证集合是否为空

与all相关的常用方法

• 集合.addAll(集合)：拼接集合

//c1是[a, b, c]
//c2是[a, b, c]
c1.addAll(c2)//[a, b, c, a, b, c]

• 集合.removeAll(集合)：删除两个集合的交集
• 集合.containsAll(集合)：判断调用的集合是否包含(全部包含) 传入的集合
  • 返回值：全部包含，true；未全部包含，false
• 集合1.retainAll(集合2)：取交集，把交集结果给 集合1
  • 返回值：如果改变，true；如果未变，false

集合的遍历

数组形式的遍历

• 先把集合转换成数组
• 然后遍历数组

元素为基本数据类型

元素为对象

向上转型(向根类转型)：数组里的元素都是Object类型

迭代器

迭代器常用方法

• 创建迭代器：集合.iterator()
  • 返回值：迭代器对象
  • 示例：Iterator it = c1.iterator();
• 获取元素：迭代器.next()
  • 返回值：获取当前游标的内容，游标并往后移动一位
  • 示例：Object o = it.next();
• 判断迭代器是否还有元素：迭代器.hasNext()
  • 返回值：有，true；无，false。

迭代器的遍历

语法格式

元素为自定义对象的遍历

• 定义Cat类
  
• 遍历元素为Cat类型的迭代器，需要 向下转型
  

List

• list有角标
• 根据角标添加元素：index必须<=size，否则会报错
• 根据角标获取元素

并发修改异常

• 并发修改异常：在迭代集合的过程中，是不允许直接修改集合结构。

  • 因为，在获取迭代器的时候，迭代器和集合进行了关联，为保持双方数据一致，modCount和expectedModCount需要是相等的。

• 如需删除，可使用迭代器的删除

• modCount != expectedModCount：就会抛出ConcurrentModificationException，目的是保证 迭代器 与 集合 的内容一致。

  • modCount：集合修改次数
  • expectedModCount：迭代当中记录集合修改的次数
  • 迭代器的remove()会强制modCount = expectedModCount;

代码示例

• Iterator有remove，但无add。
  

ListIterator（list迭代器）

• list特有的迭代器
• 拥有add()方法
  

ListIterator的常用方法

• hasPrevious()：迭代器当前元素 之前是否还有元素（倒序）
• previousIndex()：倒序游标
• previous()：前一个元素

ArrayList数据结构分析

ArrayList为什么可以增加元素

• 数组被初始化就不会被改变
• ArrayList：创建一个容量(角标)增加50%的新数组，把原数据复制到新数组中，然后扔掉原数组。

ArrayList特点

• 查询和修改元素较快：通过索引，就能找到对应的值
• 添加和删除比较慢：需要依次移动元素，即依次更改下标

代码练习：集合去重

元素为字符串

• contains()：判断集合是否包含某个对象，基于Object.equals()，即地址值的比较。

元素为自定义对象

• 因为contains()是地址的比较，需要重写Student类的equals()，使其基于name进行比较。
• 可以使用eclipse的sources -> generate equals 自动生成。
  

LinkedList

链表

• 优点：链表插入与删除元素，较快
• 缺点：查询与修改比较慢，因为需要遍历
• 与数组(ArrayList)正好相反

链表的结构

链表的插入、删除节点

LinkedList常用方法

• listIterator()：可以使用List父类的所有方法

独有方法

• list.addFirst("myxq");：在最前添加元素
• list.addLast("last");：在最后添加元素
• list.removeFirst();：移除第一个元素
• list.removeLast();：移除最后一个元素
• list.get(0)：根据角标获取元素，源码基于for遍历，效率低；而ArrayList基于角标直接获取，效率更高。

利用LinkedList构造栈

• 栈：先进后出
  

Vector

• Vector类很少使用，常用ArrayList
• 从1.2开始并入List接口

Vector特有方法

• addElement()：添加元素，现在使用add()
• elements()：获取所有元素，用于遍历

Vector与ArrayList

• 都是用数组实现
• Vector的synchronized方法都会加同步锁，更安全；而ArrayList无同步锁。

数组 转 集合

基本数据类型的数组 转 集合

• 优点：除了不能添加与删除元素外，集合当中的其他方法都可以使用
• 基本数据类型 转 数组时，把该数组的整体当中一个对象，其集合的内部元素只有1个。
• 一般不使用

引用数据类型的数组 转 集合

• 因为自动装箱，其集合的内部元素为多个。

代码示例

集合 转 数组

• 静态开辟空间：如何开辟的空间小于size，会自动创建size相同的空间大小。
  

练习：学科、班级与学生

• 学科下有多个班级，班级中有多名学生
• 思路：集合嵌套集合
  

集合Set

HashSet

• Set中存的元素是无序的，而且没有重复的元素。（用HashSet<>()实现）
• foreach(增强for循环)可以遍历迭代器。

代码示例

自定义对象的去重

• Set中的元素为自定义对象时，如何去重：必须覆盖 hashCode方法 和 equals方法。

• 如果自定义对象的属性相同，则判定为重复对象。

• hashCode

  • 每个对象都有一个hashCode值
  • hashCode值就是与内存地址对应的一个唯一编号
  • 自动重写的hashCode方法：属性相同时，hashCode值相同；反之亦反。

• add

  • 添加一个对象时，会调用hashCode方法
  • hashCode值不相同时，不会调用equals方法
    • hashCode值相同，且equals方法的返回值为true，则不添加进集合

代码示例：自定义对象的去重

LinkedHashSet

• LinkedHashSet为HashSet的子类
• 底层基于链表实现
• 在Set集合中，唯一能有序存取的（取出顺序与存入顺序一致）

代码示例：有序Set

练习

练习1：生成随机数

生成10个在1-20之间的不重复的随机整数。

练习2：字符串去重

字符串去重："aaabbbccc" -> "abc"

TreeSet

• 基于二叉树算法实现

• TreeSet是无序的（相对添加顺序），无重复元素

• TreeSet会对元素进行默认排序

  • 数字按照大小排序
  • 汉字按照Unicode码排序（包含Ascii码的字符）
    

• TreeSet只能存放同一类型
  

• 自定义对象不能直接添加进TreeSet

  • 除非，实现Comparable接口
  • 并覆盖compareTo方法
    • 返回0，只添加第一个元素
    • 返回1 或 任意正数，添加所有元素，正序显示（相对添加顺序）
    • 返回 任意负数，添加所有元素，倒序显示
      

• 详解compareTo方法

  • 在添加元素时，被调用
  • 返回0，表示为重复元素，不添加
  • 返回 任意正数，表示比根元素大，往右添加元素
  • 返回 任意负数，表示比根元素小，往左添加元素
    

TreeSet的自定义排序

• 简单的自定义排序的 流程剖析图：只比age
  

• 优化情况：比完age，再比name

  • ifelse简化写法：return num == 0 ? this.name.compareTo(obj.name) : num;
    

比较器

• 默认情况下，比较时会调用对象的compareTo方法进行比较
• 如果自定义比较器，就不适用compareTo方法，而使用你传入的比较器

示例代码：以字符串长度排序

示例的二叉树剖析图

• 打印结果（从左往右）：z, wc, cba, myx, aaaaaaaaaa

Map映射

类似Python的字典（dict）
Map映射是无序的

Map概念

• 映射关系：A集合 B集合（ArrayList, LinkedList, Vector, HashSet, LinkedHashSet, TreeSet）

• A集合中的每一元素，都可以在B集合中找到唯一一个值与之对应。

• A集合中的元素不能重复（Set）；B集合中的元素可以重复（List）

• A集合中的每个元素称为KEY；B集合中的元素称为Value

• 图示
  

• Map又称 双列集合
  

map的使用

添加

• map.put：添加实体
  • key1=value1：是一个entry，即键值对。
    
  • KEY已经存在，就会更新之前的值，并返回之前的值。
    

删除

• map.clear()：清空所有实体（键值对）
• map.remove(键名)：删除指定键名的实体

获取元素

• 获取一个元素：根据指定KEY获取对应的Value

  • map.get(键名)
  • 键名不存在时，返回值为null。
    

• 获取所有元素（遍历）

  • map没有迭代器，即不能使用foreach(快速遍历)
  • 解决方法：取出所有键，然后通过键获取对应的值。
    

• 遍历Map的简便写法
  

获取Entry实体

• entrySet()方法

  • Entry是定义在Map内部的一个接口
    

  • foreach快速遍历（基于迭代器的简写）
    

其他查看操作

• map.keySet：获取所有键名

• map.values：获取所有值
  

• map.size：查看元素个数

Map自定义对象做KEY

• 自定义Student类

class Student{
	String name;
	Integer age;
	Student(String name, Integer age){
		this.name = name;
		this.age = age;
	}
}

• Student类默认比较内存地址，需要覆盖其equals方法与hashCode方法
  

LinkedHashMap

• HashMap的KEY是没有顺序的
• LinkedHashMap添加的元素是有序的
  

TreeMap

• TreeMap会对KEY进行排序，类似TreeSet。
  

练习：统计字符的出现次数

• 统计字符串中每个字符出现的次数
• 注意hm的KEY类型是Character包装类，而不是String类。
  

HashTable

• HashMap与HashTable的异同

	HashMap	HashTable
相同	哈希算法、双列集合	-
区别1	线程不安全、效率比较高，1.2版才有	线程安全，效率不高，1.0之前就有
区别2	可以存储null	不能存储null

• 代码示例：