HashMap解读
相信大家对HashMap都非常熟悉, 网上也有很多关于hashmap的源码解析, 此文仅记录本人对HashMap的理解. 若描述或者观点有误, 请指出, 感谢.
为什么学习HashMap源码?
就是因为想学而已, 想感受HashMap的魅力, 明白理论上O(1)时间复杂度的实现.
我个人认为搞明白底层的实现, 可以更加游刃有余地使用HashMap.
在学习HashMap前, 我们先了解一下一些基础概念.
Hash算法
哈希算法又叫做散列算法, 是将任意长度的二进制值映射为较短的固定长度的二进制值, 这个小的二进制值称为哈希值. 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数.
这里我们不深入了解, 只需要知道Object类中有一个hashcode(), 该方法是一个本地接口方法, 所以其内部实现其实是由C/C++ 语言实现的, 被编译成DLL, 由java调用, 所以我们也不必深究其底层实现方式感兴趣的同学可以自行翻看openJDK深入了解.
所以其实我们只需知道, 由于hashcode()是Object类的方法,一个任意对象都有这个方法, 而调用该方法可以得到一个hash值, 该值为一个32位整数(32位指32个二进制位, 也就是一个int数, 并非32位的十进制数).
Hash冲突
如果大家看明白了上面的这个hash内容, 相信会有这么一个疑惑, 既然所有的对象都可以调用这个hashcode, 而对象千千万, 这个值又只是一个int, 有范围所以不可能所有的对象得到的不同的值, 那么就会出现不同的对象进行hashcode时得到了相同的值. 这就是hash冲突.
位运算
由于hashmap的设计者考虑到位运算效率高于普通算符运算, 所以在hashmap中大量使用位运算符进行运算操作.
相信有一定计算机基础的同学应该对位运算不陌生, 但这里还是提一下. 程序中的所有数在计算机内存中都是以二进制的形式储存的. 位运算就是直接对整数在内存中的二进制位进行操作. 这里就稍微将概念解释一下, 具体的运算以及在java中的运算符希望大家可以自行了解一下.
使用与运算对2的幂次方取模
位运算(&)效率要比代替取模运算(%)高很多, 主要原因是位运算直接对内存数据进行操作, 不需要转成十进制, 因此处理速度非常快.
那么, 如何使用(&)与运算来实现(%)取模运算呢?
其实非常简单, 举个例子:
如果你想将x对y进行取模, 如果是普通的取模运算, 则写成: x % y 而使用了(&)进行运算, 则可以写成x & (y-1)
听起来非常美好, 更换一个运算符则可以大大提高取模的效率, 但其实这是有条件的, 仅当y为2的幂次方才可以进行此操作. 这就是为什么hashmap的容量, 会将数组长度强行定义为2的幂次方的原因(比如你构造时入参传的是7, 也会定义为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的数据结构
在JDK7版本中, HashMap的数据结构为: 数组 + 链表
在JDK8版本中, HashMap的数据结构为: 数组 + 链表 + 红黑树
JDK7中使用的数组+链表, 当最坏的情况出现, 若持续出现hash碰撞 (当然这是指极端情况) , 则表的存储为链表形式, 查询时速度达到O(n).而JDK8中, 使用红黑树来代替长链表. 如果链表长度大于8时, 则将该链表转换为红黑树, 则查询时时间复杂度降低至O(log n).
个人认为这是一个大的优化, 本文仅针对JDK8的HashMap进行讨论.
下图为HashMap(JDK1.8)的数据结构. (图片来源于网络, 侵删)
JDK8中HashMap的数据结构
HashMap的宏观结构
下面我想通过代码, 图片和文字结合的形式将HashMap的宏观结构描述一下, 让大家对它有个大致的认识.或许画的图不够好看, 请大家见谅.
这里只展示对hashmap的操作中, hashmap的内容, 而对于jvm的内存结构, 如堆栈方法区等都不具体画出.
当执行一个put方法时, hashmap如何存值?
// 创建一个初始容量为8的hahsmap
HashMap hashMap = new HashMap(8);
// 对其进行存值操作
hashMap.put("key00", "value00");
图片展示其过程:
空hashmap存值.png
具体描述:
当调用上述代码中的put方法时, hashmap会对字符串"key00"进行hash运算, hash运算的过程是: 先将"key00"调用hashcode方法, "key00".hashCode()得到一个int值, 然后hashmap会将该值与其高16位异或.
计算出了对象"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的元素中.
今天先到这里了. 后续再更新进行hash冲突存值的讨论.
