浙江大学数据结构 第十一讲 散列查找
本文为浙江大学mooc课程 数据结构 散列查找的搬运，原课程地址如下：https://www.icourse163.org/learn/ZJU-93001?tid=1459700443#/learn/content?type=detail&id=1235254076
1 散列表
编译处理中对变量的管理：动态查找问题。
是否可以先把字符串转换为数字，再处理？
如何快速搜索到需要的关键词？如果关键词不方便比较怎么办？
查找的本质：已知对象找位置。
有序安排对象：全序、半序；直接“算出”对象位置：散列
散列查找法的两项基本工作：
计算位置：构造散列函数确定关键词存储位置；
解决冲突：应用某种策略解决多个关键词位置相同的问题。
时间复杂度几乎是常量：O（1），即查找时间与问题规模无关。
2 散列函数的构造方法
一个“好”的散列函数一般应考虑下列两个因素：
- 计算简单，以便提高转换速度；
- 关键词对应的地址空间分布均匀，以尽量减少冲突。
对每个字符来说，ASCII码的编码范围是0-127，如果变量名是十位字符串，求和之后在0-1270之间，但十位变量本身的变化范围远大于1270，所以很容易产生冲突。
有26个字母，考虑空格，共27个字符，使用27进制；经过统计，字符串（单词）中前三位的组合情况大概只有3000种，采用移位法是按26^3考虑的，造成了空间的浪费。