数据结构-散列表.ppt

7.3 散列表的查找技术 例子 一组数：12，37，52，43，84，99 散列函数为:H(k)=k%11 散列表： 长度为11 * * 7.3 散列表的查找技术 顺序查找、折半查找等。 这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。 查找操作要完成什么任务？ 待查值k 确定k在存储结构中的位置 我们学过哪些查找技术？这些查找技术的共性？ 在存储位置和关键码之间建立一个确定的对应关系 能否不用比较，通过关键码直接确定存储位置？ 概 述 散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。 7.3 散列表的查找技术 关键码集合 ki ri H(ki) …… …… H 散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。 概 述 7.3 散列表的查找技术 关键码集合 ki ri H(ki) …… …… H 散列表 数组 散列函数：将关键码映射为散列表中适当存储位置的函数。 概 述 7.3 散列表的查找技术 散列表 关键码集合 ki ri H(ki) …… …… H 散列函数 数组 散列地址：由散列函数所得的存储位置 。 概 述 7.3 散列表的查找技术 散列表 关键码集合 ki ri H(ki) …… …… H 散列函数 散列地址 下标 数组 10 9 8 7 6 5 4 3 2 1 0 12 37 52 43 84 99 概 述 7.3 散列表的查找技术 散列技术仅仅是一种查找技术吗？ 散列既是一种查找技术，也是一种存储技术。 散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。 散列是一种完整的存储结构吗？ 散列技术的关键问题： ⑴ 散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。 ⑵ 冲突的处理。如何采取合适的处理冲突方法来解决冲突。 7.3 散列表的查找技术 概 述 冲突：对于两个不同关键码ki≠kj，有H(ki)＝H(kj)，即两个不同的记录需要存放在同一个存储位置,ki和kj相对于H称做同义词。 7.3 散列表的查找技术 概 述 ri 关键码集合 ki …… …… H(ki) kj H(kj) 散列函数 7.3 散列表的查找技术 设计散列函数一般应遵循以下原则： ⑴ 计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。 ⑵ 函数值即散列地址分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。 1、散列函数——直接定址法 散列函数是关键码的线性函数，即： H(key) = a ? key + b （a，b为常数） 例：关键码集合为{10, 30, 50, 70, 80, 90}，选取的散列函数为H(key)=key/10，则散列表为： 0 1 2 3 4 5 6 7 8 9 10 30 50 70 80 90 适用情况？ 事先知道关键码，关键码集合不是很大且连续性较好。 7.3 散列表的查找技术 散列函数为： H(key)=key mod p 7.3 散列表的查找技术 2、散列函数——除留余数法 如何选取合适的 p，产生较少同义词？ 一般情况下，选p为小于或等于表长（最好接近表长）的最小素数。 适用情况？ 除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。 根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。 例：关键码为8位十进制数，散列地址为2位十进制数 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 7.3 散列表的查找技术 3、散列函数——数字分析法 适用情况: 能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。 7.3 散列表的查找技术 3、散列函数——数字分析法 对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。 7.3 散列表