hash算法冲突

Ⅰ hash算法

有一点你搞错了。Hash算法不是为了快速找出相同的元素，而是为了快速判断两个元素不相等。
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。

例如：设计一个针对字符串的Hash算法，简单地返回字符串的首字母：
def Hash_string(str):
return str[0]
那么：
Hash_string(a)=Hash(gfdgfd)=g
Hash_string(b)=Hash(xzcfs)=x

这样就可以最快速地判断出两个字符串不相等。这个Hash算法常用于将大量文件分散存储。

对于首字母相同的两个字符串，本算法得到的Hash值肯定相同，这就是出现了命中冲突。解决命中冲突有很多策略，比如：再散列法、链地址法、公共溢出法……等等。

一个好的Hash算法，应该保证高命中率和均匀分布。

Ⅱ 如何解决Hash中的冲突问题

1、开放寻址法
用开放寻址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。注意：
①用开放寻址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
按照形成探查序列的方法不同，可将开放寻址法区分为线性探查法、线性补偿探测法、随机探测等。
（1）线性探查法(Linear Probing)
该方法的基本思想是：
将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到 T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
hi=(h(key)+i)％m 0≤i≤m-1 //即di=i
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。
（2）线性补偿探测法
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。 2、拉链法
（1）拉链法解决冲突的方法
拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数 组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：

（2）拉链法的优点
与开放寻址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放寻址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

（3）拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放寻址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放寻址法中的冲突，从而提高平均查找速度。

Ⅲ 什么是哈希冲突

哈希计算就是努力的把比较大的数据存放到相对较小的空间中。
最常见的哈希算法是取模法。
下面简单讲讲取模法的计算过程。
比如：数组的长度是5。这时有一个数据是6。那么如何把这个
6存放到长度只有5的数组中呢。按照取模法，计算
6％5，结果是1，那么就把6放到数组下标是1的位置。那么，7
就应该放到2这个位置。到此位置，哈斯冲突还没有出现。
这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么
原来数组下标是1的地方已经有数了，是6。这时又计算出1这个
位置，那么数组1这个位置，就必须储存两个数了。这时，就叫
哈希冲突。冲突之后就要按照顺序来存放了。
如果数据的分布比较广泛，而且储存数据的数组长度比较大。
那么哈希冲突就比较少。否则冲突是很高的。
具体的算法你要参照更加专业的书籍。
希望对你有帮助。

Ⅳ hash算法不发生冲突的概率

hash算法的发生冲突的概率较小。由于hash的原理是将输入空间的值映射成hash空间内,而hash值的空间远小于输入的空间。

Ⅳ hash算法是什么

Hash，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

使用哈希查找有两个步骤：

1、使用哈希函数将被查找的键转换为数组的索引。在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突。

2、处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法，本文后面会介绍拉链法和线性探测法。

Ⅵ 哈希值为什么会冲突

1、哈希就是做一个映射,为的是查找快.冲突是zd因为映射毕竟是有一个范围的,这个范围可能会小于你原来的那个范围,所以可能好多个值映射了之后成为一个值了.
举例来说,可能希望查版找字符串比较快,你会用一种计算方法将一个字符串权映射为一个整数,而且要求这个数字在100以内.那么如果处理了10000个字符串,他们映射的值肯定会冲突.

2、hash：hashing定义了一种百将字符组成的字符串转换为固定长度度(一般是更短长度)的数值或索引值的方法，称为问散列法，也叫哈希法。
冲突：两个不同的关答键字，由于散列函数值相同，因而被内映射到同一表位置上。该容现象称为冲突(collision)或碰撞。

3、哈希计算就是努力的把比较大的数据存放到相百对较小的空间中。
最常见的哈希算法是取模法。
下面简单讲讲取模法的计算过程。
比如：数组的长度是5。这时有度一个数据是6。那么如何把这个
6存放到长度只有5的数组中呢。按照取模法，计算
6％5，结果是1，那么就把6放到数组下标是1的位问置。那么，7
就应该放到2这个位置。到此位置，哈希冲突还没有出现。
这时，有个数据是11，按照取模法，11％5＝1，也等于1。那么
原来数组下标是1的地方已经有数了答，是6。这时又计算出1这个
位置，那么数组1这个位置，就回必须储存两个数了。这时，就叫
哈希答冲突。冲突之后就要按照顺序来存放了。
如果数据的分布比较广泛，而且储存数据的数组长度比较大。
那么哈希冲突就比较少。否则冲突是很高的。
具体的算法你要参照更加专业的书籍。
希望对你有帮助。
出自：网络知道

Ⅶ redis使用什么算法来解决hash冲突

因为Memcached的哈希策略是在其客户端实现的，因此不同的客户端实现也有区别，以Spymemcache、Xmemcache为例，都是使用了KETAMA作为其实现。
因此，我们也可以使用一致性hash算法来解决Redis分布式这个问题。在介绍一致性hash算法之前，先介绍一下我之前想的一个方法，怎么把Key均匀的映射到多台Redis Server上。

Ⅷ 解决hash冲突的三个方法

通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：

开放寻址法

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

线性探测再散列

这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

二次探测再散列

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

伪随机探测再散列

具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。

如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。

如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

再哈希法

这种方法是同时构造多个不同的哈希函数：

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

优缺点

开放散列（open hashing）/ 拉链法（针对桶链结构）

优点：

缺点：

封闭散列（closed hashing）/ 开放寻址法

优点：

缺点：

Ⅸ hash冲突的方法

当冲突发生后，直接去下一个位置找是否存在没用的位置，例如2位置发生冲突，然后去下一位置3查找，如果3也被占用，去找4，直到问题解决

未发生冲突前

直到现在2插入，发现2位置上上是5，已经有值，所以去找下一个发现没有了，紧接着直接扩容和线性探测

后面4插入时，先去看1，发现有1，看2发现有5，看3发现有2，扩容插入4

可以看到非常容易产生一次聚类

以上为例：
当2发现发生冲突时直接每次增长i^2 倍，即2（hash值）+（-） i^2

当4发生冲突，先是寻找2（1+1^2）再寻找5（1+ 2^2）

发生冲突：如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3 + 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元

这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

在我hashcode的后面建立一个链表，每一个链表表示现在hashcode为当前的所有元素
但是这个方法很容易就造成链表的长度过大，在访问时候可能会时间很长，
所有适时的要增大数组的长度。来换取链表的长度
例如上面是mod3，我们可以mod5

什么时候扩容？
“我们可以定义这样一个变量 α = 所有元素个数/数组的大小，我们叫它装载因子吧，它代表着我们的Hash表（也就是数组）的装满程度，在这里也代表链表的平均长度
例如上面的 数组{5,1,3,2,4} 当取mod3时候就是 α = 5%3，这时候我们扩容
即使Hash函数设计的合理，基本上每次存放元素的时候就会冲突，所以鉴于两者之间我觉得 0.6 - 0.9 之间是一个不错的选择，不妨选0.75吧”
参考： https://cloud.tencent.com/developer/article/1361248