通过阐明JDK源代码研究Hash存储机制
当前位置：以往代写 > JAVA 教程 >通过阐明JDK源代码研究Hash存储机制

通过阐明JDK源代码研究Hash存储机制

2019-06-14

通过阐明JDK源代码研究Hash存储机制

通过阐明JDK源代码研究Hash存储机制

副标题#e#

通过 HashMap、HashSet 的源代码阐明其 Hash 存储机制

荟萃和引用

就像引用范例的数组一样，当我们把 Java 工具放入数组之时，并不是真正 的把 Java 工具放入数组中，只是把工具的引用放入数组中，每个数组元素都是 一个引用变量。

实际上，HashSet 和 HashMap 之间有许多相似之处，对付 HashSet 而言， 系统回收 Hash 算法抉择荟萃元素的存储位置，这样可以担保能快速存、取荟萃 元素；对付 HashMap 而言，系统 key-value 当成一个整体举办处理惩罚，系统老是 按照 Hash 算法来计较 key-value 的存储位置，这样可以担保能快速存、取 Map 的 key-value 对。

在先容荟萃存储之前需要指出一点：固然荟萃号称存储的是 Java 工具，但 实际上并不会真正将 Java 工具放入 Set 荟萃中，只是在 Set 荟萃中保存这些 工具的引用而言。也就是说：Java 荟萃实际上是多个引用变量所构成的荟萃， 这些引用变量指向实际的 Java 工具。

HashMap 的存储实现

当措施试图将多个 key-value 放入 HashMap 中时，以如下代码片断为例：

HashMap<String　,　Double>　map　=　new　 HashMap<String　,　Double>();
map.put("语文"　,　80.0);
map.put("数学"　,　89.0);
map.put("英语"　,　78.2);

HashMap 回收一种所谓的“Hash 算法”来抉择每个元素的存储位置。

当措施执行 map.put("语文" , 80.0); 时，系统将挪用"语文"的 hashCode () 要领获得其 hashCode 值——每个 Java 工具都有 hashCode() 要领，都可 通过该要领得到它的 hashCode 值。获得这个工具的 hashCode 值之后，系统会 按照该 hashCode 值来抉择该元素的存储位置。

我们可以看 HashMap 类的 put(K key , V value) 要领的源代码：

public　V　put(K　key,　V　value)
{
//　假如　key　为　null，挪用　putForNullKey　要领举办处理惩罚
if　(key　==　null)
return　putForNullKey(value);
//　按照　key　的　keyCode　计较　Hash　值
int　hash　=　hash(key.hashCode());
//　搜索指定　hash　值在对应　table　中的索引　
int　i　=　indexFor(hash,　table.length);
//　假如　i　索引处的　Entry　不为　null，通过轮回不绝遍历　e　元 素的下一个元素
for　(Entry<K,V>　e　=　table[i];　e　!=　null;　e　=　 e.next)
{
Object　k;
//　找到指定　key　与需要放入的　key　相等（hash　值沟通
//　通过　equals　较量放回　true）
if　(e.hash　==　hash　&&　((k　=　e.key)　==　key
||　key.equals(k)))
{
V　oldValue　=　e.value;
e.value　=　value;
e.recordAccess(this);
return　oldValue;
}
}
//　假如　i　索引处的　Entry　为　null，表白此处还没有　Entry
modCount++;
//　将　key、value　添加到　i　索引处
addEntry(hash,　key,　value,　i);
return　null;
}


#p#副标题#e#

JDK 源码

在 JDK 安装目次下可以找到一个 src.zip 压缩文件，该文件里包括了 Java 基本类库的所有源文件。只要读者有进修乐趣，随时可以打开这份压缩文件来阅 读 Java 类库的源代码，这对提高读者的编程本领长短常有辅佐的。需要指出的 是：src.zip 中包括的源代码并没有包括像上文中的中文注释，这些注释是笔者 本身添加进去的。

上面措施顶用到了一个重要的内部接口：Map.Entry，每个 Map.Entry 其实 就是一个 key-value 对。从上面措施中可以看出：当系统抉择存储 HashMap 中 的 key-value 对时，完全没有思量 Entry 中的 value，仅仅只是按照 key 来 计较并抉择每个 Entry 的存储位置。这也说明白前面的结论：我们完全可以把 Map 荟萃中的 value 当成 key 的隶属，当系统抉择了 key 的存储位置之后， value 随之生存在哪里即可。

