学习笔记之散列表
学习笔记之散列表 （哈希表） 相关主题 Post not found: 学习笔记之查找 学习笔记之查找
散列技术是在记录的存储位置和关键字之前简历确定的对应关系f, 使得每个关键字key对应一个存储位置f（key）.
存储位置 = f（关键字）, f 称之为散列函数，有称为哈希（hash）函数
哈希函数
原则：
- 计算简单
- 散列地址均匀分布
直接定址 （f(key) = key ），抽取关键字的一部分来计算， 除留取余 等
设计散列函数需要考虑的因素：
- 计算地址所需的时间
- 关键字的长度
- 散列表的大小
- 关键字的分布情况
- 记录的查找频率
冲突 （collision）
当k1\(\ne\)k2, \(f(k1)\) == \(f(k2)\)
开放定址
发生冲突后继续寻找下一个地址
线性探测
随机探测
再散列
链地址
散列表的性能指标
- 散列函数是否分布均匀
- 处理冲突的方法： 如线性探测会导致堆积，二次探测则没有堆积问题。
- 装填因子： 填入表中记录个数 / 散列表的长度； 装填越大，冲突概率越大。 - 选择合适的装填因子