《Java核心技术（卷1）》笔记：第9章集合

集合

（P 365）Enumeration接口提供了一种用于访问任意容器中各个元素的抽象机制
（P 367）队列接口：Queue
```
public interface Queue<E> {
    void add(E element);
    E remove();
    int size();
}
```
- 循环数组队列：ArrayQueue（有界集合，容量有限）
- 链表队列：LinkedList
- 其他：AbstractQueue（用于扩展实现自己的队列）
（P 368）集合接口：Collection
```
public interface Collection<E> {
    boolean add(E element);
    Iterator<E> iterator();
    ...
}
```
实现自己的接口时，可以继承AbstractCollection（P 371）

（P 368）迭代器接口：Iterator

public interface Iterator<E> {
    E next();
    boolean hasNext();
    void remove();	// 删除上次调用next方法时返回的对象
    default void forEachRemaining(Consumer<? super E> action);
}

（P 369）for-each循环可以处理任何实现了Iterable接口的对象（Collection接口扩展了Iterable接口）
```
public interface Iterable<E> {
    Iterator<E> iterator();
    ...
}
```
（P 373）集合框架的接口

graph TD Iterable --> Collection Collection --> List Collection --> Set Collection --> Queue Set --> SortedSet SortedSet --> NavigableSet Map --> SortedMap SortedMap --> NavigableMap Iterator --> ListIterator RandomAccess
（P 374）集合的两个基本接口：Collection和Map
（P 374）ListIterator接口是Iterator的子接口，其定义了一个方法用于在迭代器位置前面增加一个元素
（P 374）RandomAccess接口：标记接口，用于测试一个特定的集合是否支持高效的随机访问
（P 375）SortedSet和SortedMap接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法
NavigableSet和NavigableMap包含一些用于搜索和遍历有序集和映射的方法

TreeSet和TreeMap实现了这些接口

（P 376）集合中的框架类

graph TD AbstractCollection --> AbstractList AbstractCollection --> AbstractSet AbstractCollection --> AbstractQueue AbstractCollection --> ArrayQueue AbstractList --> AbstractSequentialList AbstractList --> ArrayList AbstractSequentialList --> LinkedList AbstractSet --> HashSet AbstractSet --> EnumSet AbstractSet --> TreeSet HashSet --> LinkedHashSet AbstractQueue --> PriorityQueue
graph TD AbstractMap --> HashMap AbstractMap --> TreeMap AbstractMap --> EnumMap AbstractMap --> WeakHashMap AbstractMap --> IdentityHashMap HashMap --> LinkedHashMap
（P 384）ArrayList是异步的，Vector是同步的
（P 385）hashCode方法应与equals方法兼容，即如果a.equals(b)为true，则a与b必须有相同的散列码
（P 385）Java中，散列表用链表数组实现（Java 8中，使用平衡二叉树代替）
（P 388）要使用树集，必须能够比较元素。这些元素必须实现Comparable接口，或者构造集时必须提供一个Comparator。树的排序顺序必须是全序，任意两个元素都必须是可比的，并且只有在两个元素相等时结果才为0
（P 391）双端队列接口：Deque
- 实现类：ArrayDeque、LinkedList
（P 392）优先队列（Priority queue）中的元素可以按照任意的顺序插入，但会按照有序的顺序进行检索
- 典型用法：任务调度
（P 393）PriorityQueue与TreeSet的迭代不同，它并不是按照有序顺序来访问元素。不过，删除操作却总是删除剩余元素中最小的那个元素

映射

（P 394）如果对同一个键调用两次put方法，第二个值就会取代第一个值，put将返回与这个键参数关联的上一个值
（P 394）迭代处理映射的键和值：
```
map.forEach((k, v) -> { ... });
```
（P 397）putIfAbsent方法：只有当键原先不存在（或者映射到null）时，才会放入一个值

（P 397）merge方法：

map.merge(word, 1, Integer::sum);
// 相当于
map.putIfAbsent(word, 0);
map.put(word, map.get(word) + 1);

（P 398）3种映射视图：
- 键集：Set<K> keySet()
- 值集合（不是一个集）：Collection<V> values()
- 键/值对集：Set<Map.Entry<K, V>> entrySet()
（P 399）WeakHashMap：当对键的唯一引用来自散列表映射条目时，这个数据结构将与垃圾回收器协同工作一起删除键/值对
（P 400）LinkedHashSet和LinkedHashMap类会记住插入元素项的顺序

（P 401）EnumSet是一个枚举类型元素集的高效实现，内部用位序列实现。其没有构造器，需要使用静态工厂方法构造这个集：

