查找与散列（Hash）
1.查找的一些概念
查找——在给定集合中查找特定的元素。
在查找的过程中，查找的长度是指关键字间的比较次数，而平均查找长度则是数学上的期望：ASL=P1*C1+P2*C2+...+Pn*Cn。 Pi为查找第i个元素的概率，Ci为查找第i个元素所需的查找长度。一般认为每个元素查找概率相同。平均查找长度分为查找成功和查找不成功长度两种。
对于顺序查找来说。ASL（成功）=(1+2+...+n)*1/n=(n+1)/2；ASL(不成功)=n。
折半查找的查找过程可以用判定树来描述。
ASL(成功)=int[log(2)(n)]+1。
例题：【2010研招】已知一个长度为16的顺序表L，其元素有序，若采用折半查找去查找一个不存在的元素，则关键字的比较次数最多是（5次）
答：具有n个结点的判定树高度为int[log(2)(n)]+1。所以最多比较5次。
2.散列表(Hash)
散列：把元素的内容与元素的存储地址关联起来，提高查找效率。
散列函数：实现从元素值到存储地址的映射。
散列表：记录元素值到存储地址的映射。
常用散列函数：
1.直接定址法:H(key)=a*key+b。
2.除留余数法：H(key)=key mod b。
处理冲突的方法：
1.拉链法——把所有同义词存储在一个链表中。
2.线性探测法——冲突发生时，查找该冲突位置后面的单元，遇到空单元时把地址填进去。
散列表的查找效率取决于三个因素：散列函、冲突处理方法和填装因子。
填装因子=元素数目/散列表长度。填装因子越大，散列表越满，发生冲突的可能性就大。
例题：【2010研招】将关键字序列(7,8,30,11,18,9,14)7个元素散列存储到散列表中。散列表的存储空间是下标从0开始的一维数组，散列函数为H(key)=key*3 mod 7。处理冲突的方法为线性探测再散列法，填充因子为0.7。
1）请画出散列表；
2）分别计算等概率情况下，查找成功和查找不成功的平均查找长度。
引申：
他人blog——从头到尾彻底解析Hash 表算法
http://blog.csdn.net/v_july_v/article/details/6256463
原文：http://blog.csdn.net/chuchus/article/details/23000125
