HashMap解读

相信大家对HashMap都非常熟悉, 网上也有很多关于HashMap的源码解析, 此文仅记录本人对HashMap的理解. 若描述或者观点有误, 请指出, 感谢.

为什么学习HashMap源码?

就是因为想学而已, 想感受HashMap的魅力, 明白理论上O(1)时间复杂度的实现.

我个人认为搞明白底层的实现, 可以更加游刃有余地使用HashMap.

在深入学习HashMap之前, 我们先了解一下它的数据结构, 让大家对它有个感性的认识.

HashMap的数据结构

在JDK7中, HashMap的数据结构为: 数组 + 链表
在JDK8中, HashMap的数据结构为: 数组 + 链表 + 红黑树

JDK7中使用的数组+链表, 当最坏的情况出现, 若持续出现hash碰撞 (当然这是指极端情况) , 则表的存储为链表形式, 查询时速度达到O(n). 而JDK8中, 使用红黑树来代替链表. 如果链表长度大于8时, 则将该链表转换为红黑树, 则查询时时间复杂度降低至O(log n).

个人认为这是一个非常大的优化, 本文仅针对JDK8的HashMap进行讨论.

下图为HashMap(JDK1.8)的数据结构. (图片来源于网络, 侵删)

JDK8中HashMap的数据结构

说不定这个数据结构示意图已经见过n次了, 但就是还没明白啥意思, 怎么一个集合还三种数据结构的? 怎么实现的? 这样设计有啥好处?

不急, 咱们接下来就一点点剖析它到底是怎么一回事. 在这之前我们需要了解一些基本的概念, 大家可以对这些概念先大致过一遍, 如果已经了解过可以跳过.

Hash算法

哈希算法又叫做散列算法, 是将任意长度的二进制值映射为较短的固定长度的二进制值, 这个小的二进制值称为哈希值. 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数.

这里我们不深入了解, 只需要知道Object类中有一个hashcode(), 该方法是一个本地接口方法, 所以其内部实现其实是由C/C++ 语言实现的, 被编译成DLL, 由java调用, 所以我们也不必深究其底层实现方式, 感兴趣的同学可以自行翻看openJDK深入了解.

所以其实我们只需知道, 由于hashcode()是Object类的方法,一个任意对象都有这个方法, 而调用该方法可以得到一个hash值, 该值为一个32位整数(32位指32个二进制位, 也就是一个int数, 并非32位的十进制数).

Hash冲突

如果大家看明白了上面的这个hash算法的内容, 相信会有这么一个疑惑, 既然所有的对象都可以调用这个hashcode(), 而对象千千万, 这个值又只是一个int, 有范围所以不可能所有的对象得到的不同的值, 那么就会出现不同的对象进行hashcode()时得到了相同的值. 这就是hash冲突.

既然进行hash运算过程中可能会出现hash冲突, 那出现这种情况的时候hashmap如何解决这个问题呢? 从上文中可知道hashmap采用的是链地址法. (其它解决hash冲突方式就不过多介绍了, 有兴趣查阅相关资料)

位运算

由于hashmap的设计者考虑到位运算效率高于普通算符运算, 所以在hashmap中大量使用位运算符进行运算操作.

相信有一定计算机基础的同学应该对位运算不陌生, 但这里还是提一下. 程序中的所有数在计算机内存中都是以二进制的形式储存的. 位运算就是直接对整数在内存中的二进制位进行操作. 这里就稍微将概念解释一下, 具体的运算以及在java中的运算符希望大家可以自行了解一下.

使用与运算对2的幂次方取模

位运算(&)效率要比代替取模运算(%)高很多, 主要原因是位运算直接对内存数据进行操作, 不需要转成十进制, 因此处理速度非常快.

那么, 如何使用(&)与运算来实现(%)取模运算呢?
其实非常简单, 举个例子:
如果你想将x对y进行取模, 如果是普通的取模运算, 则写成: x % y 而使用了(&)进行运算, 则可以写成x & (y-1)

听起来非常美好, 更换一个运算符则可以大大提高取模的效率, 但其实这是有条件的, 仅当y为2的幂次方才可以进行此操作. 这就是为什么hashmap的容量, 会将数组长度强行定义为2的幂次方的原因(比如你构造时入参传的是7, 也会定义为8, 也就是2^3, 又或者构造时入参是36, 会被定义成64...), 为了完美使用最高效的取模运算

