hash算法深度学习（数据结构与算法）

提到hash，相信大多数同学都不会陌生，之前很火现在也依旧很火的技术区块链背后的底层原理之一就是hash，下面就从hash算法的原理和实际应用等几个角度，对hash算法进行一个讲解。

1、什么是hash

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

Hash 算法能将将任意长度的二进制明文映射为较短的二进制串的算法，并且不同的明文很难映射为相同的 Hash 值。

也可以理解为空间映射函数，是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，Hash 函数转换后不可逆，意思是不可能通过逆操作和 Hash 值还原出原始的值。

散列方法的主要思想是根据结点的关键码值来确定其存储地址：以关键码值K为自变量，通过一定的函数关系h(K)(称为散列函数)，计算出对应的函数值来，把这个值解释为结点的存储地址，将结点存入到此存储单元中。检索时，用同样的方法计算地址，然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列（hash，也称“哈希”）是一种重要的存储方式，也是一种常见的检索方法。

2、Hash的特点

Hash 值又称为指纹或者摘要，具有以下特点：

正向快速：给定明文和 Hash 算法，在有限时间和有限资源内能计算得到 Hash 值。逆向困难：给定 Hash 值，在有限时间内很难逆推出明文。输入敏感：原始输入信息发生任何变化，新的 Hash 值都应该出现很大变化。冲突避免：很难找到两段内容不同的明文，使得它们的 Hash 值一致。

一致性。

Hash 函数可以接受任意大小的数据，并输出固定长度的散列值，同时输出不同值的概率应该尽可能一致。如 CityHash128，不管原始数据有多大，计算得到的 hash 值总是 128 bit。

雪崩效应。

原始数据哪怕只有一个字节的修改，得到的 hash 值都会发生巨大的变化。

单向。

只能从原始数据计算得到 hash 值，不能从 hash 值计算得到原始数据。所以散列算法不是加密解密算法，加密解密是可逆的，散列算法是不可逆的。

避免冲突。

几乎不可能找到一个数据和当前计算的这个数据计算出一样的 hash 值，因此散列函数能够确保数据的唯一性。在 Hash 函数保证不同值出现的概率一致的情况下，CityHash128 出现碰撞的概率只有 2 ^ -128。因为不同 Key 的碰撞概率很小，所以在某些情况下我们可以直接使用较短的 Hash 值代替较长原始数据存储。

3、hash碰撞的解决方案

3.1 哈希碰撞的理解

先来看看哈希表的定义，在概念上哈希表可以定义为是一个根据键（Key）而直接访问在内存中存储位置的值（Value）的数据结构。这里所说的键就是指哈希函数的输入，而这里的值并不是指哈希值，而是指我们想要保存的值。

在现实中， 想要有一个完美的哈希函数，将输入值转换成哈希值而不产生哈希碰撞基本是不可能的，所以哈希表在通过键来访问存储位置的值的时候，是根据我们处理哈希碰撞来决定它自身操作的。那下面我们就以一个具体例子来说明一下，不同的哈希碰撞其解决方式所带来的底层存储键值对操作的差异。 我们假设存储哈希表的底层数据结构是一个大小为 3 的数组，我们还是以保存好友电话号码为例，这个哈希表的键是我们好友的名字，哈希表的值是这个好友的电话号码。刚开始的时候，因为这个数据结构并没有存储任何信息，所以数据结构内存结构图如下图所示：

假设第一个输入的键值对是（Tom：123456），表示好友的名字叫 Tom，电话号码为 123456。我们同时假设 Tom 这个字符串在通过哈希函数之后的所产生的哈希值是 0，此时可以把 123456 这个值放在以哈希值为索引的地方，内存结构如下图所示：

紧接着，我们输入的第二个键值对是（Jack：456789），同时假设 Jack 这个字符串在通过哈希函数之后所产生的哈希值也是 0，而因为索引为 0 的位置已经存放一个值了，也就表示这时候产生了哈希碰撞。

3.2 hash 碰撞产生的概率

   无论 hash table 有多大，hash 冲突都很容易出现。典型的例子是生日悖论， 23 个人中两个人生日相同的概率高达 50%。

3.3 hash碰撞的解决方案

3.3.1 开放地址法

开放定址法也称为再散列法，基本思想就是，如果p=H(key)出现冲突时，则以p为基础，再次hash，p1=H(p),如果p1再次出现冲突，则以p1为基础，以此类推，直到找到一个不冲突的哈希地址pi。 因此开放定址法所需要的hash表的长度要大于等于所需要存放的元素，而且因为存在再次hash，所以只能在删除的节点上做标记，而不能真正删除节点。

缺点:容易产生堆积问题;不适合大规模的数据存储;插入时会发生多次冲突的情况;删除时要考虑与要删除元素互相冲突的另一个元素，比较复杂。

3.3.2 再哈希法(双重散列，多重散列)

