HashMap设计原理和实现分析.docx
《HashMap设计原理和实现分析.docx》由会员分享，可在线阅读，更多相关《HashMap设计原理和实现分析.docx（24页珍藏版）》请在冰点文库上搜索。
HashMap设计原理和实现分析
HashMap在Java开发中有着非常重要的角色地位，每一个Java程序员都应该了解HashMap。
本文主要从源码角度来解析HashMap的设计思路，并且详细地阐述HashMap中的几个概念，并深入探讨HashMap的内部结构和实现细节，讨论HashMap的性能问题，并且在文中贯穿着一些关于HashMap常见问题的讨论。
读完本文，你会了解到：
1.HashMap的设计思路和内部结构组成
2.HashMap中的一些概念：
什么是阀值？
为什么会有阀值？
什么是加载因子？
它们有什么作用？
3.HashMap的性能问题以及使用事项
4.HashMap的源码实现解析
5.为什么JDK建议我们重写Object.equals（Objectobj）方法时，需要保证对象可以返回相同的hashcode值？
1.HashMap设计思路以及内部结构组成
HashMap设计思路
Map是一种以键值对存储数据的容器，而HashMap则是借助了键值Key的hashcode值来组织存储，使得可以非常快速和高效地地根据键值key进行数据的存取。
对于键值对，HashMap内部会将其封装成一个对应的Entry对象，即Entry对象是键值对的组织形式；
对于每个对象而言，JVM都会为其生成一个hashcode值。
HashMap在存储键值对Entry的时候，会根据Key的hashcode值，以某种映射关系，决定应当将这对键值对Entry存储在HashMap中的什么位置上；
当通过Key值取数据的时候，然后根据Key值的hashcode，以及内部映射条件，直接定位到Key对应的Value值存放在什么位置，可以非常高效地将Value值取出。
为了实现上述的设计思路，在HashMap内部，采用了数组+链表的形式来组织键值对Entry。
HashMap内部维护了一个Entry[]table 数组，当我们使用 newHashMap（）创建一个HashMap时，Entry[]table 的默认长度为16。
Entry[]table的长度又被称为这个HashMap的容量（capacity）；
对于Entry[]table的每一个元素而言，或为null，或为由若干个Entry组成的链表。
HashMap中Entry的数目被称为HashMap的大小（size）;
Entry[]table中的某一个元素及其对应的Entry又被称为桶（bucket）;
其结构如下图所示：
HashMap内部组织结构由上图所示，现在来看一下HashMap的基本工作流程：
2.什么是阀值？
为什么会有阀值？
什么是加载因子？
它们有什么作用？
HashMap设计的初衷，是为了尽可能地迅速根据Key的hashCode值,直接就可以定位到对应的Entry对象，然后得到Value。
请读者考虑这样一个问题：
当我们使用 HashMapmap=newHashMap（）语句时，我们会创建一个HashMap对象，它内部的 Entry[]table的大小为 16，我们假定Entry[]table的大小会改变。
现在，我们现在向它添加160对Key值完全不同的键值对，那么，该HashMap内部有可能下面这种情况：
即对于每一个桶中的由Entry组成的链表的长度会非常地长！
我们知道，对于查找链表操作的时间复杂度是很高的，为O（n）。
这样的一个HashMap的性能会很低很低，如下图所示：
现在再来分析一下这个问题，当前的HashMap能够实现：
1.根据Key的hashCode，可以直接定位到存储这个Entry的桶所在的位置，这个时间的复杂度为O
（1）；
2.在桶中查找对应的Entry对象节点，需要遍历这个桶的Entry链表，时间复杂度为O（n）;
那么，现在，我们应该尽可能地将第2个问题的时间复杂度o（n）降到最低，读者现在是不是有想法了：
我们应该要求桶中的链表的长度越短越好！
桶中链表的长度越短，所消耗的查找时间就越低，最好就是一个桶中就一个Entry对象节点就好了！
这样一来，桶中的Entry对象节点要求尽可能第少，这就要求，HashMap中的桶的数量要多了。
我们知道，HashMap的桶数目，即Entry[]table数组的长度，由于数组是内存中连续的存储单元，它的空间代价是很大的，但是它的随机存取的速度是Java集合中最快的。
我们增大桶的数量，而减少Entry链表的长度，来提高从HashMap中读取数据的速度。
这是典型的拿空间换时间的策略。
但是我们不能刚开始就给HashMap分配过多的桶（即Entry[]table数组起始不能太大），这是因为数组是连续的内存空间，它的创建代价很大，况且我们不能确定给HashMap分配这么大的空间，它实际到底能够用多少，为了解决这一个问题，HashMap采用了根据实际的情况，动态地分配桶的数量。
HashMap的权衡策略
要动态分配桶的数量，这就要求要有一个权衡的策略了，HashMap的权衡策略是这样的：
如果
HashMap的大小> HashMap的容量（即Entry[]table的大小）*加载因子（经验值0.75）
则
HashMap中的Entry[]table的容量扩充为当前的一倍；
然后重新将以前桶中的Entry链表重新分配到各个桶中
上述的 HashMap的容量（即Entry[]table的大小）*加载因子（经验值0.75）就是所谓的阀值（threshold）：
最后，请读者看一个实例：
默认创建的HashMapmap=newHashMap（）;map的容量是 16，那么，当我们往 map中添加第几个完全不同的键值对时，HashMap的容量会扩充呢？
呵呵，很简单的计算：
由于默认的加载因子是0.75 ，那么，此时map的阀值是 16*0.75=12，即添加第13 个键值对的时候，map的容量会扩充一倍。
这时候读者可能会有疑问：
本来Entry[]table的容量是16，当放入12个键值对后，不是至少还剩下4个Entry[]table 元素没有被使用到吗？
这不是浪费了宝贵的空间了吗？
！
确实如此，但是为了尽可能第减少桶中的Entry链表的长度，以提高HashMap的存取性能，确定的这个经验值。
如果读者你对存取效率要求的不是太高，想省点空间的话，你可以newHashMap（intinitialCapacity,floatloadFactor）构造方法将这个因子设置得大一些也无妨。
2.HashMap的算法实现解析
HashMap的算法实现最重要的两个是put（）和get（）两个方法，下面我将分析这两个方法：
[java] viewplain copy
print?
1.public V put（K key, V value）;
2.public V get（Object key）;
另外，HashMap支持Key值为null的情况，我也将详细地讨论这个问题。
1.向HashMap中存储一对键值对流程---put（）方法实现：
put（）方法-向HashMap存储键值对
a. 获取这个Key的hashcode值，根据此值确定应该将这一对键值对存放在哪一个桶中，即确定要存放桶的索引；
b. 遍历所在桶中的Entry链表，查找其中是否已经有了以Key值为Key存储的Entry对象，
c1.若已存在，定位到对应的Entry,其中的Value值更新为新的Value值；返回旧值；
c2.若不存在，则根据键值对创建一个新的Entry对象，然后添加到这个桶的Entry链表的头部。
d. 当前的HashMap的大小（即Entry节点的数目）是否超过了阀值，若超过了阀值（threshold），则增大HashMap的容量（即Entry[]table的大小），并且重新组织内部各个Entry排列。
详细流程如下列的代码所示：
[java] viewplain copy
print?
1./**
2. * 将键值对存到HashMap中，如果Key在HashMap中已经存在，那么最终返回被替换掉的Value值。
3. * Key 和Value允许为空
4. */
5.public V put（K key, V value） {
6.
7. //1.如果key为null，那么将此value放置到table[0],即第一个桶中
8. if （key == null）
9. return putForNullKey（value）;
10. //2.重新计算hashcode值，
11. int hash = hash（key.hashCode（））;
12. //3.计算当前hashcode值应当被分配到哪一个桶中，获取桶的索引
13. int i = indexFor（hash, table.length）;
14. //4.循环遍历该桶中的Entry列表
15. for （Entry e = table[i]; e !
= null; e = e.next） {
16. Object k;
17. //5. 查找Entry链表中是否已经有了以Key值为Key存储的Entry对象,
18. //已经存在,则将Value值覆盖到对应的Entry对象节点上
19. if （e.hash == hash && （（k = e.key） == key || key.equals（k））） {//请读者注意这个判定条件，非常重要！
！
！
20. V oldValue = e.value;
21. e.value = value;
22. e.recordAccess（this）;
23. return oldValue;
24. }
25. }
26. modCount++;
27. //6不存在，则根据键值对 创建一个新的Entry对象，然后添加到这个桶的Entry链表的头部。
28. addEntry（hash, key, value, i）;
29. return null;
30.}
31.
32./**
33. * Key 为null,则将Entry放置到第一桶table[0]中
34. */
35.private V putForNullKey（V value） {
36. for （Entry e = table[0]; e !
= null; e = e.next） {
37. if （e.key == null） {
38. V oldValue = e.value;
39. e.value = value;
40. e.recordAccess（this）;
41. return oldValue;
42. }
43. }
44. modCount++;
45. addEntry（0, null, value, 0）;
46. return null;
47.}
[java] viewplain copy
print?
1./**
2. * 根据特定的hashcode 重新计算hash值，
3. * 由于JVM生成的的hashcode的低字节（lower bits）冲突概率大，（JDK只是这么一说，至于为什么我也不清楚）
4. * 为了提高性能，HashMap对Key的hashcode再加工，取Key的hashcode的高字节参与运算
5. */
6.static int hash（int h） {
7. // This function ensures that hashCodes that differ only by
8. // constant multiples at each bit position have a bounded
9. // number of collisions （approximately 8 at default load factor）.
10. h ^= （h >>> 20） ^ （h >>> 12）;
11. return h ^ （h >>> 7） ^ （h >>> 4）;
12.}
13.
14./**
15. * 返回此hashcode应当分配到的桶的索引
16. */
17.static int indexFor（int h, int length） {
18. return h & （length-1）;
19.}
当HashMap的大小大于阀值时，HashMap容量的扩充算法当当前的HashMap的大小大于阀值时，HashMap会对此HashMap的容量进行扩充，即对内部的Entry[]table数组进行扩充。
HashMap对容量（Entry[]table数组长度）有两点要求：
1.容量的大小应当是2的N次幂；
2.当容量大小超过阀值时，容量扩充为当前的一倍；
这里第2点很重要,如果当前的HashMap的容量为16，需要扩充时，容量就要变成16*2=32,接着就是32*2=64、64*2=128、128*2=256.........可以看出，容量扩充的大小是呈指数级的级别递增的。
这里容量扩充的操作可以分为以下几个步骤：
1.申请一个新的、大小为当前容量两倍的数组；
2. 将旧数组的Entry[]table中的链表重新计算hash值，然后重新均匀地放置到新的扩充数组中；
3. 释放旧的数组；
由上述的容量扩充的步骤来看，一次容量扩充的代价非常大，所以在容量扩充时，扩充的比例为当前的一倍，这样做是尽量减少容量扩充的次数。
为了提高HashMap的性能：
1.在使用HashMap的过程中，你比较明确它要容纳多少Entry，你应该在创建HashMap的时候直接指定它的容量；
2.如果你确定HashMap的使用的过程中，大小会非常大，那么你应该控制好加载因子的大小，尽量将它设置得大些。
避免Entry[]table过大，而利用率觉很低。
[java] viewplain copy
print?
1./**
2. * Rehashes the contents of this map into a new array with a
3. * larger capacity. This method is called automatically when the
4. * number of keys in this map reaches its threshold.
5. *
6. * If current capacity is MAXIMUM_CAPACITY, this method does not
7. * resize the map, but sets threshold to Integer.MAX_VALUE.
8. * This has the effect of preventing future calls.
9. *
10. * @param newCapacity the new capacity, MUST be a power of two;
11. * must be greater than current capacity unless current
12. * capacity is MAXIMUM_CAPACITY （in which case value
13. * is irrelevant）.
14. */
15.void resize（int newCapacity） {
16. Entry[] oldTable = table;
17. int oldCapacity = oldTable.length;
18. if （oldCapacity == MAXIMUM_CAPACITY） {
19. threshold = Integer.MAX_VALUE;
20. return;
21. }
22.
23. Entry[] newTable = new Entry[newCapacity];
24. transfer（newTable）;
25. table = newTable;
26. threshold = （int）（newCapacity * loadFactor）;
27.}
28.
29./**
30. * Transfers all entries from current table to newTable.
31. */
32.void transfer（Entry[] newTable） {
33. Entry[] src = table;
34. int newCapacity = newTable.length;
35. for （int j = 0; j < src.length; j++） {
36. Entry e = src[j];
37. if （e !
= null） {
38. src[j] = null;
39. do {
40. Entry next = e.next;
41. int i = indexFor（e.hash, newCapacity）;
42. e.next = newTable[i];
43. newTable[i] = e;
44. e = next;
45. } while （e !
= null）;
46. }
47. }
48.}
为什么JDK建议我们重写Object.equals（Objectobj）方法时，需要保证对象可以返回相同的hashcode值？
Java程序员都看过JDK的API文档，该文档关于Object.equals（Objectobj）方法，有这样的描述：
“注意：
当此方法被重写时，通常有必要重写hashCode 方法，以维护hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
”
读者虽然知道这个协定，但是不一定真正知道为什么会有这一个要求，现在，就来看看原因吧。
请读者再注意看一下上述的额put（）方法实现，当遍历某个桶中的Entry链表来查找Entry实例的过程中所使用的判断条件：
[java] viewplain copy
print?
1.for （Entry e = table[i]; e !
= null; e = e.next） {
2. Object k;
3. //5. 查找Entry链表中是否已经有了以Key值为Key存储的Entry对象,
4. //已经存在,则将Value值覆盖到对应的Entry对象节点上
5. if （e.hash == hash && （（k = e.key） == key || key.equals（k））） {
6. V oldValue = e.value;
7. e.value = value;
8. e.recordAccess（this）;
9. return oldValue;
10. }
11. }
对于给定的Key,Value，判断该Key是否与Entry链表中有某一个Entry对象的Key值相等
升级会员 