上面要领提供了一个按照 hashCode() 返回值来计较 Hash 码的要领：hash ()，这个要领是一个纯粹的数学计较，其要领如下：

static　int　hash(int　h)
{
h　^=　(h　>>>　20)　^　(h　>>>　12);
return　h　^　(h　>>>　7)　^　(h　>>>　 4);
}

对付任意给定的工具，只要它的 hashCode() 返回值沟通，那么措施挪用 hash(int h) 要领所计较获得的 Hash 码值老是沟通的。接下来措施会挪用 indexFor(int h, int length) 要领来计较该工具应该生存在 table 数组的哪 个索引处。indexFor(int h, int length) 要领的代码如下：

static　int　indexFor(int　h,　int　length)
{
return　h　&　(length-1);
}

#p#分页标题#e#

这个要领很是巧妙，它老是通过 h &(table.length -1) 来获得该工具 的生存位置——而 HashMap 底层数组的长度老是 2 的 n 次方，这一点可参看 后头关于 HashMap 结构器的先容。

当 length 老是 2 的倍数时，h & (length-1)将是一个很是巧妙的设计 ：假设 h=5,length=16, 那么 h & length – 1 将获得 5；假如 h=6,length=16, 那么 h & length – 1 将获得 6 ……假如 h=15,length=16, 那么 h & length – 1 将获得 15；可是当 h=16 时 , length=16 时，那么 h & length – 1 将获得 0 了；当 h=17 时 , length=16 时，那么 h & length – 1 将获得 1 了……这样担保计较获得 的索引值老是位于 table 数组的索引之内。

按照上面 put 要领的源代码可以看出，当措施试图将一个 key-value 对放 入 HashMap 中时，措施首先按照该 key 的 hashCode() 返回值抉择该 Entry 的存储位置：假如两个 Entry 的 key 的 hashCode() 返回值沟通，那它们的存 储位置沟通。假如这两个 Entry 的 key 通过 equals 较量返回 true，新添加 Entry 的 value 将包围荟萃华夏有 Entry 的 value，但 key 不会包围。假如 这两个 Entry 的 key 通过 equals 较量返回 false，新添加的 Entry 将与集 合华夏有 Entry 形成 Entry 链，并且新添加的 Entry 位于 Entry 链的头部— —详细说明继承看 addEntry() 要领的说明。

当向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值抉择 该 key-value 对（就是 Entry 工具）的存储位置。当两个 Entry 工具的 key 的 hashCode() 返回值沟通时，将由 key 通过 eqauls() 较量值抉择是回收覆 盖行为（返回 true），照旧发生 Entry 链（返回 false）。

上面措施中还挪用了 addEntry(hash, key, value, i); 代码，个中 addEntry 是 HashMap 提供的一个包会见权限的要领，该要领仅用于添加一个 key-value 对。下面是该要领的代码：

void　addEntry(int　hash,　K　key,　V　value,　int　 bucketIndex)
{
//　获取指定　bucketIndex　索引处的　Entry
Entry<K,V>　e　=　table[bucketIndex];　//　①
//　将新建设的　Entry　放入　bucketIndex　索引处，并让新的　 Entry　指向本来的　Entry
table[bucketIndex]　=　new　Entry<K,V>(hash,　key,　 value,　e);
//　假如　Map　中的　key-value　对的数量高出了极限
if　(size++　>=　threshold)
//　把　table　工具的长度扩充到　2　倍。
resize(2　*　table.length);　//　②
}

上面要领的代码很简朴，但个中包括了一个很是优雅的设计：系统老是将新 添加的 Entry 工具放入 table 数组的 bucketIndex 索引处——假如 bucketIndex 索引处已经有了一个 Entry 工具，那新添加的 Entry 工具指向原 有的 Entry 工具（发生一个 Entry 链），假如 bucketIndex 索引处没有 Entry 工具，也就是上面措施①号代码的 e 变量是 null，也就是新放入的 Entry 工具指向 null，也就是没有发生 Entry 链。

#p#副标题#e#

Hash 算法的机能选项

按照上面代码可以看出，在同一个 bucket 存储 Entry 链的环境下，新放入 的 Entry 老是位于 bucket 中，而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最结尾。

上面措施中尚有这样两个变量：

size：该变量生存了该 HashMap 中所包括的 key-value 对的数量。

threshold：该变量包括了 HashMap 能容纳的 key-value 对的极限，它的值 便是 HashMap 的容量乘以负载因子（load factor）。

