2.Hash表 Hash表技术是直接查找技术的推广 其主要目标是提高查找效率。 如果按照直接査找表的填入方法,填 入结果如表31所示。 表3.1 直接查找表的填入 表项序号 1234567「8「9|101112 按I=INT门)+1 02*05 13 2325*27*31*35 填入的关键字k 09 18 PT PRESS 单击鼠标左键换页
2．Hash表 Hash表技术是直接查找技术的推广， 其主要目标是提高查找效率。 如果按照直接查找表的填入方法，填 入结果如表3.1所示
设表的长度为n 如果存在一个函数i=i(k),对于 表中的任意一个元素的关键字k,满 足1<还n,则称此表为Hash表 其中函数i=i(k)称为关键字的 Hash码。 PT PRESS 单击鼠标左键换页
设表的长度为n。 如果存在一个函数i = i(k)，对于 表中的任意一个元素的关键字k，满 足1≤i≤n，则称此表为Hash表。 其中函数i = i(k)称为关键字k的 Hash码
Hash表技术的关键是要处理好表中元 素的冲突问题,它主要包括以下两方面的 工作: (1)构造合适的Hash码,以便尽量 减少表中元素冲突的次数。 即Hash码的均匀性要比较好。 (2)当表中元素发生冲突时,要进 行适当的处理。 PT PRESS 单击鼠标左键换页
Hash表技术的关键是要处理好表中元 素的冲突问题，它主要包括以下两方面的 工作： （1）构造合适的Hash码，以便尽量 减少表中元素冲突的次数。 即Hash码的均匀性要比较好。 （2）当表中元素发生冲突时，要进 行适当的处理
3.Hash码的构造 在实际设计HaSh码时,要考虑以下两 方面的因素: ①使各关键字尽可能均匀地分布在 Hash表中。 ②Hash码的计算要尽量简单 PT PRESS 单击鼠标左键换页
3．Hash码的构造 在实际设计Hash码时，要考虑以下两 方面的因素： ① 使各关键字尽可能均匀地分布在 Hash表中 。 ② Hash码的计算要尽量简单
比较简单的Hash码的构造方法。 (1)戴段法 (2)分股叠加法 (3)除法 (4)乘法 PT PRESS 单击鼠标左键换页
比较简单的Hash码的构造方法。 （1）截段法 （2）分段叠加法 （3）除法 （4）乘法