哈希法-哈希表介绍
哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。这种方法的基本思想是：首先在元素的关键字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）建立公共溢出区
基本思想：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
网友评论