[数据结构与算法]09_集合

Java集合框架

集合接口与实现分离

可以使用接口类型引用集合对象

Collection接口

使用add方法添加元素，集合中不能有重复的对象

使用iterator方法返回一个实现了Iterator接口的迭代器对象，可以使用迭代器访问集合中的元素

迭代器

使用next方法访问下一个元素

使用hasNext方法判断没有到集合的末尾

Collection接口扩展了Iterable接口

使用for each循环处理任何实现了Iterable接口的对象

或使用forEachRemaining方法，并提供一个lambda表达式，来对每一个元素调用这个表达式

访问元素的顺序取决于集合类型

查找一个元素的唯一方法是调用next，在执行查找操作时，迭代器的位置就会随之向前移动

可以认为迭代器位于两个元素之间，当调用next时，迭代器就越过下一个元素，并返回这个元素的引用

使用remove方法删除迭代器上次调用next返回的元素，要先调用next越过将要删除的元素

如果一个迭代器发现他的集合被另一个迭代器或是被集合自身的某个方法修改了，会抛出ConcurrentModificationException异常

可以根据需要为一个集合关联多个迭代器，但这些迭代器只能读取集合，或者可以再关联一个同时读取的迭代器

为了检测到并发修改，可以使集合跟踪更改操作的次数，每个迭代器也维护一个单独的更改操作数，然后进行检查

泛型实用方法

AbstractCollection类将size方法和iterator方法保持为抽象方法，同时实现了Collection接口中的其他方法

可以使具体集合类扩展AbstractCollection类，以避免实现Collection接口的繁琐

Collection接口中还增加了与流有关的默认方法，如removeIf方法用于删除满足条件的元素

集合框架中的接口

java框架为不同类型的集合定义了大量接口

集合有两个基本接口，Collection和Map

具体集合

链表

链表LinkedList是一个有序集合，实现了ListIterator接口

java中的链表都是双向链接的

不支持随机访问，每次重头开始搜索

每个对象存储在单独的链接中，每个链接还存放着下一个和上一个链接的引用

使用listIterator方法返回实现了ListIterator接口的对象

使用previous方法返回迭代器反向越过的对象，使用hasprevious方法判断没有到集合的首部

使用next方法返回迭代器正向越过的对象，使用hasNext方法判断没有到集合的末尾

使用add方法在迭代器之前添加对象

使用set方法用一个新元素替换调用next或previous方法返回的上一个元素

数组列表

数组列表ArrayList，封装了一个动态再分配的对象数组

支持随机访问

在不需要同步时使用ArrayList，需要同步时视同Vector类

散列表

散列表为每一个对象计算一个散列码，散列码由对象的实例字段得出，用于快速地查找对象

注意hashCode方法与equals方法兼容

散列表由链表数组实现，列表的每一项称为桶，对象放在散列码与桶数取余的位置，桶满时会从链表变为平衡二叉树

通常将桶数设置为预计元素个数的75%~150%，且桶数是2的幂

如果散列表太满会进行再散列，使用装填因子（默认0.75）确定何时进行

HashSet散列集是由散列表实现的无序的集，使用add方法添加元素，使用contains方法快速查找元素是否存在

树集

TreeSet树集对散列集有所改进，是由树实现的一个有序集合

添加元素时较慢，会自动放置在排序位置上

保存的对象既可以是实现了Comparable接口，也可以是在构造器中提供了Comparator

队列与双端队列

队列允许高效地在尾部添加元素，并在头部删除元素

双端队列允许高效地在头部和尾部添加或删除元素

不支持在队列中间添加元素

ArrayDeque循环数组实现了Deque接口，双端队列，是一个有界集合，比链表更高效

优先队列

可以按任意的顺序插入，但会按有序的顺序进行检索

使用了堆数据结构，堆是一个可以自组织的二叉树

add方法和move方法可以让最小的元素移动到根进行操作，而不需要进行排序

但迭代不是按有序顺序来访问的

