通过分析 JDK 源代码研究 Hash 存储机制

核心提示： 程序①号代码处可以看到：table 的实质就是一个数组，一个长度为 capacity 的数组，通过分析 JDK 源代码研究 Hash 存储机制(7)，对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置，最后返回该 key 对应的 value 即可，看 Hash

程序①号代码处可以看到：table 的实质就是一个数组，一个长度为 capacity 的数组。

对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如图 1 所示：

图 1. HashMap 的存储示意

HashMap 的读取实现

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：

　public　V　get(Object　key)　
　{　
　//　如果　key　是　null，调用　getForNullKey　取出对应的　value　
　if　(key　==　null)　
　　return　getForNullKey();　
　//　根据该　key　的　hashCode　值计算它的　hash　码　
　int　hash　=　hash(key.hashCode());　
　//　直接取出　table　数组中指定索引处的值，　
　for　(Entry<K,V>　e　=　table[indexFor(hash,　table.length)];　
　　e　!=　null;　
　　//　搜索该　Entry　链的下一个　Entr　
　　e　=　e.next)　　//　①　
　{　
　　Object　k;　
　　//　如果该　Entry　的　key　与被搜索　key　相同　
　　if　(e.hash　==　hash　&&　((k　=　e.key)　==　key　
　　||　key.equals(k)))　
　　return　e.value;　
　}　
　return　null;　
　}