算法与数据结构 — 散列表_散列表装填因子计算

算法与数据结构 — 散列表

一、相关概念

1. 散列表：

   • 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
     这个映射函数叫做 散列函数，存放记录的 数组 叫 做散列表。

   • 散列表利用的是数组支持按照下标随机访问数据的特性（时间复杂度O(1)），所以散列表其实就是数组的一种扩展，由数组演化而来。

2. 散列函数：
   一个把查找表中的关键字映射成关键字对应的地址的函数，记为：Hash(key) = Addr

3. 冲突：
   散列函数可能把两个或两个以上的不同的关键字映射到同一地址，称这种情况为 “冲突”，这些发生碰撞的不同关键字称为 同义词。

二、构建散列函数

2.1 hash函数

2.1.1 直接定址法

取关键字或关键字的某个线性函数值为散列地址。散列函数：H(key) = key 或 H(key) = a·key + b，其中a和b为常数。
这种方法计算最简单，并且不会产生冲突。

2.1.2 除留余数法

假设散列表长度为m，取一个不大于m但最接近或等于m的质数p，散列函数：H(key) = key MOD p,p<=m。
对 p 的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

2.1.3 平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。

2.1.4 折叠法

2.1.5 数字分析法

2.1.6 随机数法

2.2 冲突处理

2.2.1 拉链法

• 拉链法：

  • 对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把 所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。【把散列表的每个槽定义为链表的头】
  • 拉链法适用于 经常进行插入和删除 的情况

• HashMap 利用拉链法解决冲突的

2.2.2 开放定址法

将产生冲突的 hash 地址作为自变量，通过某种冲突解决函数得到一个新的空闲的 hash 地址。

1. 线性探测法：

   • 冲突发生时，顺序查看表中下一个单元（当探测到表尾 m-1 时，下一个探测地址是表首地址 0），直到找出一个空闲的单元。
   • 线性探测法会造成大量元素在相邻的散列地址上 “聚集” 起来，大大降低了查找效率。

2. 平方探测法：

   • 设发生冲突的地址为d，平方探测法得到的新地址序列为：d + 1²，d - 1²，d + 2²，d - 2²…
   • 平方探测法是一种比较好的处理冲突的方法，可以避免出现 “堆积” 问题，缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

2.2.3 再散列法

• 再散列法：又称为双散列法。需要使用两个散列函数，当通过第一个散列函数（key）得到的地址发生冲突时，则利用第二个散列函数 Hash2(key) 计算该关键字的 地址增量。
• Hi = (H(key) + i * Hash2(key)) % m，其中 m 时散列表的长度，i 是冲突次数，初始为 0

2.2.4 建立公共溢出区

• 即为所有冲突的关键字建立一个公共的溢出区来存放

  在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对

  如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找

• 如果对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高

三、散列表查找

3.1 查找过程

• 给定一个关键字 key
• 先根据散列函数计算出散列地址，然后检查散列地址的位置有没有关键字
  • 如果没有，表明关键字不存在，返回查找失败
  • 如果有，则检查该记录是否等于关键字
    • 如果等于关键字，返回查找成功
    • 如果不等于，则按照给定的 冲突解决办法 来计算下一个散列地址，再用该地址去执行上述过程

3.2 查找性能

和装填因子有关。

• 装填因子：散列表的装填因子一般即为 a，定义为一个表的装满程度。
  • 计算方法，a = （表中记录数 n）/（散列表长度 m）
• 散列表的平均查找长度，依赖于散列表的装填因子a，而不直接依赖于 n 或 m。
  a 越大，表示装填的记录越慢，发生的冲突可能性就越大，反之发生冲突的可能性就越小