彻底搞懂HashMap（上）

一、彻底搞懂HashMap(上)

文章概述：

相信很多朋友对于HashMap，开发中我们几乎每天都要使用它，但是每当问到map的一些原理时，很多朋友就不知道如何去回答，甚至一问三不知，从而离我们心仪的offer越来越远，那么今天借着咱们IT 巡游屋这个平台，和大家分享一下关于map的原理，让大家读完这篇文章后，再也不会因为map而倒在面试的路上

二、什么是哈希

• 什么是哈希

翻译成 “散列” ，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值，这个映射函数叫做散列函数，存放记录的数组叫做散列表。

相信读完这个概念后，大家一定是一脸茫然的，来，这就给各位读者老爷解释：

解释一:什么是哈希

假设，我们有10个抽屉，我们恰好也有10个有编号随机 的苹果，假设每个抽屉只能放一个苹果，那么恰好10 个苹果就可以放在10个抽屉里边去，当然这个顺序我们是随机放的,现在苹果已经放进去了，假设我们想找6号苹果，我们就得打开一个一个的抽屉，去看抽屉里边的苹果是不是编号6 ，这样做很有可能会在最后一个抽屉才找到我们想要的苹果，这样去查找一个数据无疑会很慢，所以，我们就想能不能给他加下速呢，当然可以，用咱们的哈希算法，我现在就建立起来一个 方法

抽屉的位置 =int index = fn(编号){ return 编号 % 抽屉的长度； }

当我在放元素的时候，我就拿着编号的苹果去 % 一下抽屉的长度，那只要你了解%的含义，你就一定知道的意思，我现在就按照得出的这个index 的值放在对应的抽屉里边，找的时候，我也按照这个算法算出来，此时我就能快速的找到苹果了，什么是哈希呢？哈希其实就是我通过那个方法算出来的index ，什么是哈希函数呢？就是我的那个方法。

解释二:什么是完美哈希，什么是哈希冲突，以及如何解决哈希冲突

相信通过上边那个故事，有同学一定想到了这样的问题，我们有10 个抽屉，但是我们有11个苹果，那么我们一定会有一个苹果找不到地方放进去，这个时候呢，多出来这个苹果如果一定要放进抽屉，那么就只能和其他某一个苹果，挤一挤啦，这种情况就称之为哈希冲突，哈希冲突怎么办呢？他有很多种办法，咱们就给同学们介绍map中的方式就好了，叫做链式地址法，也就是会把后来的苹果挂在相同index上，形成一个链表，至于什么是链表我就不多说啦，值得注意的是，1.7的挂法和1.8的挂法并不一样，这个咱们后边再聊

三、map中的哈希算法是怎么回事

前言

我们都知道链表他的遍历效率是很低的，而形成哈希冲突之后，他就得慢慢去遍历链表，效率贼低，所以我们不希望发生哈希冲突，于是我们就得把咱们的哈希算法设计的精妙一些，来避免哈希冲突

map中的哈希算法

以1.8为例

n-1 & (h = key.hashCode()) ^ (h >>> 16) 注意：这个式子就是咱们传说中的哈希算法，得出的结果就是哈希值，并不是咱们同学们认为的hashCode 就是它的哈希值哦

他为何要这么做

如果要明白为何要这么做，我们就得把这两个式子拆开来看，并且对二进制有些基本的了解，现在我们把

(h = key.hashCode()) ^ (h >>> 16) 看成式子一，然后把n-1 看成式子二，n就是数组长度

我们先来看式子一

现在为了能够更好的理解哈希冲突算法，我们把n-1 看成一个常量，也就是说式子一要和一个常量运算，得到的结果要尽可能的不一样，因为如果一样不就发生哈希冲突了，那么我们怎么能让一个数和一个常量计算得到的结果尽可能的不一样呢，那就是参与运算的位数越多，最终计算出来的结果就越不一样，因为 key的hashCode 求出一个32 位长度的二进制数字数字，如果我拿32 位的hashCode 值和 n-1 直接计算，相当于有很多位没有参与到运算，这样就容易产生重复，那为了能让32 位数都尽可能参与到运算，那我只能在32 位 长度的二进制头上来上一刀，再让前边的半截和后边的半截计算一样，综合一下，这样不就尽可能多的参与到运算了吗，这是怎么做到的呢? 我们来看式子

h =(key.hashCode()) ^ (h >>> 16)

假设 key.hashCode 是： 01000111 01010101 10000000 01001010

本来的哈希code 01000111 01010101 10000000 01001010 向右的移动16 00000000 00000000 01000111 01010101 高位补0

这样不就让一个32位的数尽可能的参与运算了吗，但是这样还不够，万一前边的半截和后边的半截算出来结果 出现了很多的0，要么全是1 ，那大家岂不是算出来的值就没有区别，所以，我们应该想个办法让0,1 尽可能的平均，怎么办，用^符号，^符号可以在相同的概率下得到0,1 平均概率最高的一个符号，就好像这样

如果做到了以上两步，那么我就保证两件事情

第一点 32位的变化值 他尽可能的参与到运算

第二点 得到的结果是一个0,1 平均最高的数字

接下来我们来看式子二

式子2 很简单，就是n-1 ，为啥要使用&和式子一计算 ，那又是为啥，接下来我们就来解答这些问题

为什么要用&

问题一为啥要用&、

你有没有想过，万一我通过 一个所谓的哈希算法算出来的index它的值并不在数组索引里，比如，我有10个抽屉的位置，我通过哈希算法算出来的index 是101,那这个元素都跑到天边去了，还怎么放，没法放，所以我们在选用计算符号时，一定要确保 最终计算出来的结果一定 小于索引的，通过计算的式子1，有16 位之多，可以不用考虑，那么也就是说，最终得到的结果一定得小于或者等于 n-1 ，而数组索引从0 开始计算，如果小于或者等于n-1 不就正好满足吗？那&的特性 同1 得1 ，就完全能够解决这个问题

看一下的这个式子

1010 1010 0100 0101 式子1 0111 1111 式子2

0100 0101

如果式子2 固定，那么如果按照同一得1 来计算，最大的值算出来就是0111 1111 ，而式子2是数组长度-1 ，那么得到的结果不就正好是 数组对应的索引最大值吗？

问题二之：数组长度必须是2的n次幂

偶数必然是二进制末尾位是0，而奇数的末尾必然是1 ，我们还是借助于之前的二进制

1010 1010 0100 010X 式子1 0111 1111 式子2

0100 0101

注意：我在的式子一最后一位写的是x

式子2 是（n-1），n是一个偶数，那么（n-1）一定是一个奇数，那么由于&的存在，最终的index 值，就有可能最后的结果 就是有可能是个偶数页有可能是个奇数，至于算出来到底是个偶数还是个奇数，那么就由你的式子一决定啦~~

四、总结

好了，哥们门，如果以后面试官问你，map的哈希冲突是怎么一回事，怎么答，你应该知道了吧，希望大家通过学习能有所收获