哈希算法取余

㈠ hash算法是怎么样的

hash算法是一种散列算法，是把任意的长度的输入，转换成固定的额输出，福鼎的输出，输出的是散列值。在空间的比较中，输入的空间是远大于输出的散列值的空间，不同输入散列成同样的输出，一般很难从输出的散列值获取输入值的。

常用的hash函数有直接取余法、乘法取整法，平方取中法。在直接取余法中，质数用到的比较多，在乘法取整法中，主要用于实数，在平方取中法里面，平方后取中间的，每位包含的信息比较多些。

Hash在管理数据结构中的应用

在用到hash进行管理的数据结构中，就对速度比较重视，对抗碰撞不太看中，只要保证hash均匀分布就可以。比如hashmap，hash值（key）存在的目的是加速键值对的查找，key的作用是为了将元素适当地放在各个桶里，对于抗碰撞的要求没有那么高。

换句话说，hash出来的key，只要保证value大致均匀的放在不同的桶里就可以了。但整个算法的set性能，直接与hash值产生的速度有关，所以这时候的hash值的产生速度就尤为重要。

㈡ 哈希算法从原理到实战

引言 

       将任意长度的二进制字符串映射为定长二进制字符串的映射规则我们称为散列（hash）算法，又叫哈希（hash）算法，而通过原始数据映射之后得到的二进制值称为哈希值。哈希表（hash表）结构是哈希算法的一种应用，也叫散列表。用的是数组支持按照下标随机访问数据的特性扩展、演化而来。可以说没有数组就没有散列表。

哈希算法主要特点

        从哈希值不能反向推导原始数据，也叫单向哈希。

        对输入数据敏感，哪怕只改了一个Bit，最后得到的哈希值也大不相同。

        散列冲突的概率要小。

        哈希算法执行效率要高，散列结果要尽量均衡。

哈希算法的核心应用

         安全加密 ：对于敏感数据比如密码字段进行MD5或SHA加密传输。

         唯一标识 ：比如图片识别，可针对图像二进制流进行摘要后MD5，得到的哈希值作为图片唯一标识。

         散列函数 :是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。不过相对哈希算法的其他方面应用，散列函数对散列冲突要求较低，出现冲突时可以通过开放寻址法或链表法解决冲突。对散列值是否能够反向解密要求也不高。反而更加关注的是散列的均匀性，即是否散列值均匀落入槽中以及散列函数执行的快慢也会影响散列表性能。所以散列函数一般比较简单，追求均匀和高效。

        *负载均衡 ：常用的负载均衡算法有很多，比如轮询、随机、加权轮询。如何实现一个会话粘滞的负载均衡算法呢？可以通过哈希算法，对客户端IP地址或会话SessionID计算哈希值，将取得的哈希值与服务器列表大小进行取模运算，最终得到应该被路由到的服务器编号。这样就可以把同一IP的客户端请求发到同一个后端服务器上。

        *数据分片 ：比如统计1T的日志文件中“搜索关键词”出现次数该如何解决？我们可以先对日志进行分片，然后采用多机处理，来提高处理速度。从搜索的日志中依次读取搜索关键词，并通过哈希函数计算哈希值，然后再跟n(机器数)取模，最终得到的值就是应该被分到的机器编号。这样相同哈希值的关键词就被分到同一台机器进行处理。每台机器分别计算关键词出现的次数，再进行合并就是最终结果。这也是MapRece的基本思想。再比如图片识别应用中给每个图片的摘要信息取唯一标识然后构建散列表，如果图库中有大量图片，单机的hash表会过大，超过单机内存容量。这时也可以使用分片思想，准备n台机器，每台机器负责散列表的一部分数据。每次从图库取一个图片，计算唯一标识，然后与机器个数n求余取模，得到的值就是被分配到的机器编号，然后将这个唯一标识和图片路径发往对应机器构建散列表。当进行图片查找时，使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后，得到的值k，就是当前图片所存储的机器编号，在该机器的散列表中查找该图片即可。实际上海量数据的处理问题，都可以借助这种数据分片思想，突破单机内存、CPU等资源限制。

        *分布式存储 ：一致性哈希算法解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。

         JDK集合工具实现 ：HashMap、 LinkedHashMap、ConcurrentHashMap、TreeMap等。Map实现类源码分析，详见  https://www.jianshu.com/p/602324fa59ac

总结

        本文从哈希算法的原理及特点，总结了哈希算法的常见应用场景。

        其中基于余数思想和同余定理实现的哈希算法（除留取余法），广泛应用在分布式场景中（散列函数、数据分片、负载均衡）。由于组合数学中的“鸽巢”原理，理论上不存在完全没有冲突的哈希算法。（PS:“鸽巢”原理是指有限的槽位，放多于槽位数的鸽子时，势必有不同的鸽子落在同一槽内，即冲突发生。同余定理：如果a和b对x取余数操作时a%x = b%x，则a和b同余）

        构造哈希函数的常规方法有：数据分析法、直接寻址法、除留取余法、折叠法、随机法、平方取中法等  。

        常规的解决哈希冲突方法有开放寻址法（线性探测、再哈希）和链表法。JDK中的HashMap和LinkedHashMap均是采用链表法解决哈希冲突的。链表法适合大数据量的哈希冲突解决，可以使用动态数据结构（比如：跳表、红黑树等）代替链表，防止链表时间复杂度过度退化导致性能下降；反之开放寻址法适合少量数据的哈希冲突解决。

