19:04:41 2019-09-17
已知的查找方式
顺序查找 $O(N)$
二分查找(静态查找) $O(LogN)$
二叉搜索树 $O(h)$ h为二叉查找树的高度
平衡二叉树 $O(LogN)
查找的本质:已知对象找位置
有序安排对象:全序(二分查找) 半序(二叉搜索树)
直接“算出”对象位置:散列
散列查找法的两项基本工作:
计算位置:构造散列函数 确定关键词存储位置
解决冲突:引用某种策略 解决多个关键词位置相同的问题
时间复杂度几乎是常量:$O(1)$,及查找时间与问题规模无关
散列表(哈希表)
类型名称:符号表(SymbolTable)
数据对象集:符号表是"名字(Name)-属性(Attribute)"的集合
如果没有溢出 $T_查询=T_插入=T_删除=O(1)$
”散列(Hashing)"的基本思想是:
(1)以关键字Key为自变量,通过一个确定的函数h(散列函数) 计算出对应的函数值h(Key)，作为数据对象的存储地址
(2)可能不同的关键字会映射到同一个散列地址上，
即$h(key_1)=h(key_2) 当(key_1\not=key_2)$，称为“冲突(Collision)”---------需要某种冲突解决策略
散列函数的构造方法
一个好的散列函数一般应考虑下列两个因素:
1.计算简单,以便提高转换速度
2.关键词对应的 地址空间分布均匀,以尽量减少冲突
数字关键词的散列函数构造
1.直接定址法
取关键词的某个线性函数值为散列地址,即$h(key)=a*key+b (a、b为常数)$
2.除留余数法
散列函数为 $h(key)=key mod p$
这里 $p=TableSize$
一般，$p$取素数
3.数字分析法
4.折叠法
把关键词分割成位数相同的几个部分,然后叠加
5.平方取中法
原文：https://www.cnblogs.com/57one/p/11536647.html