第9章 集合

• 在实现方法时，选择不同的数据结构会导致其实现风格以及性能存在着很大差异
• 这里，将跳过理论部分，近介绍如何使用标准库中的集合类

9.1 Java集合框架

9.1.1 将集合的接口与实现分离

• 队列接口的最简形式可能类似下面这样：

public interface Queue<E> {
    void add(E element);
    E remove();
    int size();
}

• AbstractQueue是为类库实现者而设计的

9.1.2 Collection接口

• 集合类的基本接口是Collection

9.1.3 迭代器

• 编译器简单地将“for each”循环翻译为带有迭代器的循环

因此，应该将Java迭代器认为是位于两个元素之间。当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

• next方法和remove方法的调用具有互相依赖性，如果调用remove之前没有调用next将是不合法的

9.1.4 泛型实用方法

• toArray

9.1.5 集合框架中的接口

• 两个基本接口：Collection和Map

9.2 具体的集合

集合体系

9.2.1 链表

• 在Java中，所有链表都是双向链表
• ListIterator包含add方法，在迭代器位置之前添加一个新对象

为什么要优先使用链表呢？使用链表的唯一理由是尽可能地减少在列表中间插入或删除元素所付出的代价。如果列表只有少数几个元素，就完全可以使用ArrayList

9.2.2 数组列表

• ArrayList封装了一个动态再分配的对象数组
• ArrayList方法不是同步的，如果需要同步，可以使用Vector

9.2.3 散列集

• 链表和数组可以按照人们的意愿排列元素的次序
• 有一种众所周知的数据结构，可以快速地查找所需要的对象，这就是散列表hashtable
• 散列表为每个对象计算一个整数，称为散列码hashCode
• 散列码是由对象的实例域产生的一个整数
• 如果自定义类，就要负责实现hashCode方法
• hashCode方法要与equals方法兼容
• 散列表用链表数组实现
• 在JavaSE8中，桶满时会从链表变为平衡二叉树

9.2.4 树集

• TreeSet是一个有序集合
• 将一个元素添加到树中要比添加到散列表中慢

9.2.5 队列与双端队列

• 不支持在队列中间添加元素
• 队列：Queue
• 双端队列：Deque

9.2.6 优先级队列

• 使用了一个优雅且高效的数据结构，称为堆(heap)
• 堆是一个可以自我调整的二叉树
• 使用优先级队列的典型示例是任务调度

9.3 映射

• 映射用来存放键/值对

9.3.1 基本映射操作

staff.forEach(k, v)->(System.out.println("key=" + k + ", value=" + v));

9.3.2 更新映射项

counts.merge(word, Integer::sum);

9.3.3 映射视图

• 集合框架不认为映射本身是一个集合
• 可以得到映射的视图(view)，这是实现了Collection接口或某个子接口的对象
• 3种视图
  1. 键集：Set<K> keySet()
  2. 值集合：Collection<V> values() values()
  3. 键值对集：Set<Map.Entry<K, V>> entrySet()

9.3.4 弱散列映射

• 一个弱引用进入队列意味着这个键不再被他人引用，并且已经被收集起来，于是，WeakHashMap将删除对应的条目

9.3.5 链接散列集与映射

• LinkedHashSet和LinkedHashMap
• 链接散列映射将用访问顺序，而不是插入顺序，对映射条目进行迭代

9.3.6 枚举集与映射

• EnumSet
• EnumMap

9.3.7 标识散列映射

• IdentityHashMap使用==而不是equals方法

9.4 视图与包装器

• 视图包装了接口，只能访问接口中定义的方法

9.4.1 轻量级集合包装器

• Collections工具类

9.4.2 子范围

• subrange
• List group2 = staff.subList(10, 20);

9.4.3 不可修改的视图

• unmodifiableCollection
• 使用原始的hashCode方法

9.4.4 同步视图

• 类库的设计者使用视图机制来确保常规集合的线程安全，而不是实现线程安全的集合类

9.4.5 受查视图

• checkedList

9.4.6 关于可选操作的说明

• 通常，视图有一些局限性，即可能只可以读、无法改变大小、只支持删除而不支持插入

9.5 算法

• 泛型集合接口有一个很大的优点，即算法只需要实现一次。

9.5.1 排序与混排

• sort使用稳定的排序算法：即不需要交换相同的元素

9.5.2 二分查找

• 只有采用随机访问，二分查找才有意义。快速定位中间位置的元素

9.5.3 简单算法

• 替换：Collections.replaceAll("C++", "Java");

9.5.4 批操作

• 通过视图实现批操作

9.5.5 集合与数组的转换

由于Java平台API的大部分内容都是在集合框架创建之前设计的，所以，有时候需要在传统的数组和比较现代的集合之间进行转换

• asList
• toArray

9.5.6 编写自己的算法

• 如果编写自己的算法，应该尽可能地使用接口，而不要使用具体的实现类

9.6 遗留的集合

• 从Java第1版问世以来，在集合框架出现之前已经存在大量遗留的容器类

9.6.1 Hashtable类

• Hashtable类与HashMap类的作用一样，是线程安全的
• 如果需要并发访问，应该使用ConcurrentHashMap

9.6.2 枚举

• 遗留集合使用Enumeration接口
• 集合体系使用Iterator接口
• 传递集合要比传递迭代器更为明智

9.6.3 属性映射：Properties

• property map
  • 键与值都是字符串
  • 表可以保存到一个文件中，也可以从文件中加载
  • 使用一个默认的辅助表

9.6.4 栈

• Stack类扩展于Vector类
• push和pop方法

9.6.5 位集

• BitSet：高效地存储位序列就可以使用位集