由数组的直接寻址想到的 散列基本思想 例如,读取指定下标的数组元 一个确定的函数关系h 以结点的关键码K为自变量 函数值h(K作为结点的存储地址 与数组元囊个数的规模n无关 ■检索时也是根据这个函数计算其存储位 猫经楼 通常散列表的存储空间是一个一维数组 种重要的存储方法 散列地址是数组的下标 也是一种常见的检索方法 叔新有,盘 张 列盐类膏 散列地她类萄码 例子1 例91:已知线性表关健码集合为 S=iand, begin, do, end, for, go, if, repeat, then, until, while 可设散列表为 char HT2 26I8I 散列函数H(key)的值,取为关健码key中的 个字母在字母表{a,b,c,….x}中的序 订恤 张铝 张帖 歡列地址关健码 歐列地址关管码 例子2 例92:在集合S中增加4个关健码,集合S1=S+ 要修改散列函数:散列函数的值为key中首尾字 母表中序号的平均值,即 学恤息 权新有,种7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 由数组的直接寻址想到的 „ 例如，读取指定下标的数组元 素 „ 根据数组的起始存储地址、以及 数组下标值而直接计算出来的， 所花费的时间是O(1) „ 与数组元素个数的规模n无关 „ 受此启发，计算机科学家发明 了散列方法（Hash, 有人称“哈 希”，还有称“杂凑”）散列是一 种重要的存储方法 „ 也是一种常见的检索方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 散列基本思想 „ 一个确定的函数关系h „ 以结点的关键码K为自变量 „ 函数值h(K)作为结点的存储地址 „ 检索时也是根据这个函数计算其存储位 置 „ 通常散列表的存储空间是一个一维数组 „ 散列地址是数组的下标 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 例子1 例9.1：已知线性表关键码集合为： S = { and, begin, do, end, for, go, if, repeat, then, until, while} 可设散列表为： char HT2[26][8]; 散列函数H(key)的值，取为关键码key中的第一 个字母在字母表{a, b, c, ..., z}中的序号，即： H(key)=key[0] – ‘a’ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 例 子 1表 散列地址 关键码 散列地址 关键码 0 and (array) 13 1 begin 14 2 15 3 do 16 4 end (else) 17 repeat 5 for 18 6 go 19 then 7 20 u ntil 8 if 21 9 22 w hile (w ith) 10 23 11 24 1 2 2 5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 例子2 例9.2：在集合S中增加4个关键码，集合S1 = S + { else, array, with, up} 要修改散列函数：散列函数的值为key中首尾字 母在字母表中序号的平均值，即： int H3(key) char key[]; int i; { i = 0; while ((i<8) && (key[i]!=‘\0’)) i++; return((key[0] + key(i-1) – 2*’a’) /2 ) } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 例 子 2表 散列地址 关键码 散列地址 关键码 0 13 w hile 1 and 14 w ith 2 15 until 3 end 16 then 4 else 17 5 18 repeat 6 if 19 7 begin 20 8 do 21 9 22 10 go 23 11 for 24 1 2 arra y 2 5