这里我举几个证明&运算代替%运算的例子吧(一定要注意, 模的是2的幂次方才有这样的效果)

// example1
5 % 8 = 5
5 & (8-1) = 5
---------------
5:  0101
7:  0111
---------------
    0101

0b0101 == 5
// example2
77 % 32 = 13
77 & (32-1) = 13
---------------
77:  01001101
31:  00011111
---------------
     00001101
 
0b1101 == 13

HashMap简要介绍

下面我想通过代码, 图片和文字结合的形式将HashMap描述一下, 让大家对它有个更为全面的认识.或许画的图不够好看, 请大家见谅.

这里只展示对hashmap的操作中, hashmap的内容, 而对于jvm的内存结构, 如堆栈方法区等都不具体画出.

当执行一个put方法时, hashmap如何存值?(无hash冲突的第一次存值情况)

// 创建一个初始容量为8的hahsmap
HashMap hashMap = new HashMap(8);
// 对其进行第一次存值操作
hashMap.put("key00", "value00");

图片展示其过程:

空hashmap存值.png

计算出了对象"key00"的hash值, 其对应的十进制值为203787916.得到了hash值后, hashmap需要将该值放置到数组的对应元素中, 而我们定义的hashmap初始容量为8, 这时候就需要将203787916对8进行取模运算, 得到的值则为hashmap中数组对应的下标4.

也就是如下运算:

h = "key00".hashCode();                 // 亲测该字符串进行hashcode后, 值为101943455, 也就是该步骤为: h = 101943455
                   h :     0000011000010011 1000100010011111
            (h>>>16) :     0000000000000000 0000011000010011
---------------------------------------------------------------
 hash = h ^ (h>>>16) :     0000011000010011 1000111010001100
        hash & (n-1) :     0000000000000000 0000000000000111
---------------------------------------------------------------
                           0000000000000000 0000000000000100
0b100 == 4

计算出了下标4后, 将键值对存放到数组下标为4的元素中.

当执行一个put方法时, hashmap如何存值?(假设第二次存值时, key01与之前存的key00出现hash冲突)

// 对其进行第二次存值操作
hashMap.put("key01", "value01");

图片展示其过程:

第二次使用put, key与第一次不一致, 出现冲突

当调用了put方法进行对已经存了一个值的hashmap进行第二次的存值时, "key01"同样进行了hash运算, 这个过程与"key00"的hash运算过程一致, 这里就不再详细描述了, 我们假设这个"key01"与"key00"进行hash运算得到的结果值是一样的(也就是出现了hash冲突), 然后再进行了对8(hashmap容量)的取模, 得到同样的数组下标4.

这时候进行存值时发现了该数组中有元素. 而我们使用过hashmap都知道, 如果我们对同一个key进行了put操作, 新的value会覆盖旧的value, 而如果我们put的key不是同一个, 就不会覆盖已有的key, 而是正常存值.
但是在这样的情况下, 如果不做判断, 我们无法知道, 现在即将存进去的key("key01")是不是已有元素的key, 如果是的话应该进行value的覆盖, 否则将存值. 所以这里使用了equals方法来对这两个key进行比较. 这样就知道该进行什么操作了, 很显然我们这里不是同一个key, 所以将进行存值, 但是数组中有值了, 我们需要将数组的这个位置转换为链表, 将已有的元素Node后继节点指向一个新的Node, 新的key和value存在新的Node中.

这样, 第二次存值时key不一致且出现冲突的情况, 会将数组中的一个元素转变为链表形式.

!注意:以上put方法执行过程暂不不考虑容量的校验(扩容机制)

put方法逻辑就是如此了. 如果一直出现hash碰撞, 碰撞了8次以上, hash中的桶(即数组中的元素)转为链表后, 长度还大于8, 这个链表就会被转换为红黑树的结构(hashmap的红黑树数据结构在JDK8中才有). 不过在hashmap扩容时, 如果发现链表长度小于6, 则会由树重新退化为链表.

扩容机制

我们在学习put的方法的过程中, 模拟了一次hash碰撞, 实际上不刻意假设进行模拟, 也很容易出现碰撞. 相信大家也看到了, 存值时是通过对hashmap的容量进行%运算, 而我设置的容量为8, 那取值范围只会在0~7, 碰撞出现也毫不意外了.
我们可以看到, 如果hashmap容量定义得太小, 出现碰撞的概率真的很大, 当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的).

碰撞几率大的话, 容易把hash的数组结构转为链表结构. 这样对我们put的速度是相当不利的(其实get方法也一样需要这样), 因为链表的话需要一次次进行equals方法一个个比对后决定覆盖还是再存值, 遍历链表的时间复杂度就为O(n)了, 与数组取值O(1)的时间复杂度速度差很多.

所以为了提高效率，就要对hashmap的数组进行扩容.

我们先看看源码中一些常量的定义:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient int size; 
int threshold;

接下来对这些常量依次解释一下:

• DEFAULT_INITIAL_CAPACITY:
  初始容量, 也就是默认会创建16个元素.
• MAXIMUM_CAPACITY:
  哈希表最大容量, 一般情况下只要内存够用, 哈希表不会出现问题。
• DEFAULT_LOAD_FACTOR:
  默认的负载因子. 因此默认情况下, 当键值对的数量大于16 * 0.75 = 12 时, 就会触发扩容.
• size:
  表示当前HashMap包含的键值对数量
• threshold:
  表示当前HashMap能够承受的最多的键值对数量，一旦超过这个数量HashMap就会进行扩容

这些概念性的东西可能看了就头大, 那么我来简述一下重点概念吧.
简要描述:
hashmap什么时候进行扩容?

1. size是已存入的键值对数量. 我们每次存入一个新的键值对就进行增加.
2. 我们可以存的最大键值对数量公式为: 数组容量 * 负载因子 = 最大键值对数量 也就是DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = threshold
3. 如果size > threshold时, 容量(CAPACITY)就扩大两倍.

举个例子:
如果如我上述例子, 执行语句:HashMap hashMap = new HashMap(8);定义一个容量为8的hashmap, 这时DEFAULT_INITIAL_CAPACITY在构造时赋值为8, 而DEFAULT_LOAD_FACTOR默认时为0.75(一般不对负载因子进行修改, 除非有特别的需要, 负载因子可以大于1), 这时threshold的值通过计算可以得到8 * 0.75 = 6, 则我们如果存值存到了第7个, 大于了6个(也就是大于threshold的值)就会触发扩容机制, 新的容量为DEFAULT_INITIAL_CAPACITY * 2. 这时候新的容量newCap为16, 而threshold也随之改变, 为16 * 0.75 = 12, 扩容后, 我们再次进行存值的话, 存到第13个时会再次进行扩容.

说完了扩容机制, 我们为什么要了解扩容机制呢?
我在文章开始的时候就提到了, hashmap是一个理论上可以达到O(1)的时间复杂度的神器, 如果说万物不会是完美的, 那么扩容是hashmap的唯一性能瓶颈了.

扩容时, hashmap会新建一个新的数组, 将所有已存的值进行rehash(再次使用hash算法, 再对新的数组容量取模), rehash之后再次存值. 如果是我这例子里的8个容量扩大到16个容量, 那倒不会耗时太长, 但试想如果是一个容量达到十万, 百万, 甚至千万的hash表进行一次扩容, 大量的hash运算, equals方法的执行, 可以说极为缓慢. 所以我们需要提前考虑需要多大的容量, 避免多次扩容影响性能. (这就是为什么阿里巴巴建议hashmap集合初始化的时候定义容量大小的原因)

那么如何考虑需要多大的初始容量呢?
实际上这没法得到一个准确的答案. 为什么呢? 我模拟一个场景: 假设我们有大概1000个值需要存在hashmap中, 那么我们如果容量设置了1000, 实际上hashmap的容量只允许的2的幂次方, 所以设置1000其实就是设置了1024, 最大可存放键值对是1024 * 0.75 = 768, 这样肯定会出现一次扩容的情况了, 如果我们不希望让他扩容, 一次也不要的话. 那么至少要设置1334个容量, 这样与负载因子相乘就可以得到1000, 刚好可以存到最大值为1000个容量, 我们说过, hashmap的容量只允许的2的幂次方, 所以设置1334其实就是设置的容量为2048, 这样的话, 肯定是不会进行扩容了, 但在没存到1000个键值对时, 内存就浪费了很多. 当然如果实在是希望用空间换取时间的话, 这样无疑是最好的, 不会进行一次扩容, 而且还降低了hash碰撞的概率.

那么扩容机制大体上就是这样了.