3.2.2几种常用ash表 1.线性HaSh表 设线性Hash表的长度为n,对线性 Hash表的查找过程如下。 (1)线性Hash表的填入 (2)线性Hash表的取出 PT PRESS 单击鼠标左键换页
3.2.2 几种常用的Hash表 1．线性Hash表 设线性Hash表的长度为n，对线性 Hash表的查找过程如下。 （1）线性Hash表的填入 （2）线性Hash表的取出
线性Hash表的优点是简单,但它有以 下两个主要缺点。 当Hash码的冲突较多时,在线性Hash 表中会存在“堆聚”现象,即许多关键字 被连续登记在一起,从而会降低查找效率。 PT PRESS 单击鼠标左键换页
线性Hash表的优点是简单，但它有以 下两个主要缺点。 当Hash码的冲突较多时，在线性Hash 表中会存在“堆聚”现象，即许多关键字 被连续登记在一起，从而会降低查找效率
2.随机HaSh表 当Hash表的长度n设计成n=2时,还 可以定义另外一种Hash表随机Hash 表 随机Hash表的填入与取出的过程。 (1)随机Hh表的填入 (2)随机Hh表的取出 PT PRESS 单击鼠标左键换页
2．随机Hash表 当Hash表的长度n设计成n = 2k时，还 可以定义另外一种Hash表——随机Hash 表。 随机Hash表的填入与取出的过程。 （1）随机Hash表的填入 （2）随机Hash表的取出
表33 随机Hash表的填入 表项序号12345678910111213141516 关键字k01020509131619 a12611 31 27 冲突次数01 00000020 2 PT PRESS 单击鼠标左键换页
3.溢出ⅢaSh表 前面所介绍的线性Hash表与随机Hash 表均存在两个致命的缺点:一是在HaSh表 填入过程中不顾后效,从而在填入过程中 其冲突的机会在不断增多;二是当Hash表 填满时,不能正常地进行查找。 PT PRESS 单击鼠标左键换页
3．溢出Hash表 前面所介绍的线性Hash表与随机Hash 表均存在两个致命的缺点：一是在Hash表 填入过程中不顾后效，从而在填入过程中 其冲突的机会在不断增多；二是当Hash表 填满时，不能正常地进行查找