Java数据结构和算法 - 哈希表

2021/07/26 algorithm 共 1518 字,约 5 分钟
Bob.Zhu

哈希表是基于数组的一种数据结构,他可以快速的插入和查找,不论哈希表中有多少数据,操作需要的时间 都接近常量的时间:O(1)的时间级。但哈希表也有一些缺点,数组创建后难以扩展。某些哈希表被基本填满 时,性能下降的非常厉害。而且,也没有一种渐变的方法可以以任何一种顺序(例如从小到大)遍历表中数据 项。如果需要这种能力,就只能选择其他数据结构。然而,如果不需要有序遍历数据,并且可以提前预测数 据量的大小,那么哈希表在速度和易用性方面是无与伦比的。

哈希化

哈希化,就是如何把关键字转换成数组下标,在哈希表中,这个转换通过哈希函数来完成。对于特定的关键 字,并不需要哈希函数,关键字的值可以直接用于数组下标。

冲突

把巨大的数字空间压缩成较小的数字空间,必然要付出代价,即不能保证哈希化后取得的下标地址是空白 单元。那有两种方法解决这个冲突问题:开放地址法 和 链地址法。

开放地址法

在开放地址法中,若数据不能直接放在由哈希函数计算出来的数组下标所指的单元时,就要寻找数组的其他 位置。有三种不同的方法:线性探测、二次探测 和 再哈希法。

线性探测

在线性探测中,线性地查找空白单元。如果5421是要插入数据的位置,它已经被占用了,那么就使用5422, 如果5422也被使用了,然后判断5423,以此类推,数组下标一直递增,直到找到空位。这就叫做线性探测。

聚集

哈希表中,一串连续的已填充单元叫做填充序列。增加越来越多的数据项时,填充序列变得越来越长。这 叫做 聚集

当哈希表边的越来越满时,聚集变得越来越严重。这导致产生非常长的探测长度,意味着存取序列最后的 单元会非常耗时。数组填的越满,聚集越可能发生。数组由一半数据项时,这通常不是问题,当三分之二 满的时候,情况也不会太坏。然后,如果超过这个界限,随着聚集越来越严重,性能下降也很严重。因此, 设计哈希表的关键是确保它并不会超过整个数组容量的一半,最多到三分之二。

二次探测

在开放地址法的线性探测中会发生聚集,一旦聚集形成,它会变得越来越大。哪些哈希化后的落在聚集范围 内的数据项,都要一步一步移动,并插在聚集的最后,因此使聚集变得更大。聚集越大,它增长的也越快。 二次探测是防止聚集产生的一种尝试,思想是探测相隔较远的单元,而不是和原始位置相邻的单元。

步骤是步数的平方:在线性探测中,如果哈希函数计算的原始下标是x,线性探测就是 x+1,x+2,x+3, 以此类推;而在二次探测中,探测的过程是 x+1,x+4,x+9,x+16,以此类推。也就是到原始位置的距离 是步数的平方:x+1^2,x+2^2,x+3^2,x+4^2,等。

虽然二次探测解决了线性探测中产生的聚集问题,但依然会产生冲突的情况,这个现象叫做二次聚集。这 虽然不是一个严重的问题,但二次探测不会经常使用,因为还有稍微好些的解决方案。

再哈希法

二次聚集产生的原因是,二次探测的算法产生的探测序列步长总是固定的:1、4、9、16,以此类推。现在 需要一种方法产生一种依赖关键字的探测序列,而不是每个关键字都一样。那么,不同的关键字即使映射到 相同的数组下标,也可以使用不同的探测序列。方法是把关键字用不同的哈希函数再做一次哈希化,用这个 结果作为步长,对指定的关键字,步长在整个探测中是不变的,不过不同的关键字使用不同的步长。经验 说明,第二个哈希函数必须具备如下特点:

  • 和第一个哈希函数不同
  • 不能输出0

链地址法

链地址法中解决冲突的方式,不是寻找新的下标地址,而是将相同下标的元素组成链表,放在同一个下标 位置。装载因子通常为1,在这种情况下,大约三分之一的单元是空白单元,三分之一的单元有一个数据项, 三分之一的单元有两个或更多的数据项。

参考资料

文档信息

Search

    Table of Contents