2005-02-03
散列 (Hashing)
在线性表、树结构中查找纪录是通过与关键字的,比较,完成的。
顺序查找，比较的结果为,=”或,≠,
非顺序查找，比较的结果为,<”,,=”,,>”
散列的思想：
根据纪录的关键字直接找到记录的存储位置，
即为关键字和记录的存储位置建立一个对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。
对应关系 f为散列函数，按该思想建立的表为散列表。
2005-02-03
根据设定的哈希函数 H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，
并以关键字在地址集中的,像,作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
哈希表的定义
2005-02-03
散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系 Hash( )，使每个关键字与结构中一个唯一存储位置相对应：
Address ＝ Hash ( Rec.key )
在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，
依相同函数计算存储位置，并按此位置存放。
2005-02-03
构造散列函数时的几点要求：
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m个 地址时,其值域必须在 0 到 m-1 之间。
散列函数计算出来的地址应能均匀分布在整个地址空间中：若 key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取
0到 m-1 中的每一个值。
散列函数应是简单的，能在较短的时间内计算出结果。
哈希函数的构造方法
2005-02-03
1,直接定址法此类函数直接取关键字或关键字的某个 线性函数 值作为散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。
但是，它要求散列地址空间的大小与关键字集合的大小相同。
2005-02-03
2,数字分析法设有 n个 d位数，每一位可能有 r种不同的符号。这 r
种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
2005-02-03
9 4 2 1 4 8
9 4 1 2 6 9
9 4 0 5 2 7
9 4 1 6 3 0
9 4 1 8 0 5
9 4 1 5 5 8
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。
2005-02-03
3,平方取中法
此方法在词典处理中使用十分广泛 。 它先计算构成关键字的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址 。
设标识符可以用一个计算机字长的内码表示 。 因为内码平方数的中间几位一般是由标识符所有字符决定,
所以对不同的标识符计算出的散列地址大多不相同,
即使其中有些字符相同 。
在平方取中法中,一般取散列地址为 2的某次幂 。 例如,若散列地址总数取为 m = 2r,则对内码的平方数取中间的 r位 。 如果 r = 3,所取得的散列地址参看图的最右一列 。
2005-02-03
4,折叠法
此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。
有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。
2005-02-03
示例：设给定的关键字为 key = 23938587841，若存储空间限定 3 位,则划分结果为每段 3 位,上述关键字可划分为 4段：
239 385 878 41
把超出地址位数的最高位删去,仅保留最低的 3位，
做为可用的散列地址。
2005-02-03
一般当关键字的位数很多,而且关键字每一位上数字的分布大致比较均匀时,可用这种方法得到散列地址 。
2005-02-03
5,除留余数法
设散列表中允许的地址数为 m,取一个不大于 m，但最接近于或等于 m的质数 p,或选取一个不小于 20的质因数的合数作为除数，利用以下公式把关键字转换成散列地址。散列函数为：
hash ( key ) = key % p p? m
其中,“%”是整数除法取余的运算，要求这时的质数 p
不是接近 2的幂。
示例：有一个关键字 key = 962148，散列表大小 m
= 25，即 HT[25]。取质数 p= 23。散列函数 hash
( key ) = key % p。则散列地址为：
2005-02-03
hash ( 962148 ) = 962148 % 23 = 12
可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此
，从 23到 24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。
2005-02-03
以上介绍了几种常用的散列函数 。 在实际工作中应根据关键字的特点,选用适当的方法 。 有人曾用,轮盘赌,的统计分析方法对它们进行了模拟分析,结论是平方取中法最接近于,随机化,。
在应用平方取中法时,若关键字不是整数而是字符串时,可以把每个字符串转换成整数 。
2005-02-03
转换的方法：
把字符串从右向左，按一个固定长度 (例如 4 )
进行分段，必要时可在最左端添一些空格。
把每一个字符看成为一个数字，把字符串的每一段看作为一个整数。如,ASCII码采用 7位字符代码，
因此每一个字符可以看成一个 128进制的数字。字符串 abcd看成整数 a*(128)3 + b*(128)2 +
c*(128) + d。
把字符串的每一段都转换成一个整数后，再把各段转换成的整数加起来。
2005-02-03
如果这个整数之和太大，再选择一个适当的常数 C (大于任一段字符串转换成的整数 )来除这个和并取其余数，就得到这个字符串所对应的整数了。
2005-02-03
1,开放定址法（闭散列） ——是处理溢出的一种常用的方法
Hash函数：
Hi = (H(key)+di) MOD m,i=1,2,…,k(k≤m -1)
其中,H(key)为哈希函数,m为哈希表表长,di为增量序列 。
di分别有三种取法：
(1) di=1,2,3,…,m-1 线性探测再散列
(2) di=12,-12,22,-22,…,k2,-k2,(k≤m/ 2)
—— 二次探测再散列特别注意：要求表长 m为形如 4*j+3的素数
(3) di=伪随机数序列,伪随机探测再散列说明：
如果 Hi>m,则 Hi= Hi- m*n; 其中 n为整数
如果 Hi<0,则 Hi= Hi+ m*n; 其中 n为整数处理冲突的方法
2005-02-03
2,再哈希法（也称双散列法）
Hi = RHi (key)
2005-02-03
3,链地址法 —开散列方法
将所有关键字为同义词的记录存储在同一线性表中 。
示例 ——P258例 9-3
2005-02-03
= n / m 0.50 0.75 0.90 0.95
散列函数种类链地址法开放定址法链地址法开放定址法链地址法开放定址法链地址法开放定址法平平 方方 取取 中中
11,,22 66 11,,77 33 11,,44 00 99,,77 55 11,,44 55 33 11 00,,11 44 11,,44 77 33 11 00,,55 33
除留余数
1.19 4.52 1.31 10,20 1.38 22,42 1.41 25,79
移位折叠
1.33 21,75 1.48 65,10 1.40 71 0.01 1.51 11 8.57
分界折叠
1.39 22,97 1.57 48,70 1.55 69,63 1.51 91 0.56
数字分析
1.35 4.55 1.49 30,62 1.52 89,20 1.52 12 5.59
理论值
1.25 1.50 1.37 2.50 1.45 5.50 1.48 10,50
查找关键字时所需对桶的平均访问次数从图中可以看出，链地址法优于开放定址法；在散列函数中，用除留余数法作散列函数优于其它类型的散列函数，最差的是折叠法。
2005-02-03
用不同的方法溢出处理冲突时散列表的平均查找长度如图所示处 理 溢 出 平 均 搜 索 长 度 ASL
的 方 法 搜索成功 Sn 搜索不成功 ( 登入新记录 ) Un
开放线性探查法
)(
定址法伪随机探查法二次探查法双散列法
1l o g
1
e
链 地 址 法
( 同义词子表法 )
e
各种方法处理溢出时的平均查找长度
散列 (Hashing)
在线性表、树结构中查找纪录是通过与关键字的,比较,完成的。
顺序查找，比较的结果为,=”或,≠,
非顺序查找，比较的结果为,<”,,=”,,>”
散列的思想：
根据纪录的关键字直接找到记录的存储位置，
即为关键字和记录的存储位置建立一个对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。
对应关系 f为散列函数，按该思想建立的表为散列表。
2005-02-03
根据设定的哈希函数 H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，
并以关键字在地址集中的,像,作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
哈希表的定义
2005-02-03
散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系 Hash( )，使每个关键字与结构中一个唯一存储位置相对应：
Address ＝ Hash ( Rec.key )
在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，
依相同函数计算存储位置，并按此位置存放。
2005-02-03
构造散列函数时的几点要求：
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m个 地址时,其值域必须在 0 到 m-1 之间。
散列函数计算出来的地址应能均匀分布在整个地址空间中：若 key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取
0到 m-1 中的每一个值。
散列函数应是简单的，能在较短的时间内计算出结果。
哈希函数的构造方法
2005-02-03
1,直接定址法此类函数直接取关键字或关键字的某个 线性函数 值作为散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。
但是，它要求散列地址空间的大小与关键字集合的大小相同。
2005-02-03
2,数字分析法设有 n个 d位数，每一位可能有 r种不同的符号。这 r
种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
2005-02-03
9 4 2 1 4 8
9 4 1 2 6 9
9 4 0 5 2 7
9 4 1 6 3 0
9 4 1 8 0 5
9 4 1 5 5 8
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。
2005-02-03
3,平方取中法
此方法在词典处理中使用十分广泛 。 它先计算构成关键字的标识符的内码的平方,然后按照散列表的大小取中间的若干位作为散列地址 。
设标识符可以用一个计算机字长的内码表示 。 因为内码平方数的中间几位一般是由标识符所有字符决定,
所以对不同的标识符计算出的散列地址大多不相同,
即使其中有些字符相同 。
在平方取中法中,一般取散列地址为 2的某次幂 。 例如,若散列地址总数取为 m = 2r,则对内码的平方数取中间的 r位 。 如果 r = 3,所取得的散列地址参看图的最右一列 。
2005-02-03
4,折叠法
此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。
有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。
2005-02-03
示例：设给定的关键字为 key = 23938587841，若存储空间限定 3 位,则划分结果为每段 3 位,上述关键字可划分为 4段：
239 385 878 41
把超出地址位数的最高位删去,仅保留最低的 3位，
做为可用的散列地址。
2005-02-03
一般当关键字的位数很多,而且关键字每一位上数字的分布大致比较均匀时,可用这种方法得到散列地址 。
2005-02-03
5,除留余数法
设散列表中允许的地址数为 m,取一个不大于 m，但最接近于或等于 m的质数 p,或选取一个不小于 20的质因数的合数作为除数，利用以下公式把关键字转换成散列地址。散列函数为：
hash ( key ) = key % p p? m
其中,“%”是整数除法取余的运算，要求这时的质数 p
不是接近 2的幂。
示例：有一个关键字 key = 962148，散列表大小 m
= 25，即 HT[25]。取质数 p= 23。散列函数 hash
( key ) = key % p。则散列地址为：
2005-02-03
hash ( 962148 ) = 962148 % 23 = 12
可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此
，从 23到 24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。
2005-02-03
以上介绍了几种常用的散列函数 。 在实际工作中应根据关键字的特点,选用适当的方法 。 有人曾用,轮盘赌,的统计分析方法对它们进行了模拟分析,结论是平方取中法最接近于,随机化,。
在应用平方取中法时,若关键字不是整数而是字符串时,可以把每个字符串转换成整数 。
2005-02-03
转换的方法：
把字符串从右向左，按一个固定长度 (例如 4 )
进行分段，必要时可在最左端添一些空格。
把每一个字符看成为一个数字，把字符串的每一段看作为一个整数。如,ASCII码采用 7位字符代码，
因此每一个字符可以看成一个 128进制的数字。字符串 abcd看成整数 a*(128)3 + b*(128)2 +
c*(128) + d。
把字符串的每一段都转换成一个整数后，再把各段转换成的整数加起来。
2005-02-03
如果这个整数之和太大，再选择一个适当的常数 C (大于任一段字符串转换成的整数 )来除这个和并取其余数，就得到这个字符串所对应的整数了。
2005-02-03
1,开放定址法（闭散列） ——是处理溢出的一种常用的方法
Hash函数：
Hi = (H(key)+di) MOD m,i=1,2,…,k(k≤m -1)
其中,H(key)为哈希函数,m为哈希表表长,di为增量序列 。
di分别有三种取法：
(1) di=1,2,3,…,m-1 线性探测再散列
(2) di=12,-12,22,-22,…,k2,-k2,(k≤m/ 2)
—— 二次探测再散列特别注意：要求表长 m为形如 4*j+3的素数
(3) di=伪随机数序列,伪随机探测再散列说明：
如果 Hi>m,则 Hi= Hi- m*n; 其中 n为整数
如果 Hi<0,则 Hi= Hi+ m*n; 其中 n为整数处理冲突的方法
2005-02-03
2,再哈希法（也称双散列法）
Hi = RHi (key)
2005-02-03
3,链地址法 —开散列方法
将所有关键字为同义词的记录存储在同一线性表中 。
示例 ——P258例 9-3
2005-02-03
= n / m 0.50 0.75 0.90 0.95
散列函数种类链地址法开放定址法链地址法开放定址法链地址法开放定址法链地址法开放定址法平平 方方 取取 中中
11,,22 66 11,,77 33 11,,44 00 99,,77 55 11,,44 55 33 11 00,,11 44 11,,44 77 33 11 00,,55 33
除留余数
1.19 4.52 1.31 10,20 1.38 22,42 1.41 25,79
移位折叠
1.33 21,75 1.48 65,10 1.40 71 0.01 1.51 11 8.57
分界折叠
1.39 22,97 1.57 48,70 1.55 69,63 1.51 91 0.56
数字分析
1.35 4.55 1.49 30,62 1.52 89,20 1.52 12 5.59
理论值
1.25 1.50 1.37 2.50 1.45 5.50 1.48 10,50
查找关键字时所需对桶的平均访问次数从图中可以看出，链地址法优于开放定址法；在散列函数中，用除留余数法作散列函数优于其它类型的散列函数，最差的是折叠法。
2005-02-03
用不同的方法溢出处理冲突时散列表的平均查找长度如图所示处 理 溢 出 平 均 搜 索 长 度 ASL
的 方 法 搜索成功 Sn 搜索不成功 ( 登入新记录 ) Un
开放线性探查法
)(
定址法伪随机探查法二次探查法双散列法
1l o g
1
e
链 地 址 法
( 同义词子表法 )
e
各种方法处理溢出时的平均查找长度
