查看: 307|回复: 1

[Java学习] 几分钟理解 数据结构 - 哈希表及其优化

发表于 2017-8-13 08:27:23
小概

哈希容器也可以理解为是一种映射容器,采用哈希算法(映射算法,散列算法),将不定长的数据压缩成定长的数据,这串定长值我们称为 哈希值,并将不同的哈希值分组存起来,每一个分组我们认为是一个

我们将不同的数据格式通过哈希算法,将其映射到不同的槽内,当我们需要取数据时,把需要的数据转化成哈希值,再凭借哈希值去找对应的槽,然后便可以将数据取出来

可以理解为一个键值对容器

put(key, value)

get(key)

图解如下

并且进行以下设定

$key$ - 键

$h_{key}$ - 哈希值

$hash(key)$ - 哈希算法

$bucket$ - 槽

$bucketNum$ - 槽数

哈希表

我们现在假设 key 为整数,用 数组 分配槽的情况,并开始讨论如何设计,让对这一容器增删改查的时间复杂度趋近于 $O(1)$

哈希算法

映射可以如下表示,下标 $n$ 代表变化的取值

$$(x_n, y_n) -> (x, y)$$

更通常的映射关系如下,并且我们在这里讨论这种情况
$$(x_n, y_n) -> (0, bucketNum - 1)$$

如何将不定长的数据压缩成定长的数据,我们主要给出以下几种常用的方法

线性哈希:$hash(key) = a × key + b $

平方哈希:$hash(key) = sub(key^2, a, b)$,设函数 $sub(num, a, b)$ 代表取 $num$ 第 $a$ 位数到第 $b$ 位数,则

余数哈希:$hash(key) = key % a $

入槽

设 $bucketNum = 4,hash(key) = key % 4$,我们现在要对一对值为 6-'6号书籍' 的键值对进行如下操作

  1. hashMap.put(6, '6号书籍');
  2. hashMap.get(6);
复制代码

那么,$hash(6) = 2$,并把 '6号书籍' 存入 $bucket[2]$ 中,查询时再取出 $bucket[h_6]$

碰撞处理

我们处理$(x_n, y_n) -> (0, bucketNum - 1)$映射时,不定长的数据集可以认为是无穷大的,现在要将无限大的数据集压缩进有限数据集内,一定会引发 碰撞,即不同的数据装入一个槽内

解决冲突的方法有很多,我们主要给出以下几种常用的方法:

再哈希:遇到碰撞时,将哈希值再哈希,直到无碰撞

公共溢出区:将碰撞数据存入其中

接数据结构:碰撞时,往该槽内接入其他数据结构,并把膨胀的数据存入其中,如图解中接的就是 链表

性能瓶颈

现在开始讨论如上设计哈希表的性能问题

我们在对容器进行操作时,处理最频繁的便是 $hash(key)$,每次存储和查找都需要计算 $h$,所以 如何设计哈希算法 便显得十分重要

另一个瓶颈在于,如何更加合理地分配 $ bucketNum $,能够尽可能地减少冲突,这也是一个值得思考的方面,我们要知道虽然我们对碰撞已经进行过处理,但这步操作也会损耗相当的效率

退一步来讲,假设已经出现碰撞,如何处理碰撞、碰撞的数据应当如何搜索 也非常值得我们考虑,比方说,若采用的是如图解中的链表法,假设 $bucketNum = 100$,但一堆数据很不幸运地落入同一个 $bucket$ 内,那么我搜索这堆数据时,和遍历搜索已经基本没区别了,时间复杂度趋近与 $O(n)$



回复

使用道具 举报

发表于 6 天前
百度(常州)创新中心,坐落于江苏省常州市钟楼区科技街。
是长三角首家百度创新中心,由钟楼区政府、百度公司、三艾网络三方联合打造。
为常州市初创型互联网企业提供互联网孵化服务。
欢迎各方各界前来参观指导!
我们真挚欢迎您的到来!







回复 支持 反对

使用道具 举报