首先说一下hash冲突吧,hash冲突在hash表中一般情况下是会遇到的; hash冲突指的是你在向hash表中存数据时,首先要通过key值进行指定的hash算法进行计算,然后得到一个值,这个值就是你要将这个key对应的value存入的地址。但是在这个地址中已经有值存在,所以这个时候就发生了hash冲突,不同的key通过hash算法得到了对应的同一个值。
hash冲突解决的方法:
二次探测再散列 di=12,-12,22,-22,…,k2,-k2 ( k<=m/2 ) 这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。
伪随机探测再散列 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号单元。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/184350.html原文链接:https://javaforall.cn