二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(19)

例如，若设定存放表的区域范围为0～33 m-1 ，我们可以考虑按如下方法来设立两个散列函数h1和h2：⑴ h1取关键字中第一个字母在字母表中的序号作为散列函数值。如h1 BEIJING 2。⑵ h2取关键字的第一个和最后一个字母在字母表中的序号之和，若大于等于34，则减去34。如：YUNNAN 云南 的首尾两个字母Y和N的序号之和为39，减去34后得到的散列函数值为05，即h2 YUNNAN 05。上述人口统计表中部分关键字在两种不同散列函数情况下的散列函数值如表9.1所示。从这个例子可以看出：⑴ 散列函数是一个映射，因此散列函数的设定很灵活，英文单词hash 哈希 就是“杂凑”的意思。因此，只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可。⑵ 对不同的关键字可能得到同一哈希地址，即keyi ≠ keyj，但h keyi h keyj ，这种现象称为冲突 collision ，也称为碰撞。具有相同函数值的关键字称为同义词 synonym 。比如上例中，就有冲突现象发生。例如，关键字SHANGHAI和SHANXI不等，但有h1 SHANGHAI h1 SHANXI 。

在此例中还有关键字XINJIANG和XIZANG不等，但有h1 SHANGHAI h1 SHANXI 。对于散列函数h2也是如此。存在这种情况就意味着要把关键字不同的记录存放在以同一函数值为地址的位置上。显然这种现象是我们不希望出现的，应尽量地避免。当然，对于上例，只可能有34个记录，而且事先全部为已知，所以可以通过认真分析这34个关键字的特性，设计出一个恰当的散列函数来避免冲突的发生。然而，在一般情况下，冲突只能尽量地减少，而不可能完全避免。因为，散列函数是从可能的关键字集合到地址集合的映射，通常关键字集合相当大，它的元素包括了所有可能出现的关键字；而地址集合仅为散列表中的地址值，对应于内存的一片有限的存储区域 假设散列表的长度为m，散列地址为0 ～ m-1 ，因此，它的大小是很有限的。下面通过一个例子来说明这个问题。例9.20 假设C语言的编译程序需要对源程序中的标识符建立一张散列表。在设定散列函数时考虑的关键字应包含所有可能产生的关键字。假设标识符定义为字母开头的长度不超过8的字母、数字串，则关键字 标识符 的集合大小为52 + 52×621 + 52×622 + … + 52×62 7≈ 1.86126 × 1014≈ 186多万亿而在一个源程序中出现的标识符总是有限的，一般设表长为1000也就足够了。

这样，地址集合可设为0 ～ 999。从这个例子可以看到可能的关键字集合与要映射到的地址集合两者之间在容量上的差异是非常之大的。因此，在一般情况下，散列函数是一个压缩映像，这就不可避免会产生冲突 碰撞 。在散列存储中，虽然冲突难以避免，但发生冲突的可能性却有大有小。与之相关的一个重要参数就是负载因子 load factor ，也称为装填因子，它定义为负载因子的大小对于冲突的发生频率影响很大。直观上容易想象，散列表装得越满，则再装入新的结点时，与已有结点碰撞的可能性就越大。特别当α 1时，碰撞 冲突 是不可避免的，一般总取α 1。即分配给散列表的基本区域大于所有结点所需要的空间。α的选取要适当，因为，α取值越小，散列表中空闲单元的比例就越大，再存入结点时虽然能减少碰撞的可能性，但存储空间的利用率也随之降低。反之，α取值过大，虽然能提高存储空间的利用率，但却增加了碰撞的可能性。因此,α的选取要兼顾减少碰撞和提高存储空间的利用率这两个方面。一般α的取值控制在0.6 ～ 0.9之间为宜。下面要讨论两个问题：一是如何选取好的散列函数，使得冲突 碰撞 尽可能的少；二是既然冲突不可完全避免，那么冲突发生时怎样来处理，即要研究解决冲突的办法。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-19.html