保存的对象既可以是实现了Comparable接口，也可以是在构造器中提供了Comparator

映射

Map映射用于存放键/值对

基本映射操作

映射有两个通用实现：HashMap、TreeMap，两个类都实现了Map接口

散列映射对键进行散列，树映射根据键的顺序组织为一个搜索树，散列和比较函数都只操作键

散列映射较快，但树映射可以有序访问

使用put方法添加一个键/值对

使用putIfAbsent方法只有当键存在时放入一个值

使用get方法通过键检索一个对象，检索失败则返回null

使用getOrDefault方法代替get方法，检索失败返回默认值

使用remove方法删除给定键对应的元素

使用size方法返回元素数

使用forEach方法对元素应用lambda表达式迭代处理

使用merge方法，如果键与非null值关联，对这个键值对应用一个函数，如果结果非null，将键与之关联，否则删除键

映射视图

映射没有实现Collection接口，但映射的视图是实现了Collection接口或其子类的对象

使用keySet方法返回一个键集的视图

使用values方法返回一个值集合的视图

使用entrySet方法返回一个键值对集的视图

Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()

在键集视图上调用迭代器的remove方法，会从映射中删除这个键和值

但不能向键集视图与映射条目集视图中添加元素

弱散列映射

是要映射对象时活动的，其中的所有桶也是活动的，它们不能被回收

使用WeakHashMap，当对键的唯一引用来自散列表映射条目时，这个数据结构将与垃圾回收器一起删除键值对

WeakHashMap使用弱引用保存键，WeakReference对象将包含另一对象的引用，在这里是一个散列表键

如果某个对象只能由WeakReference对象引用，则垃圾回收器会将其回收，但将引用这个对象的弱引用放入一个队列，WeakHashMap周期性检查队列，以便找出新添加的弱引用，WeakHashMap将删除相关联的映射条目

链接散列集与映射

LinkedHashSet与LinkedHashMap类会记住插入元素项的顺序

每当插入一个新元素时，将同时并入到一个双向链表中

每次调用get或put方法时，受影响的项将从当前位置删除，放到项链表的尾部，但散列表或映射的桶不受影响

可以实现“最近最少使用”原则

枚举集与映射

EnumSet是一个枚举类型元素集的高效实现，内部使用位序列实现

没有公共的构造器，要使用静态工厂方法构造

EnumMap是一个键类型为枚举类型的映射，可以直接且高效的实现为一个值数组

标志散列映射

IdentityHashMap 中，键的散列值是用System.identityHashCode方法计算，它根据对象的内存地址计算散列码

比较时，使用==而不使用equals方法，即使内容相同，也被视为不同的对象

视图与包装器

使用视图获取其他实现了Collection或Map接口的对象

好像创建一个新集，实际上返回一个实现了接口的集合对象，用于操控原映射

小集合

java9引入的一些静态of方法，可以生成给定元素的集或列表

其中List和Set接口分别有11个版本的of方法，分别对应0到11个参数，另外还有一个参数个数可变的方法

对于Map接口，则无法提供参数个数可变的of方法，但有另一个静态ofEntries方法，能接收多个Map.Entry<K,V>对象，使用静态entry方法创建这些对象

List<String> names = List.of("a","b","c");
Set<Integer> numbers = Set.of(1,2,3);

Map<String,Integer> scores = Map.of("a",1,"b",2,"c",3);
Map<String,Integer> scores = Map.ofEntries(
	entry("a",1),
	entry("b",2),
	entry("c",3));

这些集合对象是不可修改的，可以把这些不可修改的集合对象传递给构造器，以得到一个可以修改的集合

静态Collection.nCopies方法同样返回一个不可变对象，其中的对象只存储一次，存储开销很小

java9之前使用静态Arrays.asList方法，返回一个大小不可变的列表

子范围

使用subList方法获得列表子范围的视图

对子范围视图的操作会反映到整个列表

对于SortedSet有序集合和SortedMap有序映射的接口，可以使用排序顺序而不是元素位置建立子范围

