哈希算法排行

① 桶排序与哈希桶排序

桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面，然后对每个桶再分别排序（帆禅咐可以使用其它的排序算法或者是递归使用桶排序算法），最后将各个桶中的数据有序的合并起来成为一个整体有序的序列。
排序过程：
1.假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2.将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3.将各个桶中的数据有序的合并起来

设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那么数组中最大数为 49，先设置 5 个桶，那么每个桶可存放数的范围为：09、1019、2029、3039、40~49，然后分别将这些数放人自己所属的桶，如下图：

1.时间复杂度：O(m+n)
2.空间复杂度：O(m+n)

适用于序列比较均匀的情况，否则会很耗空间。
或者特殊的场景，例如需要对一个公司的员工的年龄进行排序，年龄的范围为1-120，此时就可以开辟120个桶进行统计排序。
另，桶排序的瓶颈主要是桶数量的选择。
另此算法为稳定的排序算法。

排序算法主要是用分治法，用哈希函数对序列进行划分，最后使用其它的排序算法或者递归使用哈希排序进行排序从而得到一个整体有序的序列。下面先介绍几个自定义的概念：
1.哈希桶排序：因为本算法是使用了哈希函数把序列划分到对应的桶里面，所以本排序算法取名为哈希桶排序。
2.哈希桶因子（hashFactor）：hashFactor = （max - min） / length
计算公式如上式，当结果小于等于0的时候再做特殊处理，据此因子进行桶的划分。

设有数组 array = [10011, 10001, 16, 14, 12, 10000, 10, 10002, 10003, 1]，那么数组中最大值max = 10011，最小值min = 1，哈希桶因子hashFactor = （10011 - 1） / 10 = 1001。对数组进行划分，10011 / 1001 = 10，所以10011放在keywei10的桶里面；10001 / 1001 = 9， 所以10001放在key为9的桶里面，以此类推，最后得到的桶态纯的情况为：{0=[1, 10, 12, 14, 16], 9=[10000, 10001, 10002, 10003], 10=[10011]}。再分别对每个桶进行排序即可。

1.时间复杂度：O(m+n)
2.空间复杂度：O(m+n)

此算法与桶排序对比，主要是通过哈希建桶的方式减少了空间的消耗，对序列进行了一个归约袭伍，时间上跟桶排序相当。
使用与序列的最小最大值相差比较大同时又出现在某一个取值区间的集聚的情况。
另此算法为稳定的排序算法。

② 大数据最常用的算法有哪些

