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