核心 Map
Java 自带了各种 Map 类。这些 Map 类可归为三种类型：
- 通用 Map，用于在应用程序中管理映射，通常在 java.util 程序包中实现
- HashMap
- Hashtable
- Properties
- LinkedHashMap
- IdentityHashMap
- TreeMap
- WeakHashMap
- ConcurrentHashMap
- 专用 Map，您通常不必亲自创建此类 Map，而是通过某些其他类对其进行访问
- java.util.jar.Attributes
- javax.print.attribute.standard.PrinterStateReasons
- java.security.Provider
- java.awt.RenderingHints
- javax.swing.UIDefaults
- 一个用于帮助实现您自己的 Map 类的抽象类
内部哈希： 哈希映射技术
几乎所有通用 Map 都使用哈希映射。这是一种将元素映射到数组的非常简单的机制，您应了解哈希映射的工作原理，以便充分利用 Map。
哈希映射结构由一个存储元素的内部数组组成。由于内部采用数组存储，因此必然存在一个用于确定任意键访问数组的索引机制。实际上，该机制需要提供一个小于数组大小的整数索引值。该机制称作哈希函数。在 Java 基于哈希的 Map 中，哈希函数将对象转换为一个适合内部数组的整数。您不必为寻找一个易于使用的哈希函数而大伤脑筋： 每个对象都包含一个返回整数值的 hashCode() 方法。要将该值映射到数组，只需将其转换为一个正值，然后在将该值除以数组大小后取余数即可。以下是一个简单的、适用于任何对象的 Java 哈希函数
int hashvalue = Maths.abs(key.hashCode()) % table.length;
（% 二进制运算符（称作模）将左侧的值除以右侧的值，然后返回整数形式的余数。）
实际上，在 1.4 版发布之前，这就是各种基于哈希的 Map 类所使用的哈希函数。但如果您查看一下代码，您将看到
int hashvalue = (key.hashCode() & 0x7FFFFFFF) % table.length;
它实际上是使用更快机制获取正值的同一函数。在 1.4 版中，HashMap 类实现使用一个不同且更复杂的哈希函数，该函数基于 Doug Lea 的 util.concurrent 程序包（稍后我将更详细地再次介绍 Doug Lea 的类）。
 | | 图 3： 哈希工作原理 |
该图介绍了哈希映射的基本原理，但我们还没有对其进行详细介绍。我们的哈希函数将任意对象映射到一个数组位置，但如果两个不同的键映射到相同的位置，情况将会如何？ 这是一种必然发生的情况。在哈希映射的术语中，这称作冲突。Map 处理这些冲突的方法是在索引位置处插入一个链接列表，并简单地将元素添加到此链接列表。因此，一个基于哈希的 Map 的基本 put() 方法可能如下所示
public Object put(Object key, Object value) { //我们的内部数组是一个 Entry 对象数组 //Entry[] table; //获取哈希码，并映射到一个索引 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % table.length; //循环遍历位于 table[index] 处的链接列表，以查明 //我们是否拥有此键项 — 如果拥有，则覆盖它 for (Entry e = table[index] ; e != null ; e = e.next) { //必须检查键是否相等，原因是不同的键对象 //可能拥有相同的哈希 if ((e.hash == hash) && e.key.equals(key)) { //这是相同键，覆盖该值 //并从该方法返回 old 值 Object old = e.value; e.value = value; return old; } } //仍然在此处，因此它是一个新键，只需添加一个新 Entry //Entry 对象包含 key 对象、 value 对象、一个整型的 hash、 //和一个指向列表中的下一个 Entry 的 next Entry //创建一个指向上一个列表开头的新 Entry， //并将此新 Entry 插入表中 Entry e = new Entry(hash, key, value, table[index]); table[index] = e; return null;}
如果看一下各种基于哈希的 Map 的源代码，您将发现这基本上就是它们的工作原理。此外，还有一些需要进一步考虑的事项，如处理空键和值以及调整内部数组。此处定义的 put() 方法还包含相应 get() 的算法，这是因为插入包括搜索映射索引处的项以查明该键是否已经存在。（即 get() 方法与 put() 方法具有相同的算法，但 get() 不包含插入和覆盖代码。） 使用链接列表并不是解决冲突的唯一方法，某些哈希映射使用另一种“开放式寻址”方案，本文对其不予介绍。 |
