数据结构-4.ppt

* 与顺序表比较 * * * 第六讲： 散列表 林梦香 北京航空航天大学 2009年10月 计算机软件技术基础 还可以怎么存储 线性表？ 第二章 线性表 线性表定义及操作 顺序表及操作 单链表及操作 双链表及操作 散列（hash）表及操作 散列（Hash）表 散列法是线性表的一种重要存储方式; Addr = H（key） 用散列法存储的线性表称为散列表。 散列函数 key H（） H（key） 数据元素的关键字 内存地址 线性表 散列表 散列表的例子 例1：线性表：n＝70，关键字KEY为两位十进制数。 散列表： Int HT[100]； 散列函数： H(KEY)=KEY 例2：线性表关键字集合为： KEY={an,bee,do,end,for,if,red,the,who} 散列表：char HT[26][8]; 散列函数： H(KEY)=KEY[0]-’a’ 例3:KEY={an,bee,do,end,for,if,red,the,who,and} 采用与例2相同的散列函数－》冲突 散列表的设计 确定散列表的空间 一般地，散列表的空间(m)比线性表的 表长(n)大：a=n/m. a 称为装填因子，一般为(0.65－0.9) 构造散列函数H（key）； Addr = H（key） 设计冲突处理策略； 对不同的关键字得到相同的散列地址的现象叫冲突； 散列函数 建立散列函数的原则 均匀性：H(key)的值均匀分布在 散列表中； 简单： 以提高地址计算的速度。 散列函数构造方法 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 散列函数构造－直接定址法 取关键字或关键字的某个线性函数值为散列地址，即： H（key） = key H（key） = a * key + b （a，b为常数） 例如 ： 解放后出生人口统计表中，年份作为关键字，散列函数取为： H（key）= key +（ -1948） 地址 年份 人数 01 02 42 1949 1950 1990 ….. ….. 43 1991 3000 3500 2500 2300 ….. 散列函数构造－数字选择法 当关键字的位数比散列表地址的位数多时，可合理选择关键字的某几位组成的散列地址。取的位数由散列表长决定。 例如： 关键字 散列地址（0－999） 465 723 874 013 228 339 适用条件：预先知道所有关键字的每一位数字分布情况。 散列函数构造－平方取中法 取关键字平方后的中间几位为散列地址。这是一种较常用的构造散列函数的方法。 一般情况，取一个数平方后的中间几位数作散列地址。取的位数由表长决定。 例如，3288，平方后是，取后4位为散列地址，即“0944”。 适用条件：不知道关键字的全部情况，取其中的哪几位也不合适的情况。 散列函数构造－折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。 关键字位数很多，且每一位上数字分布大致均匀时，可采用折叠法。 散列函数构造－除留余数法 取关键字被某个不大于散列表表长m的数p除后所得余数为散列地址。 H（key） = key MOD p 最简单、最常用的构造散列函数的方法。 例如：关键字，散列表长为10000，P值可取5000； H（KEY）=MOD 5000 = 4872 由经验得知： 通常选p为小于散列表长的最大素数。 散列函数选择标准 散列函数计算所需要的时间 关键字的长度 散列表的长度 关键字的分布情况 记录的查找频率 冲突及冲突处理 在散列元素（地址）求解过程中，不同关键字值对应到同一个存储地址的现象称为冲突。即关键字K1 ? K2， 但散列函数值 H（K1）= H（K2）。 均匀的散列函数可以减少冲突，但不能避免冲突。发生冲突后，必须寻找下一个可用地址。 处