哈希(Hash)

• 根据键（Key）而直接访问在内存存储位置的数据结构
• 哈希函数(散列函数)：在记录的存储位置和它的关键词之间建立的一个确定的对应关系f，使每个关键字和结构中的一个惟一的存储位置相对应。

• 哈希表（散列表-Hash table）：在查找时，只要根据对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较就可直接取得所查记录。按这个思想建立的表为哈希表
• 定义：根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集(区间)上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
• 冲突(collision)：不同的关键字得到相同的哈希地址
• 同义词(synonym)：具有相同函数值的关键字
• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

哈希函数的构造方法

• 直接定址法

  取关键字或关键字的某个线性函数值为哈希函数。

• 数字分析法

  假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。

• 平方取中法

  取关键字平方后的中间几位为哈希地址。

• 折叠法

  将关键字分割成数位相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和(舍去进位)作为哈希地址。

• 除留余数法

  取关键字被某个不大于哈希表表长m的数p出后所得余数为哈希地址。

• 随机数法

  选择一个随机函数，取关键字的随机函数值为它的哈希地址。当关键字长度不等时采用此法构造哈希函数较恰当。

处理冲突的方法

• 开放定址法

  H_i = (H(key) + d_i) MOD m i = 1,2,…,k(k<=m-1)

  • d_i = 1,2,3,…,m-1，称为线性探测再散列；
  • d_i = 1²,-1²,2²,-2²,…,k²,-k²,(k<=m/2)称为二次探测再散列；
  • d_i = 伪随机数序列，称伪随机探测再散列。

• 再哈希法（再散列）

  在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。

• 链地址法（单独链表法）

  将所有关键字为同义词的记录存储在同一线性链表中。

• 建立一个公共溢出区

  一旦发生冲突，都填入溢出表。