1.理解哈希表
在线性表、树等数据结构中，存储元素的位置是随机的，和元素本身不存在确定的关系，因此在查找元素时，需要进行比较，在这种比较的查找机制中，结果有大于、等于和小于，查找效率依赖于过程中比较的次数。
在理想的情况下不需要进行比较，一次存取便能得到所查元素。因此，需要在元素和元素存储位置之间建立一个确定的对应关系F，使得对于每一个元素K，有相应的存储位置F（K）对应，称这个对应关系F为哈希函数。
设定哈希函数Hash(Key)和处理冲突的方法将一组元素映像到一个连续的地址空间，以Hash(Key)作为Key在表中的存储位置，这种表是哈希表，这一过为哈希构造表或散列，所得存储位置为哈希地址或散列地址。
要点：
- 哈希函数的构造灵活，只要元素的哈希值在表长的范围内即可。
- 对不同元素得到同一哈希值，这种现象为冲突，冲突只能减少，不能完全避免。
2.哈希函数的构造方法
若对于元素映像到地址空间中的任意地址的概率是相等的，则称均匀的哈希函数。
直接定值法
取元素本身或元素的线性函数值为哈希地址：
Hash(key)=key
Hash(key)=a*key+b
其中a,b为常数。
数字分析法
取关键字的若干位数组成哈希地址，尽量选择随机数。
平方取中法
取元素平方后的中间几位作为哈希值，比较常用。
除留余数法
取元素被不大于哈希表表长m的数p除后所得的余数作为哈希地址：
Hash（key)=key MOD p (p<=m)
一般情况下可选择p为素数。
折叠法
将元素分解成位数相同的几部分（最后一部分可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。当元素位数较多，而且每一位上数字分布大致均匀时，可以使用折叠法。
随机数法
选择一个随机函数，取元素的随机函数值作为哈希地址，即Hash(key)=random(key)。当关键字长度不等时，可采用此法构造哈希函数。
3.处理冲突的方法
冲突是指当前元素计算的哈希地址的位置上已经存有记录，而“处理冲突”就是为该元素找到另一个空的哈希地址。
开放定址法
=( H(key) +
) MOD m
其中：
（1）
=1,2,3,...,m-1 【线性探测再散列】
（2）
=
,
,
,
,...,
( k<=m/2) 【二次探测再散列】
链地址法
将所有元素的同义词的记录存储在同一线性链表中。假设哈希函数产生的哈希地址空间为[0,m-1],设定一个存储链表的数组，即
T Chain[m]
每个分量的初始状态为空，哈希地址为 i 的元素插入到Chain[ i ]链表中。
建立一个公共溢出区
若哈希函数的值域为[0,m-1]，创建一个基本表HashTable[0...m-1],每个分量存放一个记录，再创建一个溢出表OverFlowTable[n],若是同义词的记录，一旦发生冲突，将其填入溢出表。