hash算法好坏

Ⅰ hash算法的有哪几种，优缺点，使用场景

Hash算法在信息安全方面的应用主要体现在以下的3个方面： 1）文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。

Ⅱ hash 算法

这么说吧，hash这东西啊，主要就是为了查找方便，你学过table，heap之类的么？就比方说1-20，你要查找15， 通常的方法是从1开始，1，2，3...一个一个对照过去看是不是15，然后最后15个查找时间，找到15，但是hash不同了，hash是直接找到， 比方说 ‘key’ 存在 第15的位置，那么首先通过一个hash方程对 文字进行映射，就比方说k=3,e=8,y=4, h(key)=3+8+4=15.然后算好了直接去15取这个数，一个查找时间就算出来了。而传统的 查找方法很多，你自己可以去搜索，什么merge sort 啊，quick sort啊，slection sort啊，排序查找都是一起的，搜一下就好了。。数据结构学透不易啊。慢慢来吧。。

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

    散列表（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的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。

Ⅳ hash 算法

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

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

一个优秀的 hash 算法，将能实现：

但在不同的使用场景中，如数据结构和安全领域里，其中对某一些特点会有所侧重。

对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。

SHA-256 算法输入报文的最大长度不超过2^64 bit，输入按512-bit 分组进行处理，产生的输出是一个256-bit 的报文摘要。

Ⅳ 到底什么是hash呢

Hash算法在信息安全方面的应用主要体现在以下的3个方面:
(1)文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
(2)数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

Ⅵ 哈希表算法的哈希表的优缺点

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

Ⅶ hash算法什么时候学

什么时候都可以学。
Hash算法可以将一个数据转换为一个标志，这个标志和源数据的每一个字节都有十分紧密的关系。Hash算法还具有一个特点，就是很难找到逆向规律。
Hash算法是一个广义的算法，也可以认为是一种思想，使用Hash算法可以提高存储空间的利用率，可以提高数据的查询效率，也可以做数字签名来保障数据传递的安全性。所以Hash算法被广泛地应用在互联网应用中。[1]
Hash算法也被称为散列算法，Hash算法虽然被称为算法，但实际上它更像是一种思想。Hash算法没有一个固定的公式，只要符合散列思想的算法都可以被称为是Hash算法。[2]

Ⅷ 帮忙解释一下hash算法

hash算法是一种加密算法，是一种不可逆的算法，无论数据的大小、长短只要经过hash加密就会得到一个128位的字符串。广义上理解和应用就是：A计算机需要发送数据data1到B计算机，这时A就用hash算法加密data1得到一个128位的数据并发送给B计算机，同时A也会把原始的没有加密的数据data1发送给B，B计算机同时也有一套hash算法的机制，B会把得到的data1+hash=128位字符与A发送过来的128位字符做比较，以效验数据在传输过程有没有被sniffer篡改。
这只是我粗浅的理解。

Ⅸ hash算法是怎么样的

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

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

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

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

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