什么是哈希表和哈希算法?

1. 什么是哈希表和哈希算法?

哈希算法并不是一个特定的算法而是一类算法的统称。哈希算法也叫散列算法,一般来说满足这样的关系:f(data)=key,输入任意长度的data数据,经过哈希算法处理后输出一个定长的数据key。同时这个过程是不可逆的,无法由key逆推出data。如果是一个data数据集,经过哈希算法处理后得到key的数据集,然后将keys与原始数据进行一一映射就得到了一个哈希表。一般来说哈希表M符合M[key]=data这种形式。哈希表的好处是当原始数据较大时,我们可以用哈希算法处理得到定长的哈希值key,那么这个key相对原始数据要小得多。我们就可以用这个较小的数据集来做索引,达到快速查找的目的。稍微想一下就可以发现,既然输入数据不定长,而输出的哈希值却是固定长度的,这意味着哈希值是一个有限集合,而输入数据则可以是无穷多个。那么建立一对一关系明显是不现实的。所以"碰撞"(不同的输入数据对应了相同的哈希值)是必然会发生的,所以一个成熟的哈希算法会有较好的抗冲突性。同时在实现哈希表的结构时也要考虑到哈希冲突的问题。密码上常用的MD5,SHA都是哈希算法,因为key的长度(相对大家的密码来说)较大所以碰撞空间较大,有比较好的抗碰撞性,所以常常用作密码校验。
麻烦采纳，谢谢!

2. 哈希表算法的介绍

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重。这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。

3. 哈希表算法的哈希表的优缺点

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。第一次接触哈希表时，它的优点多得让人难以置信。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。对哈希表的使用者一一人来说，这是一瞬间的事。哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。而且，也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。如果需要这种能力，就只能选择其他数据结构。然而如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

4. 一致性哈希的哈希算法

一致性哈希提出了在动态变化的Cache环境中，哈希算法应该满足的4个适应条件： 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。（这段翻译信息有负面价值的，当缓冲区大小变化时一致性哈希(Consistent hashing)尽量保护已分配的内容不会被重新映射到新缓冲区。）简单的哈希算法往往不能满足单调性的要求，如最简单的线性哈希：x → ax + b mod (P)在上式中，P表示全部缓冲的大小。不难看出，当缓冲大小发生变化时(从P1到P2)，原来所有的哈希结果均会发生变化，从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时，所有的映射关系需要在系统内全部更新。而在P2P系统内，缓冲的变化等价于Peer加入或退出系统，这一情况在P2P系统中会频繁发生，因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。 负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。从表面上看，一致性哈希针对的是分布式缓冲的问题，但是如果将缓冲看作P2P系统中的Peer，将映射的内容看作各种共享的资源(数据，文件，媒体流等)，就会发现两者实际上是在描述同一问题。路由算法在一致性哈希算法中，每个节点(对应P2P系统中的Peer)都有随机分配的ID。在将内容映射到节点时，使用内容的关键字和节点的ID进行一致性哈希运算并获得键值。一致性哈希要求键值和节点ID处于同一值域。最简单的键值和ID可以是一维的，比如从0000到9999的整数集合。根据键值存储内容时，内容将被存储到具有与其键值最接近的ID的节点上。例如键值为1001的内容，系统中有ID为1000，1010，1100的节点，该内容将被映射到1000节点。为了构建查询所需的路由，一致性哈希要求每个节点存储其上行节点(ID值大于自身的节点中最小的)和下行节点(ID值小于自身的节点中最大的)的位置信息(IP地址)。当节点需要查找内容时，就可以根据内容的键值决定向上行或下行节点发起查询请求。收到查询请求的节点如果发现自己拥有被请求的目标，可以直接向发起查询请求的节点返回确认；如果发现不属于自身的范围，可以转发请求到自己的上行/下行节点。为了维护上述路由信息，在节点加入/退出系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息，还要知道一定深度(n跳)的间接下行节点信息，并且动态地维护节点列表。当节点退出系统时，它的上行节点将尝试直接连接到最近的下行节点，连接成功后，从新的下行节点获得下行节点列表并更新自身的节点列表。同样的，当新的节点加入到系统中时，首先根据自身的ID找到下行节点并获得下行节点列表，然后要求上行节点修改其下行节点列表，这样就恢复了路由关系。

5. 哈希表算法的哈希表的构造方法

