详解--Hash（中文也称散列、哈希）

参考链接
参考链接2

1. hash 概念

1.1 什么是 hash

• Hash 也称散列、哈希，对应的英文都是 Hash。

  • 基本原理就是把任意长度的输入，通过 Hash 算法变成固定长度的输出。这个映射的规则就是对应的 Hash 算法，而原始数据映射后的二进制串就是哈希值。
  • hash 算法理论上会出现 不同数据通过 hash 算法计算出相同的 hash 值，叫做碰撞。
  • 活动开发中经常使用的 MD5 和 SHA 都是历史悠久的 Hash 算法。
  • 好的 hash 算法至少应 计算 hash 值迅速且 hash 值冲突概率要小。

• 两个知识

  • 抗碰撞能力

    • 对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。

  • 抗篡改能力

    • 对于一个数据块，哪怕只改动其一个比特位，其hash值的改动也会非常大。

2. Hash碰撞的解决方案

即如果遇到了 hash 冲突 需要解决的时候应该怎么处理，比较常用的算法是链地址法和开放地址法。

2.1 链地址法

• 链表地址法是使用一个链表数组，来存储相应数据，当hash遇到冲突的时候依次添加到链表的后面进行处理。
  
• 链地址在处理的流程如下：
  • 添加一个元素的时候，首先计算元素 key 的 hash 值，确定插入数组中的位置。
    如果当前位置下没有重复数据，则直接添加到当前位置。
    当遇到冲突的时候，添加到同一个hash值的元素后面，行成一个链表。
    • 这个链表的特点是同一个链表上的 Hash 值相同。
      java的数据结构HashMap使用的就是这种方法来处理冲突，JDK1.8中，针对链表上的数据超过8条的时候，使用了红黑树进行优化。

2.2 开放地址法

• 开放地址法是指大小为 M 的数组保存 N 个键值对，其中 M > N。
  我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为**“开放地址”哈希表**。

  1. 线性探测法，就是比较常用的一种“开放地址”哈希表的一种实现方式。
     • 线性探测法的核心思想是当冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
       简单来说就是：一旦发生冲突，就去寻找下 一个空的散列表地址，只要散列表足够大，空的散列地址总能找到。
       线性探测法的数学描述是：h(k, i) = (h(k, 0) + i) mod m，i表示当前进行的是第几轮探查。
       i=1时，即是探查h(k, 0)的下一个；i=2，即是再下一个。这个方法是简单地向下探查。
       mod m表示：到达了表的底下之后，回到顶端从头开始。

  对于开放寻址冲突解决方法，除了线性探测方法之外，还有另外两种比较经典的探测方法：

  2. 二次探测（Quadratic probing）和双重散列（Double hashing）。但是不管采用哪种探测方法，当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。
     为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用 装载因子（load factor） 来表示空位的多少。
     散列表的装载因子 = 填入表中的元素个数 / 散列表的长度。
     装载因子越大，说明冲突越多，性能越差。

2.3 示例

假设散列长为 8，散列函数 H(K)=K mod 7，给定的关键字序列为 {32,14,23,2, 20}

• 当使用链表法时，相应的数据结构如下图所示：
  
• 当使用线性探测法时，相应的数据结果如下图所示：
  
  这里的两种算法的区别是 2 这个元素，在链表法中还是在节点 2 的位置上，但是在线性探测法遇到冲突时会将冲突数据放到下一个空的位置下面。

3 hash 的应用

3.1 信息加密

• 在密码学中，hash算法的作用主要是用于消息摘要和签名，换句话说，它主要用于对整个消息的完整性进行校验。
  • 举个例子，我们登陆知乎的时候都需要输入密码，那么知乎如果明文保存这个密码，那么黑客就很容易窃取大家的密码来登陆，特别不安全。那么知乎就想到了一个方法，使用hash算法生成一个密码的签名，知乎后台只保存这个签名值。由于hash算法是不可逆的，那么黑客即便得到这个签名，也丝毫没有用处；而如果你在网站登陆界面上输入你的密码，那么知乎后台就会重新计算一下这个hash值，与网站中储存的原hash值进行比对，如果相同，证明你拥有这个账户的密码，那么就会允许你登陆。

3.2 数据校验

3.2.1 git commit id

• 每次 git 提交后都有一个 commit id，比如:
  19d02d2cc358e59b3d04f82677dbf3808ae4fc40
  就是一次 git commit 的结果，那么这个id是如何生成出来的呢？查阅了相关资料，使用如下代码可以进行查看：

  printf "commit %s\0" $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD
  1