SortedSet和NavigableSet有subSet、headSet、tailSet方法

SortedMap有subMap、headMap、tailMap方法

不可修改视图

静态unmodifiableCollection、unmodifiableList、unmodifiableSet、unmodifiableMap…等方法生成集合的不可修改视图，对现有集合增加了运行时检查，如果发现试图修改，则抛出异常，集合仍保持不变

其中的unmodifiableCollection生成的视图将不能调用底层集合的equals、hashCode方法，而是继承自Object

使用lookAt方法查看一个集合的内容，可以调用接口的全部方法

不可修改视图只是不能通过视图进行修改，并不是集合本身不可修改

视图只是包装了接口，而不是具体的集合对象，所以只能访问接口中定义的方法

同步视图

使用视图机制确保常规集合是线程安全的

使用静态Collection.synchronizedMap方法将一个Map对象转换为有同步访问方法的Map对象

检查型视图

检查型视图用于提供调试支持

如果使用add方法将错误类型混入泛型集合，在运行时检测不到，只有当另一部分代码调用get方法时才会出现异常

使用静态Collection.checkedList方法生成的视图将检查插入的对象，但受限于虚拟机可以完成的运行时检查

无法阻止擦除后为同一个原始类型的对象插入

算法

排序与混排

静态Collection.sort方法可以对实现了List接口的集合进行排序，它假定列表元素实现了Comparable接口

也可调用sort方法，并提供一个Comparator对象

传递个sort方法的列表必须是可修改的，但不要求可以改变大小

静态Collection.reverseOrder方法返回一个用于逆序排序的比较器，按comparaTo方法逆序排序

也可通过比较器调用reversed方法，按比较器进行逆序排序

staff.sort(Collection.reverseOrder());
staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed());

对于链表，sort方法只是将所有元素转入一个列表，然后对数组进行排序，再将序列复制回链表

静态Collection.shuffle方法随机的混排集合列表中的元素

二分查找

静态Collection.binarSearch方法实现二分查找

传入的集合必须是有序的

如果提供一个链表，binarSearch方法将自动退化为线性查找

批操作

removeAll方法成批的删除集合中出现的另一个集合中的元素

retainAll方法成批的删除集合中未在另一个集合中出现的元素

通过子范围视图，可以将批操作限制在子集合中

集合与数组的转换

使用of包装器将数组转化为集合

使用toArray方法将集合转换为数组，将返回一个Object[]数组，但传入一个指定类型的数组后，返回的数组将创建为同类型

遗留集合

Hashtable类

与HashMap类作用一样，接口也基本相同

Hashtable类的方法是同步的，但想要实现同步最好使用ConcurrentHashMap

枚举

遗留的集合使用Enumration接口遍历元素序列，包含hasMoreElements和nextElements方法

使用静态Collections.enumration产生一个枚举对象

可以使用Collections.list方法将元素收集到一个ArrayList中

java9可以将枚举转换为一个迭代器

传递集合比传递迭代器更明智

属性映射

Properties类的键与值都是字符串，可以很容易的保存到文件以及从文件中加载，有一个二级表存放默认值

使用store方法将Properties对象保存到文件中

使用setProperty设置属性

使用load方法从文件中加载属性

使用System.getProperties方法生成Properties对象描述系统信息

使用getProperty方法方法在权限范围内获得指定键名对应的系统属性

Properties类有两种提供默认值的机制

使用getProperty方法时，可以指定一个默认值，当查找的键不存在时，将自动使用默认值

也可以将所有默认值放在一个二级属性映射中，并在主属性映射中提供

属性是没有层次结构的简单表格

如果要存储复杂的配置信息，应使用Preferences类

栈

Stack类扩展了Vector类

能使用push和pop方法，但也能使用非栈操作的insert方法和remove方法

位集

BitSet类存储一个位序列，将位包装在字节里

使用位集比使用Boolean对象的ArrayList高效得多

使用get方法返回状态，使用set方法置为开，使用clear方法置为关