奥地利符号计算研究所(Research Institute for Symbolic Computation，简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章，提到他做了一个调查，参与者大多数是计算机科学家，他请这些科学家投票选出最重要的算法，以下是这次调查的结果，按照英文名称字母顺序排序。

大数据等最核心的关键技术：32个算法

1、A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。

2、集束搜索(又名定向搜索，Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案，使用更少的字节数(或是其他信息承载单元)对信息编码的过程，又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法

11、欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。

12、期望-最大算法(Expectation-maximization algorithm，又名EM-Training)——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值;第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。

13、快速傅里叶变换(Fast Fourier transform，FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

15、哈希算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。

18、LLL算法(Lenstra-Lenstra-Lovasz lattice rection)——以格规约(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统(knapsack)、有特定设置的RSA加密等等。

19、最大流量算法(Maximum flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

20、合并排序(Merge Sort)。

21、牛顿法(Newton’s method)——求非线性方程(组)零点的一种重要的迭代法。

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。

23、两次筛法(Quadratic Sieve)——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。

24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。

26、Sch?nhage-Strassen算法——在数学中，Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。

27、单纯型算法(Simplex Algorithm)——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化(或最小化)的固定线性函数。

28、奇异值分解(Singular value decomposition，简称SVD)——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。

29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法(Gauss-Jordan elimination)，或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域( homogenous region)，看看它是否属于边缘，还是是一个顶点。

31、合并查找算法(Union-find)——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：

查找：判断某特定元素属于哪个组。

合并：联合或合并两个组为一个组。

32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

以上就是Christoph博士对于最重要的算法的调查结果。你们熟悉哪些算法?又有哪些算法是你们经常使用的?

③ 哈希加密算法

MD5即Message-Digest Algorithm 5（信息摘要算法5），是计算机广泛使用的散列算法之一。经MD2、MD3和MD4发展而来，诞生于20世纪90年代初。用于确保信息传输完整一致。虽然已被破解，但仍然具有较好的安全性，加之可以免费使用，所以仍广泛运用于数字签名、文件完整性验证以及口令加密等领域。

算法原理：

散列算法得到的结果位数是有限的，比如MD5算法计算出的结果字长为128位，意味着只要我们穷举2^128次，就肯定能得到一组碰撞，下面让我们来看看一个真实的碰撞案例。我们之所以说MD5过时，是因为它在某些时候已经很难表现出散列算法的某些优势——比如在应对文件的微小修改时，散列算法得到的指纹结果应当有显着的不同，而下面的程序说明了MD5并不能实现这一点。

而诸如此类的碰撞案例还有很多，上面只是原始文件相对较小的一个例子。事实上现在我们用智能手机只要数秒就能找到MD5的一个碰撞案例，因此，MD5在数年前就已经不被推荐作为应用中的散列算法方案，取代它的是SHA家族算法，也就是安全散列算法（Secure Hash Algorithm，缩写为SHA）。

SHA实际包括有一系列算法，分别是SHA-1、SHA-224、SHA-256、SHA-384以及SHA-512。而我们所说的SHA2实际是对后面4中的统称。各种SHA算法的数据比较如下表，其中的长度单位均为位：

MD5和SHA1，它们都有4个逻辑函数，而在SHA2的一系列算法中都采用了6个逻辑函数。
以SHA-1为例，算法包括有如下的处理过程：

和MD5处理输入方式相同

经过添加位数处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组，可以得到一定数量的明文分组，我们用Y ₀ ，Y ₁ ，……Y _N-1 表示这些明文分组。对于每一个明文分组，都要重复反复的处理，这些与MD5都是相同的。

而对于每个512位的明文分组，SHA1将其再分成16份更小的明文分组，称为子明文分组，每个子明文分组为32位，我们且使用M[t]（t= 0, 1,……15）来表示这16个子明文分组。然后需要将这16个子明文分组扩充到80个子明文分组，我们将其记为W[t]（t= 0, 1,……79），扩充的具体方法是：当0≤t≤15时，Wt = Mt；当16≤t≤79时，Wt = ( W _t-3 ⊕ W _t-8 ⊕ W _t-14 ⊕ W _t-16 ) <<< 1，从而得到80个子明文分组。

所谓初始化缓存就是为链接变量赋初值。前面我们实现MD5算法时，说过由于摘要是128位，以32位为计算单位，所以需要4个链接变量。同样SHA-1采用160位的信息摘要，也以32位为计算长度，就需要5个链接变量。我们记为A、B、C、D、E。其初始赋值分别为：A = 0x67452301、B = 0xEFCDAB89、C = 0x98BADCFE、D = 0x10325476、E = 0xC3D2E1F0。

如果我们对比前面说过的MD5算法就会发现，前4个链接变量的初始值是一样的，因为它们本来就是同源的。

经过前面的准备，接下来就是计算信息摘要了。SHA1有4轮运算，每一轮包括20个步骤，一共80步，最终产生160位的信息摘要，这160位的摘要存放在5个32位的链接变量中。

在SHA1的4论运算中，虽然进行的就具体操作函数不同，但逻辑过程却是一致的。首先，定义5个变量，假设为H0、H1、H2、H3、H4，对其分别进行如下操作：

（A）、将A左移5为与 函数的结果求和，再与对应的子明文分组、E以及计算常数求和后的结果赋予H0。

（B）、将A的值赋予H1。

（C）、将B左移30位，并赋予H2。

（D）、将C的值赋予H3。

（E）、将D的值赋予H4。

（F）、最后将H0、H1、H2、H3、H4的值分别赋予A、B、C、D

这一过程表示如下：

而在4轮80步的计算中使用到的函数和固定常数如下表所示：

经过4轮80步计算后得到的结果，再与各链接变量的初始值求和，就得到了我们最终的信息摘要。而对于有多个明文分组的，则将前面所得到的结果作为初始值进行下一明文分组的计算，最终计算全部的明文分组就得到了最终的结果。

④ 一致性hash算法，采用哪种算法实现比较好，比如MD5，CRC32，或者其它

环割法（一致性 hash）环割法的原理如下：

1. 初始化的时候生成分片数量 X × 环割数量 N 的固定方式编号的字符串，例如 SHARD-1-NODE-1，并计算所有 X×N 个字符串的所有 hash 值。

2. 将所有计算出来的 hash 值放到一个排序的 Map 中，并将其中的所有元素进行排序。

3. 输入字符串的时候计算输入字符串的 hash 值，查看 hash 值介于哪两个元素之间，取小于 hash 值的那个元素对应的分片为数据的分片。

数据比较

下面将通过测试对环割法和跳跃法的性能及均衡性进行对比，说明 DBLE 为何使用跳跃法代替了环割法。

• 数据源：现场数据 350595 条

• 测试经过：

  1. 通过各自的测试方法执行对于测试数据的分片任务。

  2. 测试方法：记录分片结果的方差；记录从开始分片至分片结束的时间；记录分片结果与平均数的最大差值。

  3. 由于在求模法 PartitionByString 的方法中要求分片的数量是 1024 的因数，所以测试过程只能使用 2 的指数形式进行测试，并在 PartitionByString 方法进行测试的时候不对于 MAC 地址进行截断，取全量长度进行测试。

⑤ 常见的哈希算法有哪些

1.linear hash 线性
2.quadratic hash 每次以1,4,9,16这样的幅度向下找
3.double hash 用两个函数一起决定HASH的index

⑥ 哈希表与哈希（Hash）算法

根据设定的 哈希函数H（key） 和 处理冲突的方法 将一组关键字影像到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便成为 哈希表 ，这一映像过程称为哈希造表或 散列 ，所得存储位置称 哈希地址 或 散列地址 。

上面所提到的 哈希函数 是指：有一个对应关系 f ，使得每个关键字和结构中一个唯一的存储位置相对应，这样在查找时，我们不需要像传统的烂码查找算法那样进行比较，而是根据这个对应关系 f 找到给定值K的像 f（K） 。

哈希函数也可叫哈希算法，它可以用于检验信息是否相同（ 文件校验 ），或兆历裤者检验信息的拥有者是否真实（ 数字签名 ）。

下面分别就哈希函数和族简处理冲突的方法进行讨论;

构造哈希函数的方法有很多。在介绍各种方法前，首先需要明确什么是“好” 的哈希算法。若对于关键字集合中的任一个关键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称此类哈希函数是 均匀的 （Uniform）哈希函数。换句话说，就是使关键字经过哈希函数得到一个“随机的地址”，以便使一组关键字的哈希地址均匀分布在整个地址区间中，从而减少冲突。
常用的构造哈希函数的方法有：

理论研究表明， 除留余数法的模 p 取不大于表长且最接近表长 m 的素数效果最好，且 p 最好取1.1 ⁿ ~ 1.7 ⁿ 之间的一个素数（n为存在的数据元素个数） 。

以上便是常用的6种构造哈希函数的方法，实际工作中需视不同的情况采用采用不同的哈希函数，通常考虑的因素有：

前面有提到过 均匀的哈希函数可以减少冲突，但不能避免 ，因此，如何处理冲突是哈希造表不可缺少的另一方面。

通常用的处理冲突的方法有下列几种：

在哈希表上进行查找的过程和哈希建表的过程基本一致。 给定K值，根据建表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方案找“下一地址” ，直到找到为止。