1、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。但这种方法效率不高,时间复杂度是O(1),空间复杂度是O(n),n是关键字的个数2、数字分析法有学生的生日数据如下：年.月.日75.10.03　　75.11.23　　76.03.02　　76.07.12　　75.04.21　　76.02.15　　...经分析,第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。3、平方取中法取关键字平方后的中间几位为哈希地址。4、折叠法将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字，若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,则：5、除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p (p

6. 一致性哈希算法怎么保证数据的一致性

环割法（一致性 hash）环割法的原理如下：
1. 初始化的时候生成分片数量 X × 环割数量 N 的固定方式编号的字符串，例如 SHARD-1-NODE-1，并计算所有 X×N 个字符串的所有 hash 值。
2. 将所有计算出来的 hash 值放到一个排序的 Map 中，并将其中的所有元素进行排序。
3. 输入字符串的时候计算输入字符串的 hash 值，查看 hash 值介于哪两个元素之间，取小于 hash 值的那个元素对应的分片为数据的分片。

跳跃法（jumpstringhash）跳跃法的原理如下：1. 根据公式：

将数据落在每一个节点的概率进行平均分配。
2. 对于输入的字符串进行计算 hash 值，通过判断每次产生的伪随机值是否小于当前判定的节点 1/x，最终取捕获节点编号最大的作为数据的落点。3. 在实际使用中使用倒数的方法从最大节点值进行反向判断，一旦当产生的伪随机值大于 x 则判定此节点 x 作为数据的落点。

数据比较
下面将通过测试对环割法和跳跃法的性能及均衡性进行对比，说明 DBLE 为何使用跳跃法代替了环割法。
数据源：现场数据 350595 条
测试经过：
1. 通过各自的测试方法执行对于测试数据的分片任务。
2. 测试方法：记录分片结果的方差；记录从开始分片至分片结束的时间；记录分片结果与平均数的最大差值。
3. 由于在求模法 PartitionByString 的方法中要求分片的数量是 1024 的因数，所以测试过程只能使用 2 的指数形式进行测试，并在 PartitionByString 方法进行测试的时候不对于 MAC 地址进行截断，取全量长度进行测试。

7. 哈希表与哈希（Hash）算法

 根据设定的 哈希函数H（key） 和 处理冲突的方法 将一组关键字影像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为 哈希表 ，这一映像过程称为哈希造表或 散列 ，所得存储位置称 哈希地址 或 散列地址 。
   上面所提到的 哈希函数 是指：有一个对应关系  f  ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的查找算法那样进行比较，而是根据这个对应关系  f  找到给定值K的像 f（K） 。
   哈希函数也可叫哈希算法，它可以用于检验信息是否相同（ 文件校验 ），或者检验信息的拥有者是否真实（ 数字签名 ）。
   下面分别就哈希函数和处理冲突的方法进行讨论;
   构造哈希函数的方法有很多。在介绍各种方法前，首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是 均匀的 （Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。   常用的构造哈希函数的方法有：
                                                                                                                           理论研究表明， 除留余数法的模 p 取不大于表长且最接近表长 m 的素数效果最好，且 p 最好取1.1 n  ~ 1.7 n 之间的一个素数（n为存在的数据元素个数） 。
   以上便是常用的6种构造哈希函数的方法，实际工作中需视不同的情况采用采用不同的哈希函数，通常考虑的因素有：
   前面有提到过 均匀的哈希函数可以减少冲突，但不能避免 ，因此，如何处理冲突是哈希造表不可缺少的另一方面。
   通常用的处理冲突的方法有下列几种：
                                           在哈希表上进行查找的过程和哈希建表的过程基本一致。 给定K值，根据建表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方案找“下一地址” ，直到找到为止。

8. 理解哈希表

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。
  
 什么是Hash
   Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
  
 HASH主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系。
  
 数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：
  
 ctdwcdjxhxbsf01
   左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
  
 元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的：
  
 1，除法散列法
   最直观的一种，上图使用的就是这种散列法，公式：
   index = value % 16
   学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。
  
 2，平方散列法
   求index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：
   index = (value * value) >> 28   （右移，除以2^28。记法：左移变大，是乘。右移变小，是除。）
   如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题，value如果很大，value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index。
  
 3，斐波那契（Fibonacci）散列法
  
 平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿value本身当作乘数呢？答案是肯定的。
  
 1，对于16位整数而言，这个乘数是40503
   2，对于32位整数而言，这个乘数是2654435769
   3，对于64位整数而言，这个乘数是11400714819323198485
  
 这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,233, 377, 610， 987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。
  
 对我们常见的32位整数而言，公式：
   index = (value * 2654435769) >> 28
  
 如果用这种斐波那契散列法的话，那上面的图就变成这样了：
  
 ctdwcdjxhxbsf02
   很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。
  
 适用范围
   快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。
  
 基本原理及要点
   hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
   碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。
  
 扩展
   d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同 时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个 位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。
  
 问题实例（海量数据处理）
   我们知道hash 表在海量数据处理中有着广泛的应用，下面，请看另一道百度面试题：
   题目：海量日志数据，提取出某日访问百度次数最多的那个IP。
   方案：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。
  
 第三部分、最快的Hash表算法
  
 接下来，咱们来具体分析一下一个最快的Hasb表算法。
   我们由一个简单的问题逐步入手：有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但…也只能如此了。
  
 最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串”压缩” 成一个整数。当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小