Hash算法内容整理-只有整理是原创

整理贴，供自己汇总和学习，如果能帮助到大家就更好了,本来是自己想理解了之后去写一个博客，看到大家写的已经很全面了，很难再去写什么，就把大家的内容总结汇总一下。汇总各家之长处把。

[不定时更新]

本篇的原创内容只有整理而已。所有引用的文章，会标明出处。

如果您觉得这样也是侵权的话，请您联系留言我，我尽快删除引用您博文的部分。

1、hash解释解析，以下全部来自[1]

      Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。

      这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

      所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。

两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。

2、hash计算函数，以下全部来自[1]，详解的内容请看[3]

    直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
    数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。
    除留余数法：用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。
    分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
    平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址
    伪随机数法：采用一个伪随机数当作哈希函数。

3、碰撞解决，以下全部来自[1],详解的内容请看[3]

    衡量一个哈希函数的好坏的重要指标就是发生碰撞的概率以及发生碰撞的解决方案。任何哈希函数基本都无法彻底避免碰撞，常见的解决碰撞的方法有以下几种：
    开放定址法：
        开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
    链地址法
        将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部
    再哈希法
        当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止
    建立公共溢出区
        将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中

4、Java中实现的hash表

[1]引用开始   

    在Java中，保存数据有两种比较简单的数据结构：
    数组和链表。
    数组的特点是：寻址容易，插入和删除困难；
    而链表的特点是：寻址困难，插入和删除容易。
    上面我们提到过，常用的哈希函数的冲突解决办法中有一种方法叫做链地址法，其实就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。
    jdk7中，hash的内容是，数组+链表
    进一步优化：如果恶意程序知道我们用的是Hash算法，则在纯链表情况下，它能够发送大量请求导致哈希碰撞，然后不停访问这些key导致HashMap忙于进行线性查找，最终陷入瘫痪，即形成了拒绝服务攻击（DoS）。

[1]引用结束

    jdk8内部数据结构为数组+(链表 或 红黑树)，通过key的hash值计算数据所在数组下标，多个key的hash相同或hash计算的数组下标相同，但是key值不同时，检查节点是否为树节点，是树节点则往树节点添加，如果是普通节点则往链表尾追加Entry，当链表长度大于8时，则将链表转为红黑树。引用[2]

5、常见的hash算法，以下全文来自[3]

（1) MD4

  MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。

（2) MD5

   MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好

（3) SHA-1 及其他

   SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。

6、Java8中，HashMap的内容中

      为什么loadFactor = 0.75F

     引用[4] 作为一般规则，默认负载因子（0.75）在时间和空间成本上提供了很好的折衷。较高的值会降低空间开销，但提高查找成本（体现在大多数的HashMap类的操作，包括get和put）。设置初始大小时，应该考虑预计的entry数在map及其负载系数，并且尽量减少rehash操作的次数。如果初始容量大于最大条目数除以负载因子，rehash操作将不会发生。

     引用[4]一个bucket空和非空的概率为0.5，通过牛顿二项式等数学计算，得到这个loadfactor的值为log（2），约等于0.693. 同回答者所说，可能小于0.75 大于等于log（2）的factor都能提供更好的性能，0.75这个数说不定是 pulled out of a hat

7、一致性hash算法：

     用于解决分布式集群扩展时遇到的数据失效或者数据迁移问题。

     任何hash取模定位服务器节点，服务器不可用或者增加服务器会导致新取模之后的所有数据不可用,为了解决这些问题，提出一致性hash算法。统一进行取模，取模大小为2^32

     问题：一致性hash算法会导致数据倾斜，使用虚拟节点进行解决，实际应用中虚拟节点的，为32，或者更大。

    详细解释文档：1、 什么是一致性Hash算法？

                             2、 白话解析：一致性哈希算法

写在最后，引用或者参考文献：

[1]hash算法详解 (对于hash讲解较为全面，目前推荐)

[2]jdk8 HashMap红黑树学习

[3]hash算法原理详解

[4]HashMap的loadFactor为什么是0.75？

[5] 什么是一致性Hash算法？ （详细解析一致性hash算法）

[6] 白话解析：一致性哈希算法

最后

以上就是危机小懒猪为你收集整理的Hash算法内容整理-只有整理是原创的全部内容，希望文章能够帮你解决Hash算法内容整理-只有整理是原创所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。