Java核心技术1-映射

摘要: 本文是《Java核心技术 10th》中关于映射的要点总结。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

映射

基本映射操作

Java 类库为映射提供了两个通用的实现：HashMap 和 TreeMap。这两个类都实现了 Map 接口。

散列映射对键的处理是对键进行散列。树映射对键的处理是用键的整体顺序对元素进行排序，并将其组织成搜索树。

• 建立映射

Map<String, Employee> staff = new HashMap<>();

• 往映射中添加对象，put 会返回用这个键存储的上一个值。

Employee harry = new Employee("Harry Hacker");
staff.put("987-98-9996", harry);

• 检索一个对象，如果没有给定键对应的信息，get 返回 null。

String id = "987-98-9996";
Employee e = staff.get(id);

• getOrDefault 用默认值代替 null 作为映射中不存在的键的返回值

• remove 从映射中删除给定键对应的元素。

• size 返回映射中的元素数。

• 迭代处理映射中的键和值。使用 foreach 方法。可以提供一个接收键和值的 lambda 表达式。

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

java.util.Map<K, V> 基本映射操作 API 总结1

// 获取与键对应的值；返回与键对应的对象，如果在映射中没有这个对象则返回null。键可以为null。
V get(Object key)

// 获得与键关联的值；返回与键关联的对象，或者如果未在映射中找到这个键，则返回defaultValue。
default V getOrDefault(Object key, V defaultValue)

// 将键与对应的值关系插入到映射中。如果这个键已经存在，新的对象将取代与这个键对应的旧对象。这个方法将返回键对应的旧值。如果这个键以前没有出现过则返回null。键可以为null，但值不能为null。
V put(K key, V value)

// 将给定映射中的所有条目添加到这个映射中。
void putAll(Map<? extends K, ? extends V> entries)

// 如果在映射中已经有这个键，返回true。
boolean containsKey(Object key)

// 如果映射中已经有这个值，返回true。
boolean containsValue(Object value)

// 对这个映射中的所有键/值对应用这个动作。
default void forEach(BiConsumer<? superK, ? super V>action)

java.util.TreeMap<K, V> 构造器总结

// 为实现Comparable接口的键构造一个空的树映射。
TreeMap()

// 构造一个树映射，并使用一个指定的比较器对键进行排序。
TreeMap(Comparator<? super K> c)

// 构造一个树映射，并将某个映射中的所有条目添加到树映射中。
TreeMap(Map<? extends K, ? extends V> entries)

// 构造一个树映射，将某个有序映射中的所有条目添加到树映射中，并使用与给定的有序映射相同的比较器。
TreeMap(SortedMap<? extends K, ? extends V>entries)

java.util.SortedMap<K, V> API 总结

// 返回对键进行排序的比较器。如果键是用Comparable接口的compareTo方法进行比较的，返回null。
Comparator<? super K> comparator()

// 返回映射中最小元素和最大元素。
K firstKey()
K lastKey()

更新映射项

有时要对键对应的值进行更新，而更新的时候需要用到该键对应的原值。此时需要先调用 get 得到原值，然后完成更新，再将更新后的值通过 put 放进去。

但有一种特殊情况，即键第一次出现的时候，此时 get 会返回 null，会出现 NullPointException 异常。

有两种处理方法：

(1) 可以用 getOrDefault 方法。例如 counts 是一个 HasnMap，值保存的是键的计数，每次更新的时候自增 1，那么写法就是下面这样：

counts.put(word, counts.getOrDefault(word, 0) + 1);

(2) 先调用 putIfAbsent 方法，只有当键原先不存在时才会放入值。

counts.putIfAbsent(word, 0);
counts.put(word, counts.get(word) + 1);

(3) 用 merge 方法化简上面的第二种操作。

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

上面的方法把 word 与 1 关联，否则用 Integer::sum 函数组合原值与 1。

java.util.Map<K, V> 更新映射项 API 总结

// 如果 key 与 一个非 null 值 v 关联，将函数应用到 v 和 value，将 key 与结果关联，或者如果结果为 null，则删除这个键。否则，将 key 与 value 关联，返回 get(key)。
default V merge(K key, V value, BiFunction<? super V, ?super V, ? extends V> remappingFunction) 

// 将函数应用到 key 和 get(key)。将 key 与结果关联，或者如果结果为 null，则删除这个键。返回 get(key)。
default V compute(K key, BiFunction<? super K, ? superV, ? extends V>remappingFunction)