㈢ 关于哈希值

通俗来讲，哈希值就是文件的身份证，不过比身份证还严格。他是根据文件大小，时间，类型，创作者，机器等计算出来的，很容易就会发生变化，谁也不能预料下一个号码是多少，也没有更改他的软件。哈希算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的。

有这样一种情境，有三万张图片我们要均匀放置于三个缓存服务器上
简单的做法是对缓存的key进行哈希计算，得到的值进行取模计算，所得到的余数，便是缓存的服务器编号

hash % 机器数 = 余数
当机器数为3时无论值为多少，其余数永远只有0，1，2三种情况
那么根据余数，我们给服务器进行编号s0,s1,s2,余数为0的放置于s0服务器上，1，2同理。

这样我们就将三万张图片的缓存均分成三份存放与三台缓存服务器中
因为对同一张图片进行哈希计算时，所得到的哈希值是不变的，所以当需要访问图片时，只要再次进行哈希计算和取模计算，就能获取到图片存放于哪台服务器，便可以去该服务器中查找满足了我们的需求。而这种算法也称之为哈希算法

这其中有一个问题，那便是如果我增加一台服务器呢
可以预见的是，当增加一台服务器服务器数变成了4.而余数也出现了4种情况

这时向s2的服务器查询时，无法读取到图片，这导致了程序无法从缓存服务器中读取数据，这时程序就会向后端服务器请求，而大量的缓存同时失效，会导致所有请求都指向后端服务器，这会引起后端服务器的崩溃。
这是就要引入一致性哈希算法

还是同样的三个缓存服务器，这次我们将哈希值对2 ^{32取模，所得到的数一定是1到2} 32之间的一个整数
然后我们想象一个圆环，其上的每一个点都代表1到2^32之间的一个整数，而这个圆环也被称为hash环
之后我们对服务器A进行取模计算，这样算出来的整数肯定在1到2^32之间，将这个整数代表为服务器A,并且我们可以将这个整数映射到哈希环上，同样的道理我们处理另外两个服务器，这时三个服务器都被映射到了哈希环上，对于图片我们也将他映射到哈希环上
那么我们只要从图片的哈希值开始，沿顺时针在哈希环上查找，遇到的第一个服务器便是图片缓存所在的服务器
这时哪怕新添加一个服务器在哈希环上，我门所丢失的缓存数据也只是新添加的服务器到逆时针方向遇到的第一个服务器这部分数据，而这样仍然有大部分缓存在缓存服务器中可以被查找到，这样可以帮助后端服务器分担大部分压力，不会使服务器崩溃，而这部分丢失的缓存数据，之后重新在后端加载便可以了

这又引入了另一个问题，哈希偏斜
我们无法确保三个服务器在哈希环上为均分的状态，很有可能其中一台服务器分到了很大部分而另两台分到了很少的部分，这样同样会有后端服务器崩溃的隐患
我们可以添加很多虚拟结点同一个服务器我们分出许多虚拟节点，映射在哈希环上，哈希环上的节点越多，缓存被均分的概率便越大，这样可以尽可能的保证缓存在服务器上是接近理想均分的状态，避免了哈希偏斜的问题

㈣ 哈希表、哈希算法、一致性哈希表

    散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。它通过把关键码映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数（哈希函数），存放记录的数组叫做散列表。

  优点：

        哈希表可以提供快速的操作。

缺点：

        哈希表通常是基于数组的，数组创建后难于扩展。

        也没有一种简便的方法可以以任何一种顺序〔例如从小到大）遍历表中的数据项 。

    综上， 如果不需要有序遍历数据，井且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

        1. 使用哈希函数将被查找的键转换为数组的索引。

        2. 处理哈希碰撞冲突。

    若关键字为 k ，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，按这个思想建立的表为散列表。

    若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为 均匀散列函数 (Uniform Hash function)，这就是使关键字经过散列函数得到一个"随机的地址"，从而减少碰撞。

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

一个好的散列函数一般应该考虑下列因素 ：

    1.计算简单，以便提高转换速度。

    2.关键词对应的地址空间分布均匀，以尽量减少冲突。

1.   直接寻址法

    取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b为整数),这种散列函数也叫做自身函数.如果H(Key)的哈希地址上已经有值了,那么就往下一个位置找,直到找到H(Key)的位置没有值了就把元素放进去。

2.   数字分析法

    数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

3.   平方取中法

    取关键字平方后的中间几位作为散列地址。这种方法的原理是通过取平方扩大差别，平方值的中间几位和这个数的每一位都相关，则对不同的关键字得到的哈希函数值不易产生冲突，由此产生的哈希地址也较为均匀。该方法适用于关键字中的每一位都有某些数字重复出现频度很高的现象。

