解决哈希冲突(四种方法) | 您所在的位置:网站首页 › 综合日语第四册教师用书百度云 › 解决哈希冲突(四种方法) |
目录 一、了解哈希表及哈希冲突 二、解决哈希冲突办法 1、开放定址法:我们在遇到哈希冲突时,去寻找一个新的空闲的哈希地址。 (1)线性探测法 (2)平方探测法(二次探测) 2、再哈希法 3、链地址法:将所有哈希地址相同的记录都链接在同一链表中。 4、建立公共溢出区:将哈希表分为基本表和溢出表,将发生冲突的都存放在溢出表中。 一、了解哈希表及哈希冲突哈希表:是一种实现关联数组抽象数据类型的数据结构,这种结构可以将关键码映射到给定值。简单来说哈希表(key-value)之间存在一个映射关系,是键值对的关系,一个键对应一个值。 哈希冲突:当两个不同的数经过哈希函数计算后得到了同一个结果,即他们会被映射到哈希表的同一个位置时,即称为发生了哈希冲突。简单来说就是哈希函数算出来的地址被别的元素占用了。 二、解决哈希冲突办法 1、开放定址法:我们在遇到哈希冲突时,去寻找一个新的空闲的哈希地址。举例:就是当我们去教室上课,发现该位置已经存在人了,所以我们应该寻找新的位子坐下,这就是开放定址法的思路。如何寻找新的位置就通过以下几种方法实现。 (1)线性探测法当我们的所需要存放值的位置被占了,我们就往后面一直加1并对m取模直到存在一个空余的地址供我们存放值,取模是为了保证找到的位置在0~m-1的有效空间之中。 公式:h(x)=(Hash(x)+i)mod (Hashtable.length);(i会逐渐递增加1) 举例: 存在问题:出现非同义词冲突(两个不想同的哈希值,抢占同一个后续的哈希地址)被称为堆积或聚集现象。 (2)平方探测法(二次探测)当我们的所需要存放值的位置被占了,会前后寻找而不是单独方向的寻找。 公式:h(x)=(Hash(x) +i)mod (Hashtable.length);(i依次为+(i^2)和-(i^2)) 举例: 公式:h(x)=xmod(Hashtable.length); 4、建立公共溢出区:将哈希表分为基本表和溢出表,将发生冲突的都存放在溢出表中。 |
CopyRight 2018-2019 实验室设备网 版权所有 |