哈希法-哈希表介绍、构造方法、解决冲突办法
哈希法又称 散列法、杂凑法以及关键字地址计算法 等，相应的表称为 哈希表。 这种方法的 基本思想 是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f，使得p=f(k)，f称为 哈希函数 。创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。
当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1≠k2 ，但 H（k1）=H（k2），这种现象称为 冲突， 此时称k1和k2为 同义词。 实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。
综上所述，哈希法主要包括以下两方面的内容：
1）如何构造哈希函数
2）如何处理冲突。
常用五种方法：
（1） 数字分析法 ；
（2） 平方取中法
（3） 分段叠加法
（4） 除留余数法
（5） 伪随机数法
主要有以下四种方法：
（1） 开放定址法 （也称再散列法）
基本思想 ：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
（2） 再哈希法
基本思想 ：同时构造多个不同的哈希函数，当一个函数计算产生冲突时，再用另一个函数，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
（3） 链地址法
基本思想 ：将所有哈希地址为i的元素构成一个称为 同义词链 的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
（4） 建立公共溢出区
基本思想 ：将哈希表分为 基本表 和 溢出表 两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
ZESTRON
2024-09-04 广告