4.   折叠法

    折叠法是将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为散列地址。

    数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    该方法适用于关键字特别多的情况。

5.   随机数法

    选择一个随机数,作为散列地址,通常用于关键字长度不同的场合。

6.   除留余数法

    取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m.不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。

    对不同的关键字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，这种现象称为碰撞(英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。

    通过构造性能良好的散列函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。 创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。

下面以创建哈希表为例，说明解决冲突的方法。

1.开放寻址法

    这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H(key)出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：Hi=(H(key)+di)%m   i=1，2，…，m-1,其中H（key）为哈希函数，m 为表长，di称为增量序列，i为碰撞次数。增量序列的取值方式不同，相应的再散列方式也不同。增量序列主要有以下几种：

    (1) 线性探测再散列

        di=1，2，3，…，m-1

        这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

    (2)二次探测再散列

        di=12，-12，22，-22，…，k2，-k2( k<=m/2 )

        这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

    (3)伪随机探测再散列

        di=伪随机数序列。

    线性探测再散列的 优点 是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。

    其实除了上面的几种方法，开放寻址法还有很多变种，不过都是对di有不同的表示方法。（如双散列探测法：di=i*h2(k)）

2.再哈希法

    这种方法是同时构造多个不同的哈希函数：Hi=RHi（key），i=1，2,3，…,n。

    当哈希地址H1=RH1（key）发生冲突时，再计算H2=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

 3.链地址法(拉链法)

    这种方法的基本思想是将所有哈希地址相同的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表（数组）中，因而查找、插入和删除主要在同义词链中进行。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。链地址法适用于经常进行插入和删除的情况。

     拉链法的优点

        与开放寻址法相比，拉链法有如下几个优点：

            (1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；

            (2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；

            (3)开放寻址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中理论上可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；（散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度）

注：HashMap默认装填因子是0.75。

            (4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放寻址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。这是因为各种开放寻址法中，空地址单元都被理解没有查找到元素。 因此在用开放寻址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

     拉链法的缺点

        拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放寻址法较为节省空间，此时将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放寻址法中的冲突，从而提高平均查找速度。

4、建立公共溢出区

    这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(在这个方法里面是把元素分开两个表来存储)。

    散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

    查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素:

    1. 散列函数是否均匀;

    2. 处理冲突的方法;

    3. 散列表的装填因子。

     散列表的装填因子

        定义为:α= 填入表中的元素个数 / 散列表的长度

        α是散列表装满程度的标志因子。由于表长是定值，α与"填入表中的元素个数"成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大;α越小，填入表中的元素较少，产生冲突的可能性就越小。

        实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

    这个HASH算法不是大学里数据结构课里那个HASH表的算法。这里的HASH算法是密码学的基础，了解了hash基本定义，就不能不提到一些着名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。

Hash算法在信息安全方面的应用主要体现在以下的3个方面:

     ⑴  文件校验

        我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗 数据篡改 的能力，它们一定程度上能检测出数据传输中的信道误码，但却不能防止对数据的恶意破坏。

        MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性 校验和 (Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。

     ⑵  数字签名

        Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在 数字签名 协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

     ⑶ 鉴权协议

        如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

    一致性哈希表简称DHT，主要应用于分布式缓存中，可以用来解决分布式存储结构下动态增加和删除节点所带来的问题。比如，一个分布式的存储系统，要将数据存储到具体的节点上，如果采用普通的hash方法，将数据映射到具体的节点上，如key%N（key是数据的key，N是机器节点数），如果有一个机器加入或退出这个集群，则所有的数据映射都无效了，如果是持久化存储则要做数据迁移，如果是分布式缓存，则其他缓存就失效了。

判定哈希算法好坏的四个定义 ：

    1、平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。

    2、单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

    3、分散性(Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。 分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

    4、负载(Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的， 因此好的哈希算法应能够尽量降低缓冲的负荷。

    在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash取模算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。接下来主要说明一下一致性哈希算法是如何设计的。

以SpyMemcached的ketama算法来说，思路是这样的：

把数据用hash函数，映射到一个很大的空间里，如图所示。数据的存储时，先得到一个hash值，对应到这个环中的每个位置，如k1对应到了图中所示的位置，然后沿顺时针找到一个机器节点B，将k1存储到B这个节点中。

如果B节点宕机了，则B上的数据就会落到C节点上，如下图所示：

这样，只会影响C节点，对其他的节点A，D的数据不会造成影响。然而，这又会造成一个“雪崩”的情况，即C节点由于承担了B节点的数据，所以C节点的负载会变高，C节点很容易也宕机，这样依次下去，这样造成整个集群都挂了。

为此，引入了“虚拟节点”的概念：即把想象在这个环上有很多“虚拟节点”，数据的存储是沿着环的顺时针方向找一个虚拟节点，每个虚拟节点都会关联到一个真实节点，如下图所使用：

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。