enum Weekday { MONDAY, TUESDAY, ... , SUNDAY};
EnumSet<WeekDay> always = EnumSet.allOf(Weekday.class);
EnumSet<WeekDay> none = EnumSet.noneOf(Weekday.class);
EnumSet<WeekDay> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<WeekDay> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);

（P 401）EnumMap是一个键类型为枚举类型的映射，它可以直接且高效的实现为一个值数组
```
var personInCharge = new EnumMap<Weekday, Employee>(Weekday.class);
```
（P 402）IdentityHashMap类中，键的散列值不是用hashCode函数计算的，而是用System.identityHashCode方法计算的。在对两个对象进行比较时，IdentityHashMap类使用==，而不是用equals
（P 403）视图（view）：例如keySet方法返回一个实现了Set接口的类对象（这个对象不是新创建的），由这个类的方法操纵原映射，这种集合称为视图
- 小集合
- 子范围视图
- 不可修改的视图
- 同步视图
- 检查型视图

（P 404）小集合（它的对象是不可修改的）：

List<String> names = List.of("Peter", "Paul", "Mary");	// 任意个参数
Set<Integer> numbers = Set.of(2, 3, 5);	// 任意个参数
Map<String, String> scores = Map.of("Peter", 2, "Paul", 3, "Mary", 5);	// 0 ~ 10对参数
Map<String, String> scores = Map.ofEntries(
    Map.entry("Peter", 2),
    Map.entry("Paul", 3),
    Map.entry("Mary", 4)
);	// 任意个参数

List<String> settings = Collections.nCopies(100, "DEFAULT");// 返回一个看起来像存储了100个字符串的List，实际上只存储了1个，减小开销

（P 405）子范围：

List<Employee> group2 = staff.subList(10, 20);	// 取staff的第10~19个元素
group2.clean();	// group2被清空，staff相应的元素也被清除

算法

（P 412）排序：Java中的排序采用的是归并排序，比快速排序慢一些，但优点是归并排序是稳定的（不会改变相等元素的顺序）

var staff = new LinkedList<Employee>();
...
// 排序
Collections.sort(staff);
// 按员工工资排序
staff.sort(Comparator.comparingDouble(Employee::getSalary));
// 降序排序
staff.sort(Comparator.reverseOrder());
// 按员工工资降序排序
staff.sort(Comparator.comparingDouble(Employee::getSalary).reversed());

（P 413）打乱元素顺序：
```
Collections.shuffle(cards);
```
（P 414）二分查找：binarySearch方法，待查找的集合必须能够随机访问，否则（例如提供一个链表）将失去意义，退化为线性查找
```
i = Collections.binarySearch(c, element);
i = Collections.binarySearch(c, element, comparator);
```
返回值：
- 非负值：匹配对象的索引
- 负值：查找失败，可以根据此值计算出element插入到集合中的位置
```
insertionPoint = -i - 1;
```
（P 415）简单算法（详见API文档）
- 查找集合中的最大元素
- 将一个列表中的元素复制到另外一个列表中
- 用一个常量值填充容器
- 逆置一个列表的元素顺序

（P 417）批操作（详见API文档）

coll1.removeAll(coll2);	// 从coll1中删除coll2中出现的所有元素
cool1.retainAll(coll2);	// 从coll1中删除所有未在coll2中出现的元素

（P 418）集合与数组的转换

// 数组转集合
String[] values = ...;
var staff = new HashSet<>(List.of(values));
// 集合转数组
String[] values = staff.toArray(new String[0]);

（P 420）集合框架中的遗留类

graph TD List --> AbstractList AbstractList --> Vector Vector --> Stack RandomAccess --> Vector Map --> Hashtable Hashtable --> Properties
（P 421）属性映射（property map）是一个特殊的映射结构，具有3个特性：
- 键与值都是字符串
- 这个映射可以很容易地保存到文件以及从文件加载
- 有一个二级表存放默认值

（P 421）Properties使用：对于指定程序的配置选项很有用

从文件加载

Properties p = new Properties();
InputStraem in = getClass().getClassLoader().getResourceAsStream("filename.properties");
p.load(in);
in.close();
...

保存到文件

Properties p = new Properties();
...
String path = getClass().getClassLoader().getResource("filename.properties").getPath();
FileOutputStream out = new FileOutputStream(new File(path));
p.store(out, "comment");
out.close();

读取属性
```
String value = p.getProperty("key");
```
写入属性
```
p.setProperty("key", "value");
```

《Java核心技术（卷1）》笔记：第9章 集合

集合

映射

算法

《Java核心技术（卷1）》笔记：第9章集合