// 如果 key 与一个非 null 值 v 关联，将函数应用到 key 和 v，将 key 与结果关联，或者如果结果为 null，则删除这个键。返回 get(key)。
default V computeIfPresent(K key, BiFunction<? superK, ? super V, ? extends V> remappingFunction)

// 将函数应用到 key，除非 key 与一个非 null 值关联。将 key 与结果关联，或者如果结果为 null，则删除这个键。返回 get(key)。
default V computeIfAbsent(K key, Function<? super K, ?extends V>mappingFunction) 

// 在所有映射项上应用函数。将键与非 null 结果关联，对于 null 结果，则将相应的键删除。
default void replaceAll(BiFunction<? super K, ? super V,? extends V> function)

映射视图

集合框架不认为映射本身是一个集合。但是可以得到映射的视图（view）： 这是实现了 Collection 接口或某个子接口的对象。

有 3 种视图：

• 键集
• 值集合（不是一个集）
• 键/值对集

下面的方法分别返回这三个视图。

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

注意：keySet 不是 HashSet 或 TreeSet，而是实现了 Set 接口的另外某个类的对象，Set 扩展了 Collection 接口，因此可以像集合一样使用 keySet。

枚举所有键

Set<String> keys = mapping.ketSet();
for (String key: keys) {
    ...
}

枚举所有键值对

使用视图：

for (Map.Entry<String, Employee>) entry: staff.entrySet() {
    String k = entry.getKey();
    Employee v = entry.getValue();
    ...
}

使用 forEach 方法：

staff.forEach((k, v) -> {
        ...
        });

java.util.Map<K, V> 返回视图的 API 总结

// 返回Map.Entry对象（映射中的键/值对）的一个集视图。可以从这个集中删除元素，它们将从映射中删除，但是不能增加任何元素。
 Set<Map.Entry<K, V>> entrySet()

// 返回映射中所有键的一个集视图。可以从这个集中删除元素，键和相关联的值将从映射中删除，但是不能增加任何元素。
 Set<K> keySet()

// 返回映射中所有值的一个集合视图。可以从这个集合中删除元素，所删除的值及相应的键将从映射中删除，不过不能增加任何元素。
Collection<V> values()

java.util.Map.Entry<K, V> API 总结

// 返回这一条目的键或值。
K getKey()
V getValue()
// 将相关映射中的值改为新值，并返回原来的值。
V setValue(V newValue)

若散列映射 WeakHashMap

垃圾回收器跟踪活动的对象。只要映射对象是活动的，其中的所有桶也是活动的，它们不能被回收。

因此，需要由程序负责从长期存活的映射表中删除那些无用的值。此外还可以用 WeakHashMap 完成这件事情。当对键的唯一引用来自散列条目时，这一数据结构将与垃圾回收器协同工作一起删除键/值对。

WeakHashMap 使用弱引用（weak references）保存键。WeakReference 对象将引用保存到另外一个对象中，在这里，就是散列键。对于这种类型的对象，垃圾回收器用一种特有的方式进行处理。

通常，如果垃圾回收器发现某个特定的对象已经没有他人引用了，就将其回收。但是如果某个对象只能由 WeakReference 引用，垃圾回收器仍然回收它，但要将引用这个对象的弱引用放入队列中。

WeakHashMap 将周期性地检查队列，以便找出新添加的弱引用。一个弱引用进入队列意味着这个键不再被他人使用，并且已经被收集起来。于是，WeakHashMap将删除对应的条目。

链接散列集与映射

LinkedHashSet 和 LinkedHashMap 类用来记住插入元素项的访问顺序。

链接散列映射用的是访问顺序对映射条目进行迭代。每次调用 get 或 put，受到影响的条目将从当前的位置删除，并放到条目链表的尾部（只有条目在链表中的位置会受影响，而散列表中的桶不会受影响。一个条目总位于与键散列码对应的桶中）。

构造散列映射表的方法：

LinkedHashMap<K, V>(initialCapacity, loadFactor, true)

实现高速缓存的最近最少使用原则，可以构造 LinkedHashMap 的子类，然后覆盖下面的方法：

// 如果想删除 eldest 元素，并同时返回 true，就应该覆盖这个方法。eldest 参数是预期要删除的条目。
// 这个方法将在条目添加到映射中之后调用。其默认的实现将返回 false。即在默认情况下，旧元素没有被删除。
// 可以重新定义这个方法，以便有选择地返回true。例如，如果最旧的条目符合一个条件，或者映射超过了一定大小，则返回 true。
protected boolean removeEldestEntry(Map.Entry<K, V> eldest)

