|
散列方法不同于顺序查找二分查找二叉排序树及B树上的查找它不以关键字的比较为基本操作采用直接寻址技术在理想情况下无须任何比较就可以找到待查关键字查找的期望时间为O() 散列表的概念 散列表 设所有可能出现的关键字集合记为U(简称全集)实际发生(即实际存储)的关键字集合记为K(|K|比|U|小得多) 散列方法是使用函数h将U映射到表T[m]的下标上(m=O(|U|))这样以U中关键字为自变量以h为函数的运算结果就是相 应结点的存储地址从而达到在O()时间内就可完成查找 其中 ① hU→{…m} 通常称h为散列函数(Hash Function)散列函数h的作用是压缩待处理的下标范围使待处理 的|U|个值减少到m个值从而降低空间开销 ② T为散列表(Hash Table) ③ h(K i )(K i ∈U)是关键字为K i 结点存储地址(亦称散列值或散列地址) ④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing) 散列表的沖突现象 ()沖突 两个不同的关键字由于散列函数值相同因而被映射到同一表位置上该现象称为沖突(Collision)或碰撞发生沖突的两个 关键字称为该散列函数的同义词(Synonym) 【例】上图中的k ≠k 但h(k )=h(k )故k 和K 所在的结点的存储地址相同 ()安全避免沖突的条件 最理想的解决沖突的方法是安全避免沖突要做到这一点必须满足两个条件 ①其一是|U|≤m ②其二是选择合适的散列函数 这只适用于|U|较小且关键字均事先已知的情况此时经过精心设计散列函数h有可能完全避免沖突 ()沖突不可能完全避免 通常情况下h是一个压缩映像虽然|K|≤m但|U|>m故无论怎样设计h也不可能完全避免沖突因此只能在设计h时尽可 能使沖突最少同时还需要确定解决沖突的方法使发生沖突的同义词能够存储到表中 ()影响沖突的因素 沖突的频繁程度除了与h相关外还与表的填满程度相关 设m和n分别表示表长和表中填人的结点数则将α=n/m定义为散列表的装填因子(Load Factor)α越大表越满沖突的机会 也越大通常取α≤ |
