深入理解HashMap(二): 关键源码逐行分析之hash算法

chunquedong 发布于2019-08-19 10:50 / 2114人阅读

摘要：散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值，，，或的指纹。

前言

系列文章目录

前面我们讨论了HashMap的结构, 接下来几篇我们从源码角度来看HashMap的实现细节.

本篇我们就来聊聊HashMap的hash算法

本文的源码基于 jdk8 版本.

hash算法

上一篇文章我们提到, 为了利用数组索引进行快速查找, 我们需要先将 key值映射成数组下标. 因为数组的下标是有限的集合, 所以我们可以先通过hash算法将key映射成整数, 再将整数映射成有限的数组下标:

Object -> int -> index

对于 Object -> int 部分, 使用的就是hash function, 而对于 int -> index 部分, 我们可以简单的使用对数组大小取模来实现.

下面我们就来看看HashMap使用了什么hash算法.

首先我们来看维基百科对于hash function的定义:

散列函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或hashes）的指纹。

在java中, hash函数是一个native方法, 这个定义在Object类中, 所以所有的对象都会继承.

public native int hashCode();

因为这是一个本地方法, 所以我们无法看到它的具体实现, 但是从函数签名上可以看出, 该方法将任意对象映射成一个整型值.调用该方法, 我们就完成了 Object -> int的映射

所以将 key映射成index 的方式可以是

key.hashCode() % table.length

那么HashMap是这样做的吗? 事实上, HashMap定义了自己的散列方法:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

我们知道, int类型是32位的, h ^ h >>> 16 其实就是将hashCode的高16位和低16位进行异或, 这充分利用了高半位和低半位的信息, 对低位进行了扰动, 目的是为了使该hashCode映射成数组下标时可以更均匀, 详细的解释可以参考这里.

另外, 从这个函数中, 我们还可以得到一个意外收获:

HashMap中key值可以为null, 且null值一定存储在数组的第一个位置.

性能提升

前面我们提到, 将hash值转换成数组下标我们可以采用取模运算, 但是取模运算是十分耗时的.

另一方面, 我们知道, 当一个数是 2^n 时, 任意整数对2^n取模等效于:

h % 2^n = h & (2^n -1)

这样我们就将取模操作转换成了位操作, 而位操作的速度远远快于取模操作.

为此, HashMap中, table的大小都是2的n次方, 即使你在构造函数中指定了table的大小, HashMap也会将该值扩大为距离它最近的2的整数次幂的值. 这在我们下面分析构造函数的时候就能看到了.

(完)

下一篇 : 深入理解HashMap(三): 关键源码逐行分析之构造函数

查看更多系列文章：系列文章目录

海外云主机 GPU服务器深入理解webrtc之aec 深入理解系列深入理解linux 深入理解webrtc

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76538.html

系列文章目录

摘要：为了避免一篇文章的篇幅过长，于是一些比较大的主题就都分成几篇来讲了，这篇文章是笔者所有文章的目录，将会持续更新，以给大家一个查看系列文章的入口。前言大家好，笔者是今年才开始写博客的，写作的初衷主要是想记录和分享自己的学习经历。因为写作的时候发现，为了弄懂一个知识，不得不先去了解另外一些知识，这样以来，为了说明一个问题，就要把一系列知识都了解一遍，写出来的文章就特别长。为了避免一篇...

lijy91 2019-06-28 16:36 评论0 收藏0
系列文章目录

摘要：为了避免一篇文章的篇幅过长，于是一些比较大的主题就都分成几篇来讲了，这篇文章是笔者所有文章的目录，将会持续更新，以给大家一个查看系列文章的入口。前言大家好，笔者是今年才开始写博客的，写作的初衷主要是想记录和分享自己的学习经历。因为写作的时候发现，为了弄懂一个知识，不得不先去了解另外一些知识，这样以来，为了说明一个问题，就要把一系列知识都了解一遍，写出来的文章就特别长。为了避免一篇...

Yumenokanata 2019-08-19 10:58 评论0 收藏0
深入理解HashMap(三): 关键源码逐行分析之构造函数

摘要：前言系列文章目录上一篇我们说明了的算法说到在构造时会自动将设为的整数次幂本篇我们就来聊聊的构造函数本文的源码基于版本构造函数共有四个构造函数默认初始大小默认负载因子没有指定时使用默认值即默认初始大小默认负载因子指定初始大小但使用默认负载因子前言系列文章目录上一篇我们说明了HashMap的hash算法, 说到HashMap在构造时会自动将table设为2的整数次幂. 本篇我们就来聊...

QiuyueZhong 2019-08-19 10:50 评论0 收藏0
深入理解HashMap(五): 关键源码逐行分析之put

摘要：当链表长度超过默认是个时，会将链表转换成红黑树以提升查找性能。前言系列文章目录上一篇我们讨论了HashMap的扩容操作, 提到扩容操作发生在table的初始化或者table大小超过threshold后，而这两个条件的触发基本上就发生在put操作中。本篇我们就来聊聊HashMap的put操作。本文的源码基于 jdk8 版本. put方法 HashMap 实现了Map接口, 因此...

APICloud 2019-08-19 10:51 评论0 收藏0
深入理解HashMap(四): 关键源码逐行分析之resize扩容

摘要：前言系列文章目录上一篇我们说明了的构造函数谈到构造函数中并不会初始化变量变量是在过程中初始化的本篇我们就来聊聊的扩容本文的源码基于版本用于以下两种情况之一初始化在大小超过之后进行扩容下面我们直接来对照源码分析原中已经有值已经超过最大限制不再前言系列文章目录上一篇我们说明了HashMap的构造函数, 谈到构造函数中并不会初始化table 变量, table 变量是在 resize过...

aristark 2019-08-19 10:50 评论0 收藏0