散列方法不同于顺序查找 二分查找 二叉排序树及B 树上的查找 它不以关键字的比较为基本操作 采用直接寻址技术 在理想情况下 无须任何比较就可以找到待查关键字 查找的期望时间为O( )
散列表的概念
散列表
设所有可能出现的关键字集合记为U(简称全集) 实际发生(即实际存储)的关键字集合记为K(|K|比|U|小得多)
散列方法是使用函数h将U映射到表T[ m ]的下标上(m=O(|U|)) 这样以U中关键字为自变量 以h为函数的运算结果就是相
应结点的存储地址 从而达到在O( )时间内就可完成查找
其中
① h U→{ … 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) α越大 表越满 冲突的机会
也越大 通常取α≤
lishixinzhi/Article/program/sjjg/201311/23740