【图解数据结构】外行人也能看懂的哈希表(下)

简介: 常用英文单词20万个,假设单词平均长度10个字母,平均一个单词占用10字节,那20万英文单词大约占2MB存储空间,这完全可以放在内存。所以我们可以用散列表来存储整个英文单词词典。 当用户输入某个英文单词时,拿用户输入的单词去散列表中查找: 查到,则说明拼写正确 没有查到,则说明拼写可能有误,给予提示 这就能轻松实现快速判断是否存在拼写错误。

4 扩容

  • 没有频繁插入和删除的静态数据集合,即使实习生也能轻松根据数据特点,设计出优秀的hash函数
  • 而动态hash表,数据频繁变动,无法预估数据个数,所以无法预申请一个足够的hash表。随数据越多,装载因子就会慢慢变大。当装载因子大到一定程度后,哈希冲突就会令程序窒息,此时资深的程序员们该咋办呢?

针对hash表,当 loadFactor 过大,可进行动态扩容,新申请更大的hash表,将数据迁移至新hash表。

假设每次扩容,申请一个原来hash表两倍size的。若原hash表装载因子0.8,则扩容后的新hash表装载因子就降为原来的一半0.4了。

但hash表的扩容,数据搬移操作要复杂很多。因为哈希表的大小变了,数据的存储位置也变了,需通过hash函数重新计算每个数据的存储位置。

原来hash表的21存储在0位,迁移新hash表后存储在7位。

image.png

动态扩容的散列表,插入操作的时间复杂度是多少呢?


插入一个数据:


最好无需扩容,时间复杂度O(1)

最坏情况,hash表loadFactor过高,开启扩容新申请内存空间,重新计算哈希位置并迁移数据,时间复杂度O(n)。用摊还分析法,均摊情况下,时间复杂度接近最好情况,就是O(1)。

动态散列表,随着数据的删除,散列表中的数据会越来越少,空闲空间会越来越多。

如果对空间消耗非常敏感,可以在装载因子小于某个值之后,启动动态缩容。

如果更在意执行效率,能够容忍多消耗一点内存空间,就不用费劲缩容。

避免低效扩容

大部分情况下,动态扩容的hash表插入一个数据都很快,但特殊情况下,当装载因子达阈值,需先扩容,再插数据。这时,插入数据就会变得很慢!

若hash表当前大小为1G,想扩容为原来2倍,就需对1G数据重新计算哈希值并从原hash表搬移到新表,听着都耗时!

所以这时,“一次性”扩容机制就不合适了。


为避免一次性扩容耗时过多,可将扩容操作穿插在插入操作的过程中分批完成。当装载因子达阈值后,只申请新空间,但并不将老数据搬移到新hash表。


当有新数据插入,将新数据插入新hash表中,并从老原hash表拿出一个数据放入新hash表。

每次插入一个数据到散列表,重复上面过程。

经过多次插入操作之后,原hash表的数据就一点点都迁移至新hash表。这就不会一次性数据搬移,插入操作就都变得很快了。

image.png

这期间的查询操作怎么做?

为兼容新、老hash表数据,先查新hash表,没找到再去原hash表查找。


通过这样的均摊,将一次性扩容代价,均摊到多次插入操作,解决一次性扩容耗时过多问题。这时任何情况下,插入一个数据的时间复杂度都是O(1)。


应用

强大的 HashMap

1.初始大小

HashMap默认的初始大小是16,当然这个默认值是可以设置的,如果事先知道大概的数据量有多大,可以通过修改默认初始大小,减少动态扩容的次数,这样会大大提高HashMap的性能。


2.装载因子和动态扩容

最大装载因子默认是0.75,当HashMap中元素个数超过0.75*capacity(capacity表示散列表的容量)的时候,就会启动扩容,每次扩容都会扩容为原来的两倍大小。


3.散列冲突解决方法

HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理,也免不了会出现拉链过长的情况,一旦出现拉链过长,则会严重影响HashMap的性能。


于是,在JDK1.8版本中,为了对HashMap做进一步优化,我们引入了红黑树。而当链表长度太长(默认超过8)时,链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点,提高HashMap的性能。当红黑树结点个数少于8个的时候,又会将红黑树转化为链表。因为在数据量较小的情况下,红黑树要维护平衡,比起链表来,性能上的优势并不明显。


4.散列函数

散列函数的设计并不复杂,追求的是简单高效、分布均匀。我把它摘抄出来,你可以看看。

int hash(Object key) {
    int h = key.hashCode();
    return (h ^ (h >>> 16)) & (capitity -1); //capicity表示散列表的大小
}

其中,hashCode()返回的是Java对象的hash code。比如String类型的对象的hashCode()就是下面这样:

public int hashCode() {
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0) {
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}

单词拼写检查功能是如何实现的?

常用英文单词20万个,假设单词平均长度10个字母,平均一个单词占用10字节,那20万英文单词大约占2MB存储空间,这完全可以放在内存。所以我们可以用散列表来存储整个英文单词词典。

当用户输入某个英文单词时,拿用户输入的单词去散列表中查找:

  • 查到,则说明拼写正确
  • 没有查到,则说明拼写可能有误,给予提示

这就能轻松实现快速判断是否存在拼写错误。

目录
相关文章
|
12月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
195 0
数据结构与算法学习十五:哈希表
|
7月前
|
存储 NoSQL Java
【数据结构进阶】哈希表
哈希表是一种高效的数据结构,通过哈希函数实现数据映射,支持平均O(1)时间复杂度的查找、插入和删除操作。本文详细介绍了哈希表的基本概念、哈希函数的设计(如直接定址法和除留余数法)以及哈希冲突的解决方法(如开放定址法和链地址法)。同时,文章通过代码实例展示了线性探测和链地址法两种哈希表的实现过程,并分析了各自的优缺点。最后总结指出,合理选择哈希函数和冲突解决策略是优化哈希表性能的关键。
448 2
|
10月前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
存储 Java Serverless
【数据结构】哈希表&二叉搜索树详解
本文详细介绍了二叉搜索树和哈希表这两种数据结构。二叉搜索树是一种特殊二叉树,具有左子树节点值小于根节点、右子树节点值大于根节点的特点,并且不允许键值重复。文章给出了插入、删除和搜索等方法的具体实现。哈希表则通过哈希函数将键名映射为数组下标,实现快速查找,其插入、删除和查找操作时间复杂度理想情况下为O(1)。文中还讨论了哈希函数的设计原则、哈希冲突的解决方法及哈希表的实现细节。
249 8
【数据结构】哈希表&二叉搜索树详解
|
12月前
|
存储 缓存 Java
【数据结构】哈希表
【数据结构】哈希表
166 1
|
存储 Java
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
这篇文章通过Java代码示例展示了如何实现哈希表,包括定义结点类、链表类、数组存储多条链表,并使用简单的散列函数处理冲突,以及如何利用哈希表存储和查询学生信息。
数据结构中的哈希表(java实现)利用哈希表实现学生信息的存储
|
存储 算法 NoSQL
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
数据结构和算法——哈希查找冲突处理方法(开放地址法-线性探测、平方探测、双散列探测、再散列,分离链接法)
670 1
|
存储 NoSQL 算法
redis数据结构—哈希表
redis数据结构—哈希表
118 0
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
存储 算法
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
数据结构和算法——了解哈希表(哈希查找、散列的基本思想)
126 0