下面的代码，是可以放 100 个元素的高速缓存：

Map<K, V> cache = new LinkedHashMap<>(128, 0.75F, true) {
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > 100;
            }
        }();

枚举集与映射

所有的枚举类型都扩展于泛型 Enum 类，例如 Weekday 扩展 Enum<Weekday>；E extends Enum<E> 的含义是：E 是一个枚举类型。

EnumSet 是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以 EnumSet 内部用位序列实现。如果对应的值在集中，则相应的位被置为 1。

EnumSet 类没有公共的构造器。可以使用静态工厂方法构造：

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

EnumMap 是一个键类型为枚举类型的映射。它可以直接且高效地用一个值数组实现。在使用时，需要在构造器中指定键类型：

EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);

java.util.EnumSet<E extends Enum<E>> API 总结

// 返回一个包含给定枚举类型的所有值的集。
static <E extends Enum<E>> EnumSet<E>allOf(Class<E> enumType)

// 返回一个空集，并有足够的空间保存给定的枚举类型所有的值。
static <E extends Enum<E>> EnumSet<E>noneOf(Class<E> enumType)

// 返回一个包含from～to之间的所有值（包括两个边界元素）的集。
static <E extends Enum<E>> EnumSet<E> range(Efrom, E to)

// 返回包括给定值的集。
static <E extends Enum<E>> EnumSet<E> of(E value)
static <E extends Enum<E>> EnumSet<E> of(E value,E... values)

标识散列映射 IdentityHashMap

在 IdentityHashMap 中，键的散列值不是用 hashCode 函数计算的，而是用 System.identityHashCode 方法计算的。这是 Object.hashCode 方法根据对象的内存地址来计算散列码时所使用的方式。

在对两个对象进行比较时，IdentityHashMap 类使用 ==，而不使用 equals。也就是说，不同的键对象，即使内容相同，也被视为是不同的对象。

在实现对象遍历算法（如对象串行化）时，这个类非常有用，可以用来跟踪每个对象的遍历状况。

---

视图与包装器

集合框架中的类，总览如下图：

前面我们提到了映射的视图，这里我们总结一下：

通过使用视图（views）可以获得其他的实现了 Collection 接口和 Map 接口的对象。映射类的 keySet 方法就是一个例子。

视图技术在集合框架中还有许多应用，下面我们来讨论一下：

轻量级集合包装器

• Arrays 类的静态方法 asList 将返回一个包装了普通 Java 数组的 List 包装器。这个方法可以将数组传递给一个期望得到列表或集合参数的方法。

Card[] cardDeck = new Card[52];

List<Card> cardList = Arrays.asList(cardDeck);

返回的对象不是 ArrayList，而是一个视图对象，带有访问底层数组的 get 和 set 方法，但改变数组大小的所有方法（例如，与迭代器相关的 add 和 remove 方法）都会抛出一个 UnsupportedOperationException 异常。

asList 方法可以接收可变数目的参数：

List<String> names = Arrays.asList("Amy", "Bob", "Carl");

• Collections.nCopies(n, anObject) 方法返回一个实现了 List 接口的不可修改对象。存储代价很小。例如：

List<String> settings = Collections.nCopies(100, "DEFAULT");

• Collections.singleton(anObject) 下面的方法将返回一个视图对象。这个对象实现了 Set 接口。返回的对象实现了一个不可修改的单元素集。例如：

Collections.singleton(anObject)

• 对于集合框架中的每一个接口，还有一些方法可以生成空集、列表、映射等等，集的类型可以推导得出。例如：

Set<String> deepThoughts = Collections.emptySet();

子范围

很多集合可以建立子范围（subrange）视图。例如：下面的代码取出范围 [10, 19] 的元素。

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

可以将任何操作应用于子范围，例如: 下面的代码会删除子范围，元素从 staff 中清除了，且 group2 为空。

group2.clear();

对于有序集和映射，可以使用排序顺序而不是元素位置建立子范围。例如：下面这些方法返回大于等于 from 且小于 to 的所有元素子集。

SortedSet<E> subSet(E from, E to)
SortedSet<E> headSet(E to)
SortedSet<E> tailSet(E from)

有序映射也有类似的方法，返回映射视图，该映射视图包含键落在指定范围内的所有元素。

