如何解决hash冲突
1)冲突是如何产生的? 上文中谈到,哈希函数是指如何对关键字进行编址的规则,这里的关键字的范围很广,可视为无限集,如何保证无限集的原数据在编址的时候不会出现重复呢?规则本身无法实现这个目的。举一个例子,仍然用班级同学做比喻,现有如下同学数据
...
...
我们注意到,灰色背景标示的两行里面,关键字王五,吴露被编到了同一个位置,关键字张三,赵刚也被编到了同一个位置。老师再拿号来找张三,座位上有两个人,"你们俩谁是张三?" 2)如何解决冲突问题 既然不能避免冲突,那么如何解决冲突呢,显然需要附加的步骤。通过这些步骤,以制定更多的规则来管理关键字集合,通常的办法有: a)开放地址法 开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
赵刚未来之前
(a)线性探测再散列对赵刚进行编址,且di=1
(b)二次探测再散列,且di=-2
(c)伪随机探测再散列,伪随机序列为:5,2 b)再哈希法 当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲突时。缺点:计算时间增加。 c)链地址法 将所有关键字为同义词的记录存储在同一线性链表中。如下: 因此这种方法,可以近似的认为是筒子里面套筒子 d)建立一个公共溢出区 假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。 注:之所以会简单得介绍了hash,是为了更好的学习lzw算法,学习lzw算法是为了更好的研究gif文件结构,最后,我将详细的阐述一下gif文件是如何构成的,如何高效操作此种类型文件。 以上就是本文的全部内容,希望能给大家一个参考,也希望大家多多支持编程小技巧。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |