537.散列表(Hash Table)

散列表(Hash table,也叫哈希表)是一种查找算法,与链表、树等算法不同的是,散列表算法在查找时不需要进行一系列和关键字(关键字是数据元素中某个数据项的值,用以标识一个数据元素)的比较操作。
散列表算法希望能尽量做到不经过任何比较,通过一次存取就能得到所查找的数据元素,因而必须要在数据元素的存储位置和它的关键字(可用 key 表示)之间建立一个确定的对应关系,使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时,只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。
用的构造散列函数的方法有:

  1. 直接定址法: 取关键字或关键字的某个线性函数值为散列地址。即:h(key) = key 或 h(key) = a * key + b,其中 a 和 b 为常数。
    1. 数字分析法
    2. 平方取值法: 取关键字平方后的中间几位为散列地址。
    3. 折叠法:将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为散列地址。
    4. 除留余数法:取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址,即:h(key) = key MOD p p ≤ m
  2. 随机数法:选择一个随机函数,取关键字的随机函数值为它的散列地址,即:h(key) = random(key)