从上面措施中②号代码可以看出，当 size++ >= threshold 时，HashMap 会自动挪用 resize 要领扩充 HashMap 的容量。每扩充一次，HashMap 的容量 就增大一倍。

上面措施中利用的 table 其实就是一个普通数组，每个数组都有一个牢靠的 长度，这个数组的长度就是 HashMap 的容量。HashMap 包括如下几个结构器：

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity， 负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指 定的负载因子建设一个 HashMap。

当建设一个 HashMap 时，系统会自动建设一个 table 数组来生存 HashMap 中的 Entry，下面是 HashMap 中一个结构器的代码：

//　以指定初始化容量、负载因子建设　HashMap
public　HashMap(int　initialCapacity,　float　loadFactor)
{
//　初始容量不能为负数
if　(initialCapacity　<　0)
throw　new　IllegalArgumentException(
"Illegal　initial　capacity:　"　+
initialCapacity);
//　假如初始容量大于最大容量，让出示容量
if　(initialCapacity　>　MAXIMUM_CAPACITY)
initialCapacity　=　MAXIMUM_CAPACITY;
//　负载因子必需大于　0　的数值
if　(loadFactor　<=　0　||　Float.isNaN(loadFactor))
throw　new　IllegalArgumentException(
loadFactor);
//　计较出大于　initialCapacity　的最小的　2　的　n　次方值。
int　capacity　=　1;
while　(capacity　<　initialCapacity)
capacity　<<=　1;
this.loadFactor　=　loadFactor;
//　配置容量极限便是容量　*　负载因子
threshold　=　(int)(capacity　*　loadFactor);
//　初始化　table　数组　
table　=　new　Entry[capacity];　//　①
init();
}

#p#分页标题#e#

上面代码中粗体字代码包括了一个简捷的代码实现：找出大于 initialCapacity 的、最小的 2 的 n 次方值，并将其作为 HashMap 的实际容 量（由 capacity 变量生存）。譬喻给定 initialCapacity 为 10，那么该 HashMap 的实际容量就是 16。

#p#副标题#e#

initialCapacity 与 HashTable 的容量

建设 HashMap 时指定的 initialCapacity 并不便是 HashMap 的实际容量， 凡是来说，HashMap 的实际容量总比 initialCapacity 大一些，除非我们指定 的 initialCapacity 参数值刚好是 2 的 n 次方。虽然，把握了 HashMap 容量 分派的常识之后，应该在建设 HashMap 时将 initialCapacity 参数值指定为 2 的 n 次方，这样可以淘汰系统的计较开销。

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

对付 HashMap 及其子类而言，它们回收 Hash 算法来抉择荟萃中元素的存储 位置。当系统开始初始化 HashMap 时，系统会建设一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以按照其索引快速会见该 bucket 里存储的元 素。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry）， 由于 Entry 工具可以包括一个引用变量（就是 Entry 结构器的的最后一个参数 ）用于指向下一个 Entry，因此大概呈现的环境是：HashMap 的 bucket 中只有 一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链 。如图 1 所示：

图 1. HashMap 的存储示意

通过阐发JDK源代码研究Hash存储机制

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;
}

从上面代码中可以看出，假如 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以按照索引、快速地取出该 bucket 里的 Entry；在产生“Hash 斗嘴”的环境下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链 ，系统只能必需按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如 果刚好要搜索的 Entry 位于该 Entry 链的最结尾（该 Entry 是最早放入该 bucket 中），那系统必需轮回到最后才气找到该元素。

归纳起来简朴地说，HashMap 在底层将 key-value 当成一个整体举办处理惩罚， 这个整体就是一个 Entry 工具。HashMap 底层回收一个 Entry[] 数组来生存所 有的 key-value 对，当需要存储一个 Entry 工具时，会按照 Hash 算法来抉择 其存储位置；当需要取出一个 Entry 时，也会按照 Hash 算法找到其存储位置 ，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包括的 Entry，完全雷同于现实糊口中母亲从小教我们的：差异的对象要放在差异的位 置，需要时才气快速找到它。

#p#分页标题#e#

当建设 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是时间和空间本钱上一种折衷：增大负载因子可以淘汰 Hash 表（就是 谁人 Entry 数组）所占用的内存空间，但会增加查询数据的时间开销，而查询 是最频繁的的操纵（HashMap 的 get() 与 put() 要领都要用到查询）；减小负 载因子会提高数据查询的机能，但会增加 Hash 表所占用的内存空间。

