94哈希查找表 、哈希表的概念 二、哈希函数的构造方法 三、哈希冲突处理方法 四、哈希表的查找及分析
1 9.4 哈希查找表 一、哈希表的概念 二、哈希函数的构造方法 三、哈希冲突处理方法 四、哈希表的查找及分析
、哈希表的概念 哈希表:也称作散列存储结构。 散列法存储的基本思想:建立关键码字与其存储位置的对应 关系,或者说,由关键码的值决定数据的存储地址。 优点:查找速度极快(0(1),查找效率与元素个数n无关! 例1:若将学生信息按如下方式存入计算机,如 将2001011810201的所有信息存入V[01单元; 将2001011810202的所有信息存入V[02单元; 将2001011810231的所有信息存入V31单元。 欲查找学号为2001011810216的信息,便可直接访问V[16]!
2 一、哈希表的概念 哈希表：也称作散列存储结构。 散列法存储的基本思想：建立关键码字与其存储位置的对应 关系，或者说，由关键码的值决定数据的存储地址。 优点：查找速度极快（O(1)）,查找效率与元素个数n无关！ 例1：若将学生信息按如下方式存入计算机，如： 将2001011810201的所有信息存入V[01]单元； 将2001011810202的所有信息存入V[02]单元； …… 将2001011810231的所有信息存入V[31]单元。 欲查找学号为2001011810216的信息，便可直接访问V[16]！
例2:有数据元素序列(14,23,39,9,25,11),若规定 每个元素k的存储地址H(k)=k,请画出存储结构图。 H(k)称为散列函数 解:根据散列函数H(k)=k,可知元素14应当存入地址 为14的单元,元素23应当存入地址为23的单元, 对应散列存储表(哈希表)如下 地址∴.9.11..14.232425 39 内容 14 2325 39 讨论:如何进行散列查找? 根据存储时用到的散列函数H(k)表达式,迅即可查到结果! 例如,查找key=9则访问H(9)=9号地址,若内容为9则成功 若查不到,应当设法返回一个特殊值,例如空指针或空记录。 明显缺点:空间效率低《如何解决?
3 例2 ：有数据元素序列(14，23，39，9，25，11)，若规定 每个元素k的存储地址H（k）＝k，请画出存储结构图。 解：根据散列函数H（k）＝k ，可知元素14应当存入地址 为14的单元，元素23应当存入地址为23的单元，……， 对应散列存储表（哈希表）如下： 讨论：如何进行散列查找？ 根据存储时用到的散列函数H(k)表达式，迅即可查到结果！ 例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功； 若查不到，应当设法返回一个特殊值，例如空指针或空记录。 地址 … 9 … 11 … 14 … 23 24 25 … 39 … 内容 9 11 14 23 25 39 明显缺点：空间效率低 如何解决？ H(k)称为散列函数
Hash查找法若干术语 哈希方法选取某个函数,依该函数按关键字计算元素的存储位置 (杂凑法)并按此存放;查找时也由同一个函数对给定值k计算地址 将k与地址中内容进行比较,确定查找是否成功。 哈希函数哈希方法中使用的转换函数称为哈希函数(杂 杂凑函数)凑函数) 哈希表按上述思想构造的表称为哈希表(杂凑表) (杂凑表) 冲突通常关鍵码的集合比哈希地址集合大得多,因而经 过哈希函数变换后,可能将不同的关键码映射到同 个哈希地址上,这种现象称为冲突
4 选取某个函数，依该函数按关键字计算元素的存储位置 并按此存放；查找时也由同一个函数对给定值k计算地址， 将k与地址中内容进行比较，确定查找是否成功。 通常关键码的集合比哈希地址集合大得多，因而经 过哈希函数变换后，可能将不同的关键码映射到同 一个哈希地址上，这种现象称为冲突。 Hash查找法 哈希方法 (杂凑法) 哈希函数 (杂凑函数) 哈希表 (杂凑表) 冲 突 哈希方法中使用的转换函数称为哈希函数(杂 凑函数) 按上述思想构造的表称为哈希表(杂凑表) 若干术语
冲突现象举例 有6个元素的关键码分别为:(14,23,39,9,25,11)。 选取关键码与元素位置间的函数为H(k)=kmod7 6个元素用7个 通过哈希函数对6个元素建立哈希表: 地址应该足够! 0123456 14 23 39 9 25 H(14)=14%7=0 H(25)=25%7=4 H(11=11%7= 有冲突!
5 有6个元素的关键码分别为：（14，23，39，9，25，11）。 选取关键码与元素位置间的函数为H(k)=k mod 7 通过哈希函数对6个元素建立哈希表： 25 23 39 9 14 冲突现象举例： 6个元素用7个 地址应该足够! H(14)=14%7=0 11 H(25)=25%7=4 H(11)=11%7=4 有冲突！ 0 1 2 3 4 5 6
在哈希查找方法中,冲突是不可能避兔的,只能 尽可能城少。 所以,哈希方法必须解决以下两个间题 1)构造好的哈希函数 a)所选函数尽可能简单,以便提高转换速度; b)所选函数对关键码计算出的地址,应在哈希地址内集 中并大致均匀分布,以减少空间浪费 2)制定一个好的解决冲突的方案 查找时,如果从哈希函数计算出的地址中查不到关键码,则 应当依据解决冲突的规则,有规律地查询其它相关单元
6 所以，哈希方法必须解决以下两个问题： 1）构造好的哈希函数 （a）所选函数尽可能简单，以便提高转换速度； （b）所选函数对关键码计算出的地址，应在哈希地址内集 中并大致均匀分布，以减少空间浪费。 2）制定一个好的解决冲突的方案 查找时，如果从哈希函数计算出的地址中查不到关键码，则 应当依据解决冲突的规则，有规律地查询其它相关单元。 在哈希查找方法中，冲突是不可能避免的，只能 尽可能减少
二、哈希函数的构造方法 要求一:n个数据原仅占用n个地 址,虽然散列查找是以空间换时间, 但仍希望散列的地址空间尽量小。 要求二:无论用什么方法存储,目 的都是尽量均匀地存放元素,以避免1.直接定址法 冲突。 2.除留余数法 常用的哈希函数构造方法有 3.乘余取整法 4.数字分析法 5.平方取中法
7 二、哈希函数的构造方法 常用的哈希函数构造方法有： 1. 直接定址法 2. 除留余数法 3. 乘余取整法 4. 数字分析法 5. 平方取中法 要求一：n个数据原仅占用n个地 址，虽然散列查找是以空间换时间， 但仍希望散列的地址空间尽量小。 要求二：无论用什么方法存储，目 的都是尽量均匀地存放元素，以避免 冲突
1、直接定址法 Hash(key)=akey+b(a、b为常数) 优点:以关键码key的某个线性函数值为哈希地址, 不会产生冲突 缺点:要占用连续地址空间,空间效率低。 例:关键码集合为{100,300,500,700,800,900 选取哈希函数为Hash(key)=key/100, 则存储结构(哈希表)如下: 0123456789 100 300 500 700800900
8 Hash(key) = a·key + b (a、b为常数) 优点：以关键码key的某个线性函数值为哈希地址， 不会产生冲突. 缺点：要占用连续地址空间，空间效率低。 例：关键码集合为{100，300，500，700，800，900}， 选取哈希函数为Hash(key)=key/100， 则存储结构（哈希表）如下： 0 1 2 3 4 5 6 7 8 9 100 300 500 700 800 900 1、直接定址法
2、除留余数法 Hash(key)= key mod n(m是一个整数) 特点:以关键码除以p的余数作为哈希地址。 关键:如何选取合适的m? 技巧:若设计的哈希表长为m,则一般取pm且为质数 (也可以是合数,但不能包含小于20的质因子)。 3、乘余取整法 (Akey mod I 就是取A*key的小 Hash(key)=LB( A*key mod1)」气数部分 (A、B均为常数,且0<A<1,B为整数) 特点:以关键码key乘以A,取其小数部分,然后 再放大B倍并取整,作为哈希地址。 例:欲以学号最后两位作为地址,则哈希函数应为 其实也可以用法2实现:H(k)=k%100
9 Hash(key)= B*( A*key mod 1 ) (A、B均为常数，且0<A<1，B为整数) 特点：以关键码key乘以A，取其小数部分，然后 再放大B倍并取整，作为哈希地址。 Hash(key)=key mod m (m是一个整数) 特点：以关键码除以p的余数作为哈希地址。 关键：如何选取合适的m？ 技巧：若设计的哈希表长为m，则一般取p≤m且为质数 （也可以是合数，但不能包含小于20的质因子）。 3、乘余取整法 2、除留余数法 （A*key mod 1） 就是取A*key 的小 数部分 例：欲以学号最后两位作为地址，则哈希函数应为： H(k)=100*(0.01*k % 1 ) 其实也可以用法2实现： H(k)=k % 100
4、数字分析法 特点:选用关键字的某几位组合成哈希地址。选用原则应 当是:各种符号在该位上出现的频率大致相同。 例:有一组(例如80个)关键码,其样式如下: 3470524 讨论: 3491487①第1、2位均是“3和4”,第3位也 3482696只有“7、8、9”,因此,这几位不 3485270能用,余下四位分布较均匀,可作 3486305 为哈希地址选用 3498058②若哈希地址取两位(因元素仅80 347967 个),则可取这四位中的任意两位组 3473919合成哈希地址,也可以取其中两位与 位号:①②③回回⑦其它兩位叠加求和后,取低两位作哈 希地址
10 特点：选用关键字的某几位组合成哈希地址。选用原则应 当是：各种符号在该位上出现的频率大致相同。 3 4 7 0 5 2 4 3 4 9 1 4 8 7 3 4 8 2 6 9 6 3 4 8 5 2 7 0 3 4 8 6 3 0 5 3 4 9 8 0 5 8 3 4 7 9 6 7 1 3 4 7 3 9 1 9 例：有一组（例如80个）关键码，其样式如下： 4、数字分析法 讨论： ① 第1、2位均是“3和4”，第3位也 只有“ 7、8、9”，因此，这几位不 能用，余下四位分布较均匀，可作 为哈希地址选用。 位号：① ② ③ ④ ⑤ ⑥ ⑦ ② 若哈希地址取两位（因元素仅80 个），则可取这四位中的任意两位组 合成哈希地址，也可以取其中两位与 其它两位叠加求和后，取低两位作哈 希地址