SortedMap<K, V> subMap(K from, K to)
SortedMap<K, V> headMap(K to)
SortedMap<K, V> tailMap(K from)

NavigableSet 接口赋予子范围操作更多的控制能力。

NavigableSet<E> subSet(E from, boolean fromInclusive, E to, boolean toInclusive)
NavigableSet<E> headSet(E to, boolean toInclusive)
NavigableSet<E> tailSet(E from, boolean fromInclusive)

不可修改的视图

Collections 还有几个方法，产生集合的不可修改视图。这些视图对现有集合增加了一个运行时的检查。如果对集合试图进行修改，则抛出异常。

Collections.unmodifiableCollection
Collections.unmodifiableList
Collections.unmodifiableSet
Collections.unmodifiableSortedSet
Collections.unmodifiableNavigableSet
Collections.unmodifiableMap
Collections.unmodifiableSortedMap
Collections.unmodifiableNavigableMap>

每个方法都定义于一个接口。例如，Collections.unmodifiableList 与 ArrayList、LinkedList 或者任何实现了 List 接口的其他类一起协同工作。

以 Collections.unmodifiableList 方法为例，该方法返回一个实现 List 接口的类对象。该对象可以调用 List 接口中的所有方法，但所有更改器方法已经被重新定义为抛出一个 UnsupportedOperationException 异常。而不是将调用传递给底层集合。

由于视图只是包装了接口而不是实际的集合对象，所以只能访问接口中定义的方法。

unmodifiableCollection 方法（与 synchronizedCollection 和 checkedCollection 方法一样）将返回一个集合，它的 equals 方法不调用底层集合的 equals 方法。相反，它继承了 Object 类的 equals 方法，这个方法只是检测两个对象是否是同一个对象。如果将集或列表转换成集合，就再也无法检测其内容是否相同了。视图就是以这种方式运行的，因为内容是否相等的检测在分层结构的这一层上没有定义妥当。视图将以同样的方式处理 hashCode 方法。

但注意：unmodifiableSet 类和 unmodifiableList 类却使用底层集合的 equals 方法和 hashCode 方法。

同步视图

如果多线程访问集合，则必须确保结合不会被以外破坏。

类库的设计者使用视图机制来确保常规集合的线程安全，而不是实现线程安全的集合类。例如，Collections 类的静态 synchronizedMap 方法可以将任何一个映射表转换成具有同步访问方法的 Map：

Map<String, Employee> mapping = Collections.synchronizedMap(new HashMap<String, Employee>());

现在就可以多线程访问 mapping 了，get, put 都是同步操作的。

受查视图

受查视图用来对泛型类型发生问题时提供调试支持。

将错误类型的元素混入泛型集合会出问题：

ArrayList<String> strings = new ArrayList<>();
ArrayList rawList = strings;
rawList.add(new Date());

上面代码中错误的 add 在运行时检测不到，在后续调用 get，并将结果转化为 String 时，才会抛出异常。

受查视图可以检测到这类问题：

List<String> safeStrings = Collections.checkedList(strings, String.class);

视图的 add 方法将检测插入的对象是否属于给定的类。如果不属于给定的类，就立即抛出一个 ClassCastException。

但注意：受查视图受限于虚拟机可以运行的运行时检查。例如，对于 ArrayList <Pair<String>>，由于虚拟机有一个单独的“原始”Pair类，所以，无法阻止插入 Pair <Date>。

关于可选操作的说明

视图通常有局限性，例如只读、无法改大小、只支持删除而不支持插入，这些与映射的键视图一样。

如果试图进行不恰当操作，受限制的视图抛出 UnsupportedOperationException。

在集合和迭代器接口的 API 文档中，许多方法描述为“可选操作”。这看起来与接口的概念有所抵触。接口的设计目的正常来讲是要给出一个类必须实现的方法。解决方案是为每个只读视图和不能改变集合大小的视图建立各自独立的两个接口。但这样会使得接口数量成倍增长，类库设计者不能接受。

这种可选方法的设计方式不应该在用户的设计中使用。集合类库中使用，是因为设计者必须解决一组特别严格且又相互冲突的需求。用户希望类库应该易于学习、使用方便，彻底泛型化，面向通用性，同时又与手写算法一样高效。要同时达到所有目标的要求，或者尽量兼顾所有目标完全是不可能的。但是，在自己的编程问题中，很少遇到这样极端的局限性。

---