数据结构系列之二 散列表

  • 2018-06-21
  • 197
  • 0

散列表也叫哈希表。在不同的编程语言里面,有不同的名字:Dict(Python)、map(Golang)、HashMap(Java)…… 但其实都是一个东西。

什么是散列表

如果我们现在有一组 key-value 形式的数据(是一个初中班级某次考试成绩):

学生编号成绩
3100
1034
2345

想把这一组数据存放起来非常容易,有很多种方法。如果说,我想要达到读取和写入都在一个恒定的时间范围内,这个该如何存储呢?

最简单的方法,就是将 学生的编号 作为数组的下标,成绩作为值来存放。这样,在每次获取学生成绩,或者更新成绩的时候,都可以直接通过数组下表来对对应的学生进行操作,时间就是恒定的了。

在上面这个例子中,我们的实验数据有两个隐藏的假设:

  1. 学生的编号是唯一的
  2. 一个班级的编号不会很多

如果我们想把这个程序推广到给全校去使用呢?那样学生的编号就会很大,用数组存放还合适吗?

当然不合适了,因为,一个学生在全校的编号会有很多信息在编号中,这样会使得编号非常的大,达到 8,9位数组。如果我们用刚才的方法来存放。就会有问题。因为我们不可能去开辟一个这么大的数组来存放数据。在空间上来说,这是不可接受的。

那么有没有一种办法可以存放用这个方法来存放这些数据,又不会出现占用太多空间的问题?

这里就需要用到散列表。

散列表是一种典型的空间和时间上折中的数据结构。

把 key-value 结构中的key通过函数映射在一个固定的索引上。数组索引处就是其对应的值,这就是散列表。

将key映射成固定的索引的这个函数,我们称之为 散列函数(Hash Function)。理论上来说,只要有一个合适的散列算法,散列函数可以将将不同类型的源数据转换成一个固定范围内的索引。

有了这样的函数,我们的key 就不再局限于使用数字,而是可以使用很多其他类型,由散列函数经过处理,最后转换成数字的索引。

在理想的情况下,不同的key都能转换为不同的索引。但散列函数是不能保证这一点的,也就是说,不同的key,经过散列之后,有可能成为一样的索引,我们还需要考虑到转换后发生冲突的情况。

所以,这里我们就需要了解组成整个哈希表的两个重要因素:

  1. 解决索引冲突
  2. 散列函数

如何解决冲突

目前来说,解决冲突,一般分为两种:

  1. 开放寻址法
  2. 拉链法

开放寻址法

插入值

当要插入散列表的索引有冲突的时候,会以 N(N>=1) 的步进值向前寻找,直到找到一个空位可以插入这个key。

如上图所示(步进值 N=1),元素A 想要放入到散列表:

  • 将其散列之后,得到了索引 1
  • 在插入的过程中发现 索引1 已经被D占用
  • 向前寻找空位,发现索引2被 B 占用
  • 继续向前寻找,找到 索引3 为空位,将A放入

这就是开放寻址法的基本思想。如果到了数组末尾都没有找到空位,则从数组开头继续找。

使用开放寻址法,散列表可能会被装满。

假设散列表容量是\(M\),要存储的元素个数是\(N\),假设散列表一个装载因子是 \(\alpha = \frac N M (N \le m)\),那么就可以知道永远有: \(\alpha \le 1\)。

查找key

  • 比对索引中的 key 是否和 要查找的 key 相等
  • 如果不等,则向前寻找
  • 如果遇到空位,则表示没有这个key

散列表的插入和查找的速度,都依赖于装载因子。当装载因子越大,因为要遍历找到空位,查找和插入耗时就越多。

删除key

有些读者可能会想到,在我们从散列表删除元素的时候,会有些麻烦。比如按照我们刚才的方法,将 A 插入了 索引 3 的位置,并将 索引1的D元素 删除,散列表内部变成如下图所示:

这时,我们想要从列表中拿出 key 为 A 的数据:

  • 散列函数将 A 散列为 索引 1
  • 索引 1 中没有数据
  • 认为 散列表中没有 key A (问题

开放寻址法中,删除是一件比较麻烦的事情在删除了冲突的数据之后,散列表中的数据获取会有问题。当然,这个我们是有解决办法的,可以通过在删除索引的地方添加标识,比如将索引的key设置为 “DELETED”,在查找时自动跳过带有这个标识的索引。

但一般来说,我们通过拉链法来解决这个问题。

拉链法

拉链法很好理解:我们将数组的每一个节点都实现成了一个链表,每一个索引都是链表的头,如下图:

当出现冲突的时候,就在当前索引的链表上增加一个节点。查找时,先找到对应的索引,然后遍历整个链表,来比对上面的key,最后确定是否有这个元素。

在拉链法中,负载因子依然影响算法的CURD的速度。如果一个索引下的链表太长的话,就会造成散列表操作的耗时太长。最坏的情况下,所有的key都集中在了一个索引上,造成这个索引下的链表等于散列表当前的总数。其查找的时间复杂度就编程了 \(O(n)\)

在 JDK1.8中,Java对于超过 8个节点的索引进行了特殊处理,从链表转为了红黑树,这样就使得在冲突加剧,一个索引下太多key时,时间复杂度从 \(O(n)\) 降到了 \(O(log^n)\)

散列函数介绍

散列函数,也可以叫哈希函数。

A hash function is any function that can be used to map data of arbitrary size to data of a fixed size. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. — Wikipedia

一个好的哈希函数,应该能够做到将不同的key均匀的散列到一个固定的索引范围之内。这样就可以避免一个索引下有太多的key。

Java 中 hash 算法实现

在 Java 中,任何一个对象都默认实现了 hashcode方法,在Java的 HashMap 中,也是使用这个hashcode方法进行计算哈希。

对于不同的类型,hashcode 方法也用了不同的实现。我们这里举两个例子来说明:

String.hashcode()

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

字符串的hashcode,通过处理每一个字符的 Unicode 编码或 ASCII 编码,做下面的运算,来得出hashcode。
S表示字符,下标表示第几个字符,n表示字符总数。算法的公式如下:

\[S_0 \cdot 31^{(n-1)} + S_1 \cdot 31^{(n-2)} + … + S_n\]

有些同学对上面的公式到算法实现的过程有些疑惑,这里简单的说一下:

根据代码可以得出以下的结论

  • 当 \(n=1\), 令 \(t_1=S_0\)
  • 当 \(n=2\), 令 \(t_2=t_1 \times 31 + S_1\)
  • 当 \(n=3\), 令 \(t_3=t_2 \times 31 + s_2\)

将 \(t_1\)、\(t_2\) 带入 \(t_3\),计算结果:
\[t_3=(S_0 \times 31 + S_1) \times 31 + S_2 = S_0 \times 31^2 + S_1 \times 31 + S_2 \]

当 字符数为n时,可以推导出公式:

\[\Rightarrow S_0 \cdot 31^{(n-1)} + S_1 \cdot 31^{(n-2)} + … + S_n\]

算法实现符合公式表述。

对于常数 31是怎么来的,这里有个说法:

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) – i. Modern VMs do this sort of optimization automatically. — 《Effective Java》

Long.hashcode

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

这个就比较简单了。因为Java 的 hashcode 返回一个 int,所以这里只是把 Long 的高32位和低32做了异或,让高位也参与运算,然后返回。

Resizing

哈希表一定是动态的,当数组无法满足需求时,就要扩展,这个时候就面临两个开销巨大的操作:

  1. 申请新的数组
  2. 重新计算已有的每个key的索引位置,并放入新数组

所以,我们在使用哈希表的时候,应该尽量的避免在使用的时候频繁的扩容,应该对使用需求有一个大概的估算。

在 JDK1.8中,HashMap 有一些比较大的变化。同时用了一些巧妙的技巧,使得重新计算索引的时间降低很多。这个有兴趣的同学可以读一下源码,并不复杂。

总结

上面讲了 哈希表最重要的3个地方,这也是我们实现自己的哈希表的三个比较重要的点。对于哈希函数来说,现代语言都会提供一些库来实现各种类型的哈希。对于我们自己的类型进行哈希的时候,就要对实际进行考量。实现一个分布均匀的哈希函数。在需要高性能的地方,一个哈希函数满足所有需求的“银弹”是不存在的。


作者和出处(reposkeeper) 授权分享 By CC BY-SA 4.0 Creative Commons License

关注微信公众号,获取新文章的推送!
qrcode

评论

还没有任何评论,你来说两句吧

发表评论

*

code