第八章 Java集合

集合概述

• 集合用来储存数量不等的对象，且只能保存对象，实际保存的是对象的引用变量
• 主要由两个接口派生而出，Collection(派生了Set List Queue) Map
• Set无序不重复，List有序重复，Map key-value队，Queue是队列实现

---

Collection和Iterator接口

• Collection是Set List Queue的父接口，该接口里提供的方法可以操作Set、List、Queue集合。有add addAll clear contains containsAll isEmpty iterator remove removeAll retainAll size toArray。
• 所有的Collection实现类都已经重写了toString()方法
• Iterable是Collection的一个父接口，其forEach(Consumer action)默认方法可以用来遍历集合元素，Consumer是函数式接口，可以用Lambda表达式
• Iterator接口主要用于遍历Collection集合元素，Iterator对象被称为迭代器
• Iterator提供的方法：hasNext next remove forEachRemaining(java8新增)
• 用集合实例调用Iterator构造器创建迭代器实例，Iterator必须依附于Collection对象
• 值传递，修改迭代变量的值对集合无影响
• 使用Iterator迭代访问集合元素时，只能通过remove() next()返回的元素，其他修改都不允许，一旦检测到集合被修改，会立即引发异常
• Collection还可以用foreach循环来迭代访问集合元素，在迭代中同样不能改变集合
• Collection新增removeIf(Predicate filter)批量删除符合条件的集合元素
• Predicate是函数式接口，其test方法检测对象是否满足指定条件
• 独立使用Steam
  • 使用Steam或XxxSteam的builder()类方法创建Stream对应的Builder
  • 重复调用Builder的add()方法向该流中添加多个元素
  • 调用Builder的build()方法获取对应的Stream
  • 调用Stream的聚集方法
• 对于大部分的聚集方法，每个Stream只能执行一次，分为中间方法和末端方法，流的方法又两个特性，有状态的方法和短路方法
• Stream常用中间方法：filter mapToXxx peek distinct sorted limit
  常用末端方法：forEach toArray reduce min max count anyMatch allMatch nonMatch findFirst findAny
• 使用Collection接口提供的一个stream()默认方法返回集合对应的流，使用流式API来整体操作集合元素很方便

---

Set集合

• Set与Collection基本相同，没有提供额外的方法，Set不允许包含重复元素，不能记住元素添加顺序
• Set三个常用实现类，HashSet TreeSet EnumSet

HashSet

• HashSet是Set接口的典型实现，大多时候都用这个，按Hash算法来存储集合中的元素，具有很好的存取和查找性能
• 特点：不能保证元素的排列顺序、不是同步的，必须通过代码来保证其同步、集合元素可以是null
• 向集合中存入一个元素时HashSet会调用hashCode()方法得到该对象的hashCode值，根据值决定元素的储存位置
• HashSet判断两个元素的相等标准是equals()比较相等并且hashCode()方法返回值相等，所以重写方法时尽量保证equals()和hashCode()比较结果一致
• equals()相等hashCode()不等时，会将两个相同元素保存在不同位置，违背了Set的规则。equals()不等hashCode()相等时会在一个位置上用链式结构保存多个对象，导致定位性能下降。
• 重写hashCode()方法的基本规则：
  • 程序运行中，同一对象多次调用hashCode()方法应该返回相等的值
  • 两个对象equals()返回true时，hashCode()也应该又相同的返回值
  • 对象中用于equals()方法比较标准的实例变量也都应该用于计算hashCode值
• 当程序把可变对象添加到HashCode中后，尽量不要去修改参与计算hashCode()和equals()的实例变量，否则会导致HashSet无法正确操作这些集合元素
• HashSet有一个子类LinkedHashSet，它同时使用链表维护元素次序，遍历时会按元素添加顺序来访问
• LinkedHashSet因为需要维护元素的插入顺序，性能略低于HashSet，但在迭代访问全部元素时有良好的性能

TreeSet

• TreeSet是SortedSet接口的实现类，可以确保元素处于排序状态
• 比起HashSet额外提供的方法：comparator first last lower higher subSet headSet tailSet
• TreeSet采用红黑树的数据结构存储集合元素，支持两种排序方式：自然排序和定制排序，默认自然排序
• 自然排序调用Comparable接口的compareTo()方法来比较元素大小关系，然后升序排列
• 添加到自然排序TreeSet的对象必须实现了Comparable接口，实现了compareTo()方法
• 大部分类在实现compareTo()时都需要比较对象是相同类的实例，所以向TreeSet中添加的应该是同一个类的对象
• TreeSet比较两个对象是否相等的唯一标准是compareTo()是否返回0，重写equals()时应该保证与compareTo()方法结果一致
• TreeSet可以删除没有被修改实例变量且不与其他被修改实例变量的对象重复的对象
• 当TreeSet中可变对象的实例变量被修改时，处理这些对象很复杂且容易出错，所以不要修改关键的实例变量
• 定制排序，new TreeSet(Comparator对象)，可以用Lambda表达式代替，根据此来排序
• 依然不可以添加不同类的实例，比较元素相等的标准是Comparator

