数据结构-Hash

先看一下hash表的结构图：

哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表

白话一点的说就是通过把Key通过一个固定的算法函数（hash函数）转换成一个整型数字，然后就对该数字对数组的长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。

先了解一下下面几个常说的几个关键字是什么：

key ：我们输入待查找的值

value ：我们想要获取的内容

hash值 ：key通过hash函数算出的值（对数组长度取模，便可得到数组下标）

hash函数（散列函数） ：存在一种函数F，根据这个函数和查找关键字key，可以直接确定查找值所在位置，而不需要一个个遍历比较。这样就预先知道key在的位置，直接找到数据，提升效率。

即

地址index=F(key)

hash函数就是根据key计算出该存储地址的位置，hash表就是基于hash函数建立的一种查找表。

方法有很多种，比如直接定址法、数字分析法、平方取中法、折叠法、随机数法、除留余数法等，网上相关介绍有很多，这里就不重点说这个了

对不同的关键字可能得到同一散列地址， 即k1≠k2，而f(k1)=f(k2)，或f(k1) MOD 容量 =f(k2) MOD 容量 ，这种现象称为 碰撞 ，亦称 冲突 。

通过构造性能良好的hash函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是hash表的另一个关键问题。

创建和查找hash表都会遇到冲突，两种情况下解决冲突的方法应该一致。

这里要提到两个参数： 初始容量 ， 加载因子 ，这两个参数是影响hash表性能的重要参数。

容量 ： 表示hash表中数组的长度，初始容量是创建hash表时的容量。

加载因子 ： 是hash表在其容量自动增加之前可以达到多满的一种尺度（存储元素的个数），它衡量的是一个散列表的空间的使用程度。

loadFactor = 加载因子 / 容量

一般情况下，当loadFactor >> 和 ^ 就是将高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值。

在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如 jack，将它拆解成 j、a、c、k（字符的本质就是一个整数，所以 jack 的哈希值可以表示为 j * n3 + a * n2 + c * n1 + k * n0，表达式也可以写成 [(j * n + a) * n + c] * n + k，代码实现如下：

看上面代码时，可以发现，表达式中的 n 使用的是 31 这个数字，那么为什么用 31 呢？

因为 31 不仅符合 22 - 1 , 而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。

JDK 中，乘数 n 也是用 31，31 也是经过观测分布结果后的选择，关于 31 的变体可以有以下几种：

31 * i = (25 - 1) * i = i * 25 - i = (i

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com