直接寻址

相对于哈希表来说,直接寻址是一种更为简单的方法,即使用一组键集合 K 来代表一组相应的值 U,但是直接寻址受限于一个重要的缺陷,即K可能相比较于U会小很多,并且会出现数组浪费情况,很多槽都可能是空的,注意这里和是OOP里面的对象键值对没有联系,哈希表都是以数组的形式出现的,因为只有当自身是数组的时候,才能做到最快速的偏移,因为数组在绝大多数语言之中都是以一段连续的内存出现的,这就是为什么哈希表做到O(1)访问的原因。

哈希表

哈希表(散列表)是一种直接寻址技术的增强,其核心思想在于,对原本的关键字进行一次hash(),也就是说,其在表中真正的key是hash(k)

散列表的最大好处就是利用hash缩减了数组的大小。

但这会引发一个问题,即如果多次插入一个相同关键字,那么可能会插入一个相同的槽中,这被称为碰撞或者是冲突(collision)。

对于这种情况,我们拥有一些解决方案

链接法

链接法是一种最为简单的解决冲突方案,当链接法遇见冲突的时候,就将同一插槽的元素合并成一个链表,并把插槽的指针指向链表的头部。

所以我们可以预见当整个关键字集合基本相同时,我们将得到一个超长的列表,这时候所谓的表的概念会变得模糊,这也是链接法最差情况。Θ(n)

这里我们还需要引申出一个概念,装载因子 α 即 n / m 也就是当key为n个槽为m个的时候,每个槽平均对应多少个key,在hash算法为尽量平均分布的时候,我们的查找时间就是 O(1 + α),由此可以看出,我们的哈希表时间复杂度和hash算法相关。并且分配越平均,越快。当然最快的情况肯定是一个键对应一个槽

链接法性能分析

既然我们的操作效率和hash算法非常相关,那么,什么样的hash函数才是一个号的hash函数呢?

让我们看看我们的目标

  • 我们想要把key均匀分布到slot
  • 他的输出不会过于和key的输入相关 比如输入偶数必然输出某个值

除法hash法

这就是一种经典的快速hash算法

h(k) = k mod m

k = 原始key m = hashTable的长度

但要注意,m也就是表的长度最好选择一个质数,否则其平均分布的特性会大打折扣

当然还有一些别的的hash方法,比如乘法hash

解决碰撞之二 开放寻址法

开放寻址法的核心思想是构建一个Hash序列,当序列中的hash1无法找到空位的时,继续调用hash2,知道hash出一个插槽正好是空时,插入。查找也很类似,需要注意的是,这种方法在槽中是需要保存原始关键字的,因为在搜索的时候,需要比对原始key是否一致。

这种方法最大的缺陷就是删除起来非常的麻烦。

开放寻址法性能分析

既然核心是一个hash队列,那么我们的性能明显就和Hash算法的速度,整个实际运行序列的长度相关。

线性探查

给定一个普通的散列函数,获取一次h(key) 接下来遍历数组进行遍历(从h(key开始),到末尾,又从t[0]开始,到h(k) - 1 结束),查找空位并插入,这就是线性探查,整个序列的最大长度就是m,他的理解和实现都相当的简单,但是问题也是存在的,这就是一次群集 。说白了就是槽很容易一大片都是满的,这样就不能实现很快速的插入了。并且会越来越严重,因为你本身插入就是在满的后面的空位插入。

二次哈希

h(k,i) = (h1(k) + ih2(k))mod m

h1 和 h2 是hash函数 ,第i次的探查位置等于 上次探查的位置+这次计算出的hash模m,也就是说每次的探查会变的比较有跳跃性,并且和上一次探查相关,整体分布就会比较平均。