映射(Map)

  知道某些键的信息，并想要查找与之相对应的元素。映射(map)数据结构就是为此设计的。映射用来存放键/值对。

1.基本映射操作

  Java类库为映射提供了两个通用的实现：HashMap和TreeMap。这两个类都实现了Map接口。散列映射对键进行散列，树映射用键的整体顺序对元素进行排序，并将其组织成搜索树(散列或比较函数只能作用于键，与键关联的值不能进行散列或比较)。
  应该选择散列映射还是树映射？散列映射稍微快一些，如果不需要按照排列顺序访问键，就最好选择散列。

  要迭代处理映射的键和值，最容易的方法是使用forEach方法。可以提供一个接收键和值的lambda表达式。映射中的每一项会依序调用这个表达式。

Map<String, Integer> scores = ...;
scores.forEach((k, v)->
      System.out.println("key=" + k + ", value=" + v));

2.更新映射项

  处理映射时的一个难点就是更新映射项。正常情况下，可以得到与一个键关联的原值，完成更新后，再返回更新后的值。不过，必须考虑一个特殊情况，即键第一次出现。
  下面来看一个例子，使用一个映射统计一个单词在文件中出现的频度。看到一个单词时，计数器增1。

//当第一次看到word时，get会返回null。
counts.put("word", counts.get("word") + 1);
//作为简单的补救，可以使用getOrDefault()
counts.put("word", counts.getOrDefault("word", 0) + 1);
//或先调用putIfAbsent()方法
counts.putIfAbsent(word, 0);
counts.put("word", counts.get("word") + 1);

//如果键原先不存在，则把word与1关联；否则使用Integer::sum组合原值和1
counts.merge("word", 1, Integer::sum);

3.映射视图

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

  映射有3种视图：键集、值集合以及键/值对集。

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

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

  如果在键集视图上调用迭代器的remove方法，实际上会从映射中删除这个键和与它相关的值。不过，不能向键集视图增加元素。

4.弱散列映射(WeakHashMap)

  如果有一个值，对应的键已经不再使用了，假定对某个键的最后一次引用已经消亡，不再有任何途径引用这个值的对象了。但是，由于在程序中的任何部分没有再出现这个键，所以，这个键/值对无法从映射中删除。
  因此需要由程序负责从长期存活的映射表中删除那些无用的值，可以使用WeakHashMap完成这件事。

  WeakHashMap使用弱引用(weak references)保存键。如果某个对象只能由WeakReference引用，垃圾回收器仍然要回收它，但要将引用这个对象的WeakReference放入队列中。WeakHashMap将周期性地检查队列，以便找出新添加的WeakReference。一个WeakReference进入队列意味着这个键不再被他人使用，并且已经被收集起来。于是，WeakHashMap将删除对应的条目。

5.链接散列集与映射

  LinkedHashSet(链接散列集)和LinkedHashMap(链接散列映射)是用来记住插入元素项的顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。当条目插入到表中时，就会并入到双向链表中。

  链接散列映射(LinkedHashMap)将用访问顺序(调用顺序)，对映射条目进行迭代。每次调用get或put，受到影响的条目将从当前的位置删除，并放到条目链表的尾部。

  访问顺序对于实现高速缓存的“最近最少使用”原则十分重要。例如，可能希望将访问频率高的元素放在内存中，而访问频率低的元素则从数据库中读取。

6.枚举集与映射

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

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

7.标识散列映射

  类IdentityHashMap有特殊的作用。键的散列值不是用hashCode函数计算的，而是用System.identityHashCode方法计算的。这是Object.hashCode方法根据对象的内存地址来计算散列码时所使用的方式。而且，在对两个对象进行比较时，IdentityHashMap类使用==，而不使用equals。
  也就是说，不同的键对象，即使内容相同，也被视为不同的对象。在实现对象遍历算法(如对象串行化)时，这个类非常有用，可以用来跟踪每个对象的遍历状况。