EnumSet

• EnumSet中的元素必须是指定美剧类型的枚举值，有序，以枚举值在枚举类内定义顺序来决定，不允许加入null
• 内部以位向量的形式储存，EnumSet对象占用内存小运行效率高
• EnumSet只能通过类方法来创建实例，allOf complementOf copyOf noneOf of range
• 试图复制一个Collection集合里的元素来创建EnumSet集合时，必须保证Collection集合里的所有元素都是同一个枚举类的枚举值

Set实现类的性能分析

• HashSet比TreeSet性能好，特别是添加、查询等操作，只有当需要保持排序的Set时才使用TreeSet，其他时候应该使用HashSet
• LinkedHashSet对于HashSet，普通的插入、删除操作较慢，但遍历会更快
• EnumSet是三个实现类中性能最好的，但是只能保存同一枚举类的枚举值作为集合元素
• 三个实现类都是线程不安全的，必须手动保证集合的同步性，可以通过Collections工具类的synchronizedSortedSet来包装Set集合，最好在创建时执行。

---

List集合

• List集合有序、可重复，每个元素都有对应的顺序索引，从0开始
• List接口增加的一些方法：get indexOf lastIndexOf set subList replaceAll sort，还有一些原有方法的重载
• List判断两个对象相等的唯一标准是equals()
• set(int index, Object element)方法不会改变List集合的成都，索引必须有效
• sort()和replaceAll()都可以提供一个Lambda表达式作为参数
• List还额外提供listIterator()，返回一个ListIterator对象，ListIterator接口继承了Iterator接口，增加了hasPrevious previous add 方法，增加了向前迭代的功能

ArrayList和Vector

• 都是基于数组实现的，封装了一个动态的、可再分配的Object[]数组，不指定initialCapacity时，数组默认长度为10
• initialCapacity参数设置数组的长度，会自动增加，当添加大量元素时可以用ensureCapacity(int minCapacity)方法一次性增加initialCapacity大小，减少分配次数，提高性能
• trimToSize()调整数组长度等于当前元素个数
• Vector比较古老，有很多缺点，不推荐使用
• ArrayList线程不安全，Vector线程安全，所以性能相对较低
• Stack继承了Vector，模拟栈，进出栈都是Object类型，需要类型转换，提供了peek pop push方法，同样比较古老不推荐使用，应该考虑ArrayDeque
• Arrays工具类有个asList()方法江数组转换成List集合，是Arrays内部类ArrayList的实例，固定长度，只能遍历访问，不能增删

---

Queue

• Queue用于模拟队列，Queue接口定义的方法：add element offer peek poll remove
• Queue有一个PriorityQueue实现类，Deque子接口，Deque有ArrayDeque和LinkedList两个实现类

PriorityQueue实现类

• 保存队列元素的顺序是按元素大小进行排列，peek取出的是队列中最小的元素，不能插入null
• PriorityCity的toString()返回值影响看不到顺序输出
• 自然排序，实现Comparable接口，且元素应是同一个类的多个实例
• 定制排序，传入Comparator对象，不要求实现Comparable接口

Deque接口

• Deque是Queue的子接口，代表双端队列，定义了一些双端队列的方法还提供了pop push，也可以当作栈来使用
• Iterator descendingIterator()返回一个双端队列对应的迭代器，逆向顺序迭代队列中的元素
• Deque接口提供了一个典型的实现类ArrayDeque，基于数组实现的双端队列，同样可指定一个numElements，指定数组长度，不指定时默认16，提供了push peek pop方法
• ArrayDeque也可以作为队列使用，取决于使用的方法

LinkedList

• 同时实现了List和Deque，可以根据索引随机访问集合的元素，可以被当成双端队列使用，可以做栈也可以做队列
• LinkedList内部以链表的形式存储集合元素，随机访问性能较差，但是插入删除元素的性能较好

线性表的性能分析

