Hash算法只是一个定义，并没有规定具体的实现
简述
把任意长度的输入，通过Hash算法变换成固定长度的输出，这个输出就是Hash值。哈希值的空间远小于输入的空间，所以可能会发生“哈希碰撞”，即两个不同的输入，产生了同一个输出。Hash算法常用于消息摘要的场景 MD5、SHA都属于Hash算法的实现。
简单使用
凡是涉及到分布式的系统，就会有负载均衡和数据分布的问题。为了让连接（或者数据）能够分布得更均匀，很多时候会使用到Hash算法
- Hash取模 (hash(request) % n)
假设我们现在有3个服务器，想要做负载均衡，就可以对请求的ip地址或者用户的id等使用Hash函数，然后将计算得出的Hash值对3取模，余数为几，就把请求分配到相应的服务器上
缺点：如果新增服务器的时候，绝大多数请求基本上都需要重新映射到另一个节点。这种变动有时候是不能接受的。比如在Web负载均衡的场景下，session会保存在每个节点里。当然，如果你是“无状态”的服务，那不会存在这个问题。因为如果增加或者删除了一个节点，就会导致几乎所有的数据都需要重新迁移。 - 一致性Hash
优点：解决因为横向伸缩导致的大规模数据变动
上面说到用节点的数量作为除数去求余。而一致性Hash的除数是232。从0到232 – 1,首尾相连构成了一个环。我们先对服务器节点的IP进行Hash，然后除以2^32
得到服务器节点在这个Hash环中的位置。如果有请求进来了，同样进行Hash然后处于2^32求余。如果落在Hash环上，然后顺时针找到第一个节点，这个节点就负责处理这个请求。一致性Hash算法在节点数量较少的时候，会出现分布不均匀的问题
。解决这个问题的方案就是在Hash环上增加虚拟节点
哈希表简介
- 非哈希表的特点：关键字在表中的位置和它之间不存在一个确定的关系，查找的过程为给定值一次和各个关键字进行比较，查找的效率取决于和给定值进行比较的次数。
- 哈希表的特点：关键字在表中位置和它之间存在一种确定的关系。
- 哈希函数：一般情况下，需要在关键字与它在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。
- hash ：翻译为“散列”，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到莫伊固定长度的消息摘要的函数。
- hash冲突：就是根据key即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经有人先来了。这就是所谓的hash冲突啦
哈希函数处理冲突的方法
开放定址法：
其中 m 为表的长度
对增量di有三种取法
1：线性探测再散列 di = 1 , 2 , 3 , … , m-1
2：平方探测再散列 di = 1 , -1 , 2, -2 , 3 , -3 , … , k , -k(取相应数的平方)
3: 随机探测再散列 di 是一组伪随机数列
例子：
链地址法
先按照以上的hash算法：h(key) = key % 7，算出来对应的hash值，这个hash值暂时就决定，当前的这个值，存放在数组的位置。
再哈希、建立公共溢出区
建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面。
总结一下的就是下面的四行字：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/176469.html原文链接：https://javaforall.net