提供多个不同的hash函数，当R1=H1(key1)发生冲突时，再计算R2=H2(key1)，直到没有冲突为止。 这样做虽然不易产生堆集，但增加了计算的时间。

3.3.3 链地址法(拉链法)

链表地址法是使用一个链表数组，来存储相应数据，当hash遇到冲突的时候依次添加到链表的后面进行处理。

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

3.3.4 建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

3.3.5 HashMap中的处理冲突

下面是HashMap的put方法:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //如果hash数组为空，初始化一下 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) //计算落在hash桶的位置，如果当前桶为空，直接新增节点 tab[i] = newNode(hash, key, value, null); else { //当前桶存在元素 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果key已经存在，替换元素 e = p; else if (p instanceof TreeNode) //如果当前是树结构了(不是链表了),向树上添加元素 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //当前结构依然时链表，遍历链表，直到末尾或者找到key相同的元素替换 for (int binCount = 0; ; binCount) { //到达末尾，新增元素，如果链表长度达到8，转为红黑树 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //遍历链表的过程中，发现了有key相同的元素，直接替换，然后break if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { //如果是已经存在的元素，判断是否替换(onlyIfAbsent) V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } modCount; //如果容量超过阈值，扩容 if ( size > threshold) resize(); afterNodeInsertion(evict); return null; }

3.3.6 HashMap中的扩容机制

当HashMap中元素的个数达到了阈值，(capacity * load factor)，HashMap中，元素存放的位置与hash数组的个数是有关系的(tab[i = (n - 1) & hash])，所以当发生扩容是，hash数组的个数发生了变化，这个时候，元素也需要重新进行hash计算。

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //老的容量和阈值 int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; //计算新的容量和阈值 int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //构建新的hash桶 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { //遍历原由的hash桶，copy元素到新的里面 for (int j = 0; j < oldCap; j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; //原来的hash桶置空 if (e.next == null) //原来位置上只有一个元素(没有链表和树),直接放到新的位置 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //如果是树状结构，单独处理 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order 这里的是链表元素 Node<K,V> loHead = null, loTail = null; //原来index位置 Node<K,V> hiHead = null, hiTail = null; //新的index位置 Node<K,V> next; //循环处理链表元素，判断元素是放在原index位置还是放在新index位置 do { next = e.next; //放在原index的位置的元素，loHead拿到链表头，loTail拿到链表尾 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //放在新index位置的元素，hiHead拿到链表头，hiTail拿到链表尾 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //放入原index处 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //放入新index处 if (hiTail != null) { hiTail.next = null; newTab[j oldCap] = hiHead; } } } } } return newTab; }

其中比较有意思的是，由于put时计算hash数组角标是通过i = (n - 1) & hash计算的，其中n是的2的x次幂，扩容时，容量变为原来的两倍,n-1 == (n-1)<<1 & 1，所以hash桶中的元素，要么还在原来的index位置，要么在oldIndex oldCap的位置。所以放入新的index时，元素下表:newTab[j oldCap]。

关于treenode，HashMap在扩容时，如果当前节点是棵树，先还是和链表的一样，将所有元素分为两批(一批还在当前index，另一批在新的index位置，此处传入的bit=oldCap，所以和链表的还是蛮类似的)。分成的两组，分别判断当前元素个数是否小于阈值，如果是，还原成链表。

final void split(HashMap<K,V> Map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)e.next; e.next = null; if ((e.hash & bit) == 0) { if ((e.prev = loTail) == null) loHead = e; else loTail.next = e; loTail = e; lc; } else { if ((e.prev = hiTail) == null) hiHead = e; else hiTail.next = e; hiTail = e; hc; } } if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) // (else is already treeified) loHead.treeify(tab); } } if (hiHead != null) { if (hc <= UNTREEIFY_THRESHOLD) tab[index bit] = hiHead.untreeify(map); else { tab[index bit] = hiHead; if (loHead != null) hiHead.treeify(tab); } } }

4、hash算法在分布式系统中的应用

负载均衡

• 常见的负载均衡算法：轮询、随机、加权轮询等
• 通用的需求：将一个用户的请求打到相同的服务器上，高效利用缓存
• 对客户端的IP地址或者会话ID计算哈希值
• 根据hash值取模计算，分配到不同的服务器上

数据分片

• 如何统计关键字搜索次数
• 难点：日志很大，不能放入一台服务器内存
• 解决思路：将任务拆分（将关键字hash到不同机器上），通过不同服务器进行处理
• 类似MapReduce
• 如何判断图片是否在图库
• 先利用哈希值对机器取模，在对机器进行ahsh查找
• 突破单机限制

分布式存储

• 利用hash实现分布式存储
• 问题：增加机器后，取余将会造成数据丢失，最终造成缓存雪崩
• 解决：通过一致性hash算法解决（虚拟环和虚拟节点）

,