补充资料：散列算法

散列算法
hashing algorithms

50门{IeS日onfo散yJJ算法(hashing algorithms)一种建表和查表的算法。设表中元素取自集合U，采用散列法建表的方法是:构造一个映射h，使u二(0，1，一，n一1)。建立一个大小为n的数组HT，称为散列表。h(a)即为元素a任U存放在散列表中的地址。 散列法常用于U很大而n较小且动态建表的场合。例如在FORTRAN语言中大约有1.62xl。”个可能的标识符，而在一特定程序中使用的标识符仅为几十至几百个，可依此确定散列表的大小。显然，h可能会将U中不同元素映射到同一地址，从而产生冲突。解决冲突的方法通常有两种:①链表:HT的数组元素是指向链表的指针，具有相同映射值的元素置于同一地址的链表中;②使用一映射序列，若地址h(a)已有元素存在其中，则顺次计算其他映射，直至可存放为止。若整个散列表已存满，再存放元素时就要产生溢出，此时可使用再散列技术把表扩大。 散列函数即映射h。对它的主要要求是U中元素能比较均匀地分布在数组中。选择适当的正整数M(例如素数)，h(a)一amodM就是一种简单而有效的散列函数。 删除表中元素是建表的逆过程。若要在非链地址处理冲突的散列表中删除一个记录，则需在该记录的位置上填人一个特殊的符号，以免找不到在它之后填人的与它相同映射的元素。采用散列技术可以缩短查表时间。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。