把握了上面常识之后，我们可以在建设 HashMap 时按照实际需要适内地调解 load factor 的值；假如措施较量体贴空间开销、内存较量告急，可以适内地增 加负载因子；假如措施较量体贴时间开销，内存较量宽裕则可以适当的淘汰负载 因子。凡是环境下，措施员无需改变负载因子的值。

假如开始就知道 HashMap 会生存多个 key-value 对，可以在建设时就利用 较大的初始化容量，假如 HashMap 中 Entry 的数量一直不会高出极限容量 （capacity * load factor），HashMap 就无需挪用 resize() 要领从头分派 table 数组，从而担保较好的机能。虽然，开始就将初始容量配置太高大概会浪 费空间（系统需要建设一个长度为 capacity 的 Entry 数组），因此建设 HashMap 时初始化容量配置也需要小心看待。

#p#副标题#e#

HashSet 的实现

对付 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层回收 HashMap 来生存所有元素，因此 HashSet 的实现较量简朴，查察 HashSet 的源 代码，可以看到如下代码：

public　class　HashSet<E>
extends　AbstractSet<E>
implements　Set<E>,　Cloneable,　java.io.Serializable
{
//　利用　HashMap　的　key　生存　HashSet　中所有元素
private　transient　HashMap<E,Object>　map;
//　界说一个虚拟的　Object　工具作为　HashMap　的　value
private　static　final　Object　PRESENT　=　new　Object();
...
//　初始化　HashSet，底层会初始化一个　HashMap
public　HashSet()
{
map　=　new　HashMap<E,Object>();
}
//　以指定的　initialCapacity、loadFactor　建设　HashSet
//　其实就是以相应的参数建设　HashMap
public　HashSet(int　initialCapacity,　float　loadFactor)
{
map　=　new　HashMap<E,Object>(initialCapacity,　 loadFactor);
}
public　HashSet(int　initialCapacity)
{
map　=　new　HashMap<E,Object>(initialCapacity);
}
HashSet(int　initialCapacity,　float　loadFactor,　boolean　 dummy)
{
map　=　new　LinkedHashMap<E,Object>(initialCapacity
,　loadFactor);
}
//　挪用　map　的　keySet　来返回所有的　key
public　Iterator<E>　iterator()
{
return　map.keySet().iterator();
}
//　挪用　HashMap　的　size()　要领返回　Entry　的数量，就获得该 　Set　里元素的个数
public　int　size()
{
return　map.size();
}
//　挪用　HashMap　的　isEmpty()　判定该　HashSet　是否为空，
//　当　HashMap　为空时，对应的　HashSet　也为空
public　boolean　isEmpty()
{
return　map.isEmpty();
}
//　挪用　HashMap　的　containsKey　判定是否包括指定　key
//HashSet　的所有元素就是通过　HashMap　的　key　来生存的
public　boolean　contains(Object　o)
{
return　map.containsKey(o);
}
//　将指定元素放入　HashSet　中，也就是将该元素作为　key　放入　 HashMap
public　boolean　add(E　e)
{
return　map.put(e,　PRESENT)　==　null;
}
//　挪用　HashMap　的　remove　要领删除指定　Entry，也就删除了　 HashSet　中对应的元素
public　boolean　remove(Object　o)
{
return　map.remove(o)==PRESENT;
}
//　挪用　Map　的　clear　要领清空所有　Entry，也就清空了　 HashSet　中所有元素
public　void　clear()
{
map.clear();
}
...
}

由上面源措施可以看出，HashSet 的实现其实很是简朴，它只是封装了一个 HashMap 工具来存储所有的荟萃元素，所有放入 HashSet 中的荟萃元素实际上 由 HashMap 的 key 来生存，而 HashMap 的 value 则存储了一个 PRESENT，它 是一个静态的 Object 工具。

HashSet 的绝大部门要领都是通过挪用 HashMap 的要领来实现的，因此 HashSet 和 HashMap 两个荟萃在实现本质上是沟通的。

#p#副标题#e#

HashMap 的 put 与 HashSet 的 add

由于 HashSet 的 add() 要领添加荟萃元素时实际上转变为挪用 HashMap 的 put() 要领来添加 key-value 对，当新放入 HashMap 的 Entry 中 key 与荟萃 华夏有 Entry 的 key 沟通（hashCode() 返回值相等，通过 equals 较量也返 回 true），新添加的 Entry 的 value 将包围本来 Entry 的 value，但 key 不会有任何改变，因此假如向 HashSet 中添加一个已经存在的元素，新添加的 荟萃元素（底层由 HashMap 的 key 生存）不会包围已有的荟萃元素。