• git的 commit id 主要包括了以下几部分内容：Tree 哈希，parent 哈希、作者信息和本次提交的备注。针对这些信息进行SHA-1 算法后得到值就是本次提交的commit id。简单来讲，就是对于单次提交的头信息的一个校验和。
  

  Linux kernel 开创者和 Git 的开发者——Linus 说，Git 使用了 sha1 并非是为了安全性，而是为了数据的完整性；它可以保证，在很多年后，你重新 checkout 某个commit 时，一定是它多年前的当时的状态，完全一摸一样，完全值得信任。

3.2.2 版权校验

• 在数据校验方面的另一个应用场景就是版权的保护或者违禁信息的打击。
• 比如某个小视频，第一个用户上传的时候，我们认为是版权所有者，计算一个 hash 值存下来。
  当第二个用户上传的时候，同样计算hash值，如果hash值一样的话，就算同一个文件。这种方案其实也给用户传播违禁文件提高了一些门槛，不是简单的换一个名字或者改一下后缀名就可以躲避掉打击了。（当然这种方式也是可以绕过的，图片的你随便改一下颜色，视频去掉一帧就又是完全不同的hash值了。注意：我没有教你变坏，我只是和你在讨论这个技术。。。）另外我们在社区里，也会遇到玩家重复上传同一张图片或者视频的情况，使用这种校验的方式，可以有效减少 cos 服务的存储空间。

3.2.3 大文件分块校验

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

3.3 负载均衡

• 示例：
  在应对业务大用户量参与时，都会使用分库分表，针对用户的 openid 进行 hashtime33取模，就可以得到对应的用户分库分表的节点了。
  
  如上图所示，这里其实是分了10张表，openid计算后的hash值取模10，得到对应的分表，在进行后续处理就好。

  • 示例引申
    假设我们活动初始分表了 10 张，运营一段时间以后发现需要 10 张不够，需要改到 100 张。
    • 此时扩展的问题
      如果直接扩容的话，那么所有的数据都需要重新计算 Hash 值，大量的数据都需要进行迁移。如果更新的是缓存的逻辑，则会导致大量缓存失效，发生雪崩效应，导致数据库异常。
    • 解决办法
      造成这种问题的原因是 hash 算法本身的缘故，只要是取模算法进行处理，则无法避免这种情况。针对这种问题，我们就需要利用一致性 hash 进行相应的处理了。

• 一致性 hash 概念

  • 一致性hash的基本原理是将输入的值 hash 后，对结果的 hash 值进行 2^32 取模，这里和普通的 hash 取模算法不一样的点是 在一致性 hash 算法里将取模的结果映射到一个环上。

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

  • 示例
    初始情况如下：
    用户1的数据在服务器 A 里，用户 2、3 的数据存在服务器 C 里，用户 4 的数据存储在服务器 B 里。
    下面来看一下当服务器数量发生变化的时候，相应影响的数据情况：

    1. 服务器缩容
       服务器 B 发生了故障，进行剔除后，只有用户 4 的数据发生了异常。这个时候我们需要继续按照顺时针的方案，把缓存的数据放在用户 A 上面。
       

    2. 服务器扩容
       服务器扩容以后，新增了一台服务器 D，位置落在用户 2 和 3 之间。按照顺时针原则，用户 2 依然访问的是服务器 C 的数据，而用户 3 顺时针查询后，发现最近的服务器是 D，后续数据就会存储到 d 上面。
       

    3. 虚拟节点
       这只是一种理想情况，实际使用中，由于服务器节点数量有限，有可能出现分布不均匀的情况。这个时候会出现大量数据都被映射到某一台服务器的情况，如下图左侧所示。
       为了解决这个问题，我们采用了虚拟节点的方案。虚拟节点是实际节点（实际的物理服务器）在 hash 环上的复制品，一个实际节点可以对应多个虚拟节点。虚拟节点越多，hash 环上的节点就越多，数据被均匀分布的概率就越大。
       如右图所示，B、C、D 是原始节点复制出来的虚拟节点，原本都要访问机器D的用户1、4，分别被映射到了B,D。通过这样的方式，起到了一个服务器均匀分布的作用。

3.4 hash 算法扩展应用

3.4.1 SimHash

simHash是google用于海量文本去重的一种方法，它是一种局部敏感hash。
详情百度

3.4.2 GeoHash

GeoHash将地球作为为一个二维平面进行递归分解。每个分解后的子块在一定经纬度范围内拥有相同的编码。
参考链接

3.4.3 布隆过滤器

• 应用
  布隆过滤器被广泛用于黑名单过滤、垃圾邮件过滤、爬虫判重系统以及缓存穿透问题。

  • 对于数量小，内存足够大的情况，我们可以直接用 hashMap 或者 hashSet 就可以满足这个活动需求了。但是如果数据量非常大，比如 5 TB 的硬盘上放满了用户的参与数据，需要一个算法对这些数据进行去重，取得活动的去重参与用户数。
    这种时候，布隆过滤器就是一种比较好的解决方案了。

• 原理

百度