什么是Hash?

· ☕ 5 分钟 · 👻 Victor

走得慢的时候,为什么不跑呢?#️⃣

哈希散列表

两个概念:

散列表

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

散列函数

散列函数,顾名思义,它是一个函数。如果把它定义成 hash(key) ,其中 key 表示元素的键值,则 hash(key) 的值表示经过散列函数计算得到的散列值。

散列函数特点:

  • 确定性
  • 散列碰撞(collision)
  • 不可逆性(一个哈希值对应无数个明文,理论上你并不知道哪个是。)
  • 混淆特性

常见的散列函数:

  • MD51
  • SHA-12

为什么哈希算法查找数组元素会更快?

原来使用下标进行匹配的画,会一个一个从一整个数组进行元素匹配,知道找到相等的元素才得到数组的信息。例如在Arr[20]查找值为12的,就需要从下标0到19进行查找。

但是哈希散列表将一个一个按顺序的查找转换为使用计算的方式进行查找,将运算结果的下标映射成一个哈希表,实现了跳跃式的查找,从而效率更高。

问题:散列冲突

对于散列表而言,无论设置的存储区域(n)有多大,当需要存储的数据大于 n 时,那么必然会存在哈希值相同的情况。这就是所谓的散列冲突

解决散列函数的两个方法:

  1. 链表法

    就是使用链表来保存冲突下标的数据,例如$12 % 5 = 2$和$7 % 5 = 2$,那么在下标为2的表下用一个链表存储12和7。

  2. 开放寻址法。

    常见三种方法:线性探测法、二次探测法、双散列

    假设哈希函数为:
    $$
    H(key) = key \mod10
    $$

    线性探测法

    还是$12 % 10 = 2 $和$22 % 10 = 2$这两个例子,当22这个数字需要存入哈希表时,发现已经有12这个元素存放在下标为2的哈希表上了,那么对Hash后的数字加一在进行Hash。即对7进行这样的操作:
    $$
    H((H(key)+1)) = ((22 \mod 10) + 1) \mod 10 = (2 + 1) \mod 10 = 3
    $$
    但是这种方式的问题是冲突较多的时候会出现数据聚集在一个区域,这样不利于查询数据。

    二次探测法

    二次探测法使用下面的函数解决冲突:
    $$
    (H(key) \pm j^2) \mod 10,j = 0,1,2…
    $$
    这种方法较为复杂,而且虽然不会连续的聚集一片,但是会在多个间断的位置聚集。

    双散列

    双散列,顾名思义就需要增加一个二级散列函数,例如$G(key) = q - (key \mod q) q为素数且q<N$,发现冲突使用如下操作:
    $$
    H(key) + j * G(key),j = 0,1,2……
    $$
    双散列方法有很多组合的方法,这里只是其中的一种,也有一些例如:$H(key) + G(key)$,没有j这个参数。

密码学中的哈希算法

hash(散列、杂凑)函数,是将任意长度的数据映射到有限长度的域上。直观解释起来,就是对一串数据m进行杂糅,输出另一段固定长度的数据h,作为这段数据的特征(指纹)。也就是说,无论数据块m有多大,其输出值h为固定长度。到底是什么原理?将m分成固定长度(如128位),依次进行hash运算,然后用不同的方法迭代即可(如前一块的hash值与后一块的hash值进行异或)。如果不够128位怎么办?用0补全或者用1补全随意,算法中约定好就可以了。

一般来说,公司不会直接将用户的密码保存在数据库中,而是保存经过哈希操作的密码得到的哈希值。这样,当哈希值被不法分子窃取,也不能还原出用户的密码;并且,公司只需要将用户输入的密码进行哈希操作,将哈希值与存储在数据库中的哈希值进行对比就能够验证用户了。

哈希的其他用法

数据校验

  1. Git的- git commit id

    每次git提交后都有一个commit id,比如:

    19d02d2cc358e59b3d04f82677dbf3808ae4fc40

  2. 版权校验

    判断两个文件是不是一样的,对两个文件都进行哈希操作,得到哈希值,若哈希值相同,则两个文件为同一个文件。

  3. 大文件分块校验

    例如使用bt下载,在p2p网络中会把一个大文件拆分成很多小的数据各自传输。这样的好处是如果某个小的数据块在传输过程中损坏了,只要重新下载这个块就好。为了确保每一个小的数据块都是发布者自己传输的,我们可以对每一个小的数据块都进行一个hash的计算,维护一个hash List,在收到所有数据以后,我们对于这个hash List里的每一块进行遍历比对。这里有一个优化点是如果文件分块特别多的时候,如果遍历对比就会效率比较低。可以把所有分块的hash值组合成一个大的字符串,对于这个字符串再做一次Hash运算,得到最终的hash(Root hash)。在实际的校验中,我们只需要拿到了正确的Root hash,即可校验Hash List,也就可以校验每一个数据块了。

负载均衡

一致性hash的基本原理是将输入的值hash后,对结果的hash值进行2^32取模,这里和普通的hash取模算法不一样的点是在一致性hash算法里将取模的结果映射到一个环上。将缓存服务器与被缓存对象都映射到hash环上以后,从被缓存对象的位置出发,沿顺时针方向遇到的第一个服务器,就是当前对象将要缓存于的服务器,由于被缓存对象与服务器hash后的值是固定的,所以,在服务器不变的情况下,一个openid必定会被缓存到固定的服务器上,那么,当下次想要访问这个用户的数据时,只要再次使用相同的算法进行计算,即可算出这个用户的数据被缓存在哪个服务器上,直接去对应的服务器查找对应的数据即可。这里的逻辑其实和直接取模的是一样的。如下图所示:

这部分不是很深入,之后再补充……🚴


参考链接:

  1. https://www.zhihu.com/question/26762707?sort=created-知乎
  2. 动画:什么是散列表?-五分钟算法
  3. 什么是 hash?-知乎

  1. MD5 即 Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一,主流编程语言普遍已有 MD5 实现。 ↩︎

  2. SHA-1(英语:Secure Hash Algorithm 1,中文名:安全散列算法1)是一种密码散列函数,SHA-1可以生成一个被称为消息摘要的160位(20字节)散列值,散列值通常的呈现形式为40个十六进制数。 ↩︎

分享

redisread
作者
Victor
Full Stack