• List是一个线性表接口，ArrayList和LinkedList是线性表的两个典型实现，一个是基于数组的，一个是基于链表的。Queue代表队列，Deque代表双端队列。
• 总体来说ArrayList比LinkedList性能好，大部分时候应该考虑用ArrayList
• 使用List集合的建议
  • 遍历List，对于ArrayList、Vector集合应该是用随机访问(get)来遍历，对于LinkedList应该采用迭代器(Iterator)来遍历
  • 经常插入删除元素应使用LinkedList，ArrayList和Vector经常重新分配内部数组大小性能较差
  • 多线程应考虑使用Collections包装成线程安全的集合，而不是去用古老的集合

---

Map集合

• Map用于保存具有映射关系额数据，键值对，key不允许重复，key童工equals方法比较
• 键值一一对应，Map中所有的key组成了一个Set集合，Map的实现类和子接口中的key集存储形式和对应的Set集合元素的存储形式完全相同
• Java先实现了Map，然后通过包装一个所有value都为null的Map实现了Set集合
• Map常用方法：clear containsKey containsValue entrySet get isEmpty keySet put putAll remove size values
• Map中有一个内部类Entry，封装了一个键值对，提供了三个方法：getKey getValue setValue
• 如果添加的键值对key重复，新添加的value将会覆盖原来的
• 所有的Map实现类都重写了toString()
• Java8新增Map方法：compute computeIfAbsent computeIfPresent forEach getOrDefault merge putIfAbsent replace replaceAll

HashMap和Hashtable

• Hashtable是一个古老的Map实现类，线程安全，，不允许null作为key和value
• HashMap线程不安全，可以null作为key和value
• HashMap和Hashtable的元素对象必须实现hashCode()和equals()并保证结果一致
• 当修改了作为key的可变对象，会出现和HashSet类似的情形，所以尽量不要使用可变对象，尽量不要修改可变对象
• LinkedHashMap，HashMap的子类，用双向链表来维护键值对的次序，与插入顺序保持一致
• Properties是Hashtable的子类，在处理属性文件时比较方便，相当于一个键值都是String的Map，getProperty setProperty load store

SortedMap接口和TreeMap实现类

• Map接口有子接口SortedMap，TreeMap为其实现类
• TreeMap时红黑数据结构，每个键值对为一个红黑树节点，同样的两种排序方式，自然排序和定制排序，规则同TreeSet
• TreeMap提供的访问键值对的方法：firstEntry firstKey lastEntry lastKey higherEntry higherKey lowerEntry lowerKey subMap tailMap headMap

WeakHashMap实现类

• key只保留了对实际对象的弱引用，所以key所引用的对象没有被其他强引用变量所引用，就有可能会被垃圾回收，WeakHashMap也可能自动删除这些键值对
• 如果需要使用弱引用，就不要让key引用的对象具有任何强引用，否则失去了使用WeakHashMap的意义

IdentityHashMap实现类

• key相等标准为key1==key2严格相等才认为是相等的
• 允许null作为key和value，不保证顺序

EnumMap实现类

• EnumMap的key都必须是单个枚举类的枚举值，创建EnumMap时需要显式或隐式指定它对应的枚举类
• 在内部以数组形式保存，根据key在枚举类中的定义顺序维护键值对顺序，不允许null作为key，但可以作为value

Map实现类性能分析

• Hashtable和HashMap实现机制几乎一样，由于Hashtable比较古老且线程安全，所以通常比HashMap慢
• TreeMap更慢，但是总处于有序状态，可以调用keySet()再使用toArray()生成key的数组，再使用Arrays的binarySearch()再排序的数组中快速地查询对象
• 一般应该多考虑使用HashMao，需要排序好的考虑用TreeMap
• LinkedHashMap比HashMap慢，EnumMap性能最好

---

HashSet和HashMap性能选项

• hash表中桶只有一个元素时有最好的性能，多个元素时以链表形式储存在一个桶里，按顺序搜索（hash冲突）
• hash表的负载影子达到负载极限时，hash表胡自动成倍增加桶地数量，将原有对象重新分配，放入新桶内，rehashing
• 负载极限默认0.75，折中时间和控件成本地开销，所占内存和查询开销

---

Collections工具类

• 对List集合地排序操作的类方法：reverse shuffle sort swap rotate
• 用于查找替换操作的类方法：binarySearch(保证List处于有序状态) max min fill frequency indexOfSubList replaceAll
• 同步控制的类方法：synchronizedXxx()将指定集合包装成线程同步的集合
  xxx c = Collections.synchronizedXxx(new XxxXxx());
• 设置不可变集合的类方法：emptyXxx singletonXxx unmodifiableXxx，返回值为集合的只读版本

---

Enumeration接口

• Enumeration时Iterator的古老版本，hasMoreElements nextElement
• 只有Vector Stack Hashtable BitSet这些古老的集合类支持Enumeration