已知的查找方法
定义
先构造一个散列函数，把关键字放进去，将来根据这个散列函数计算出关键字的位置，来对关键字进行查找和删除等操作。
为了解决冲突，用二维数组作为散列表，把多出来的关键字放在第二列。
关键字是数字的定址方法
直接定址法
取余法
数字分析法
- 有的关键字只有特定位是变化的，其余位都跟其他关键字一样或是差不多。可以取这几位出来转换为一个整数，作为散列函数的key。
折叠法和平方取中法
- 平方取中法就是把关键字平方之后取中间几位。
关键字是字符的定址方法
ASC码加和法
- 改进一下
- 把字符串前三位看成27进制，累加起来再求余；不过前三位可能是一样的。
- 再改进一下
- 同样是要求余
- 但是如何快速计算呢？
- *32实际就是把数字移5位了。
处理冲突的方法
开放定址法
- 线性探测：如果散列函数计算出来的地址冲突，那么第一次加1，寻找下一个地址，如果第二次也冲突就加2，…
- 平方探测：第一次加1^2,第二次减1^2,第三次加2^2,第四次减2^2,…
- 双散列：再设计一个散列函数h2
线性探测
- 设计表长为13是为了留出空间以备冲突使用。
- d表示冲突次数
- 注意：出现了聚集现象。线性探测一旦出现冲突，就会导致聚集现象。
- ASLs就是查找表中存在的数据所用的平均查找次数，没冲突的数据可以一次找到，有冲突的则需要下一个下一个地查找，如，29需要查找2次。
ASLu表示要查找的数据不存在于表中，，根据余数情况11种分为11类来考虑，每一类的查找次数都相同。如，22和33，先求余=0，然后查找0位上key为11，怀疑可能是因为放入时冲突所以放到了下一位，故查找下一位，1位上为30，再下一位，2位上为空，证明表中根本没有这个数，查找不成功，查找次数为3.将这11类累计起来求平均即得ASLu。
再举个例子
- 用首字母减去a作为下标
平方探测法
- 由于平方探测法是跳着找的，所以可能会找不到空余空间。
- 不过只要表长设计好了也可以解决这个问题。
- 平方探测法能明显地减轻聚集问题。
散列函数算法实现
初始化
- 散列表可以设计成一个结构体，包含表的最大长度和存放key的数组。
- 数组设计成一个结构数组（也就是结构体数组）。结构体内存放标记和key。
- 删除散列表中的一个key时是不可以真的把它删掉的，而是改变标记为已删除，这样查找散列表时，发现某个位置为已删除，还会接着往后面找，但如果被删掉了，这个位置就是空的我就会认为要查找的key不在表中，这回造成误判。
- 插入的时候发现某个位置的key已被删除，就用要插入的key替换上去。
- 计算散列值之前先判断散列表会不会太小，太小的话就不需要做散列直接放数组里就好了。
- NextPrime函数：返回一个不小于表长度的素数。
查找
- Hash():调用某个哈希函数求散列值
插入
再散列
- 装填因子太大时，应将散列表扩大，然后重新计算key的散列值，再放进去。
- 算法实例：第十一讲->11.3第5小节
分离链接法
查找
散列表的性能分析
线性探测法
- 求ASLu则代入第一个公式
- 不过实际的计算可能跟公式计算结果不同，因为公式计算的是一般情况。
平方探测法和双散列探测法