把握上面理论常识之后，接下来看一个示例措施，测试一下本身是否真正掌 握了 HashMap 和 HashSet 荟萃的成果。

#p#分页标题#e#

class　Name
{
private　String　first;
private　String　last;

public　Name(String　first,　String　last)
{
this.first　=　first;
this.last　=　last;
}

public　boolean　equals(Object　o)
{
if　(this　==　o)
{
return　true;
}

if　(o.getClass()　==　Name.class)
{
Name　n　=　(Name)o;
return　n.first.equals(first)
&&　n.last.equals(last);
}
return　false;
}
}

public　class　HashSetTest
{
public　static　void　main(String[]　args)
{
Set<Name>　s　=　new　HashSet<Name>();
s.add(new　Name("abc",　"123"));
System.out.println(
s.contains(new　Name("abc",　"123")));
}
}

上面措施中向 HashSet 里添加了一个 new Name("abc", "123") 工具之后， 当即通过措施判定该 HashSet 是否包括一个 new Name("abc", "123") 工具。 粗看上去，很容易觉得该措施会输出 true。

实际运行上面措施将看到措施输出 false，这是因为 HashSet 判定两个工具 相等的尺度除了要求通过 equals() 要领较量返回 true 之外，还要求两个工具 的 hashCode() 返回值相等。而上面措施没有重写 Name 类的 hashCode() 要领 ，两个 Name 工具的 hashCode() 返回值并不沟通，因此 HashSet 会把它们当 成 2 个工具处理惩罚，因此措施返回 false。

由此可见，当我们试图把某个类的工具当成 HashMap 的 key，或试图将这个 类的工具放入 HashSet 中生存时，重写该类的 equals(Object obj) 要领和 hashCode() 要领很重要，并且这两个要领的返回值必需保持一致：当该类的两 个的 hashCode() 返回值沟通时，它们通过 equals() 要领较量也应该返回 true。凡是来说，所有参加计较 hashCode() 返回值的要害属性，都应该用于作 为 equals() 较量的尺度。

#p#副标题#e#

hashCode() 和 equals()

关于如何正确地重写某个类的 hashCode() 要领和 equals() 要领，请参考 猖獗 Java 体系的《猖獗 Java 教材》一书中相关内容。

如下措施就正确重写了 Name 类的 hashCode() 和 equals() 要领，措施如 下：

class　Name
{
private　String　first;
private　String　last;
public　Name(String　first,　String　last)
{
this.first　=　first;
this.last　=　last;
}
//　按照　first　判定两个　Name　是否相等
public　boolean　equals(Object　o)
{
if　(this　==　o)
{
return　true;
}
if　(o.getClass()　==　Name.class)
{
Name　n　=　(Name)o;
return　n.first.equals(first);
}
return　false;
}

//　按照　first　计较　Name　工具的　hashCode()　返回值
public　int　hashCode()
{
return　first.hashCode();
}

public　String　toString()
{
return　"Name[first="　+　first　+　",　last="　+　last　+ 　"]";
}
}

public　class　HashSetTest2　
{
public　static　void　main(String[]　args)
{
HashSet<Name>　set　=　new　HashSet<Name> ();
set.add(new　Name("abc"　,　"123"));
set.add(new　Name("abc"　,　"456"));
System.out.println(set);
}
}

上面措施中提供了一个 Name 类，该 Name 类重写了 equals() 和 toString() 两个要领，这两个要领都是按照 Name 类的 first 实例变量来判定 的，当两个 Name 工具的 first 实例变量相等时，这两个 Name 工具的 hashCode() 返回值也沟通，通过 equals() 较量也会返回 true。

措施主要领先将第一个 Name 工具添加到 HashSet 中，该 Name 工具的 first 实例变量值为"abc"，接着措施再次试图将一个 first 为"abc"的 Name 工具添加到 HashSet 中，很明明，此时没法将新的 Name 工具添加到该 HashSet 中，因为此处试图添加的 Name 工具的 first 也是" abc"，HashSet 会判定此处新增的 Name 工具与原有的 Name 工具沟通，因此无法添加进入，程 序在①号代码处输出 set 集适时将看到该荟萃里只包括一个 Name 工具，就是 第一个、last 为"123"的 Name 工具。

    关键字：

在线提交作业