哈希娱乐 行业新闻 党建先锋

为什么都用哈希Hash 表的时间复杂度为什么是 O(1)?哈希游戏

发布时间:2025-05-11 13:57:00  浏览:

  哈希游戏作为一种新兴的区块链应用,它巧妙地结合了加密技术与娱乐,为玩家提供了全新的体验。万达哈希平台凭借其独特的彩票玩法和创新的哈希算法,公平公正-方便快捷!万达哈希,哈希游戏平台,哈希娱乐,哈希游戏

为什么都用哈希Hash 表的时间复杂度为什么是 O(1)?哈希游戏

  【摘要】 写在前面博文内容为哈希表的简单认知涉及Hash表的索引计算,长度计算,以及如何减少哈希冲突,一致性哈希认知理解不足小伙伴帮忙指正 :),生活加油生如夏花之灿烂,死如秋叶之静美。—— 泰戈尔 《生如夏花》Hash 表的时间复杂度为什么是 O(1)讲 Hash 之前,简单聊聊数组(直接寻址表)数组数组是内存中一块连续的空间,并且数组中必须存放相同的类型,所以存放数组只需要记住 首地址的位置就可以...

  涉及Hash表的索引计算,长度计算,以及如何减少哈希冲突,一致性哈希认知

  数组是内存中一块连续的空间,并且数组中必须存放相同的类型,所以存放数组只需要记住 首地址的位置就可以,而且数组的长度必须是定长。

  以 int 数据类型为例,每个 int 占 4 字节内存空间,所以对一个一个长度单位为 5 的整形数组,所占用的字节为 4*5=20 字节,知道首地址,数组每个元素定长,可以轻易算出每个数据的内存下标地址。

  在这个例子中,arr[0]存储在内存地址1,arr[1]存储在内存地址2,依此类推。每个元素之间的间隔是4个字节(一个整数的大小)。

  所以只读取数组元素的时候,可以直接通过下标,也就是索引进行读取,即我们常讲的直接寻址,时间复杂度为O(1). 所以在算法导论中也会把数组称为直接寻址表

  随机快速读写是数组的一个特性,在 Java 中有个 标志性接口RandomAccess用于表示此类特性,比如我们经常用的ArrayList

  这也是常讲 对于ArrayList来说 通过索引访问要优于通过迭代器访问。知道索引下标后,下标乘以元素大小,再加上数组的首地址,就可以获得目标访问地址,直接获取数据。通过迭代器方法,需要通过方法先获取索引,中间多了一步,并且最好指定初始容量,数组定长,所以每一次的扩容都要进行一次数组拷贝

  在数组的情况下,由于元素是连续存储的,序列化过程可以直接将整个内存块复制到磁盘或网络中,这样可以减少 CPU 的开销,提高效率。所以数组尤其适合于需要高性能数据传输的场景。

  相比在链表中,由于节点是分散存储的,序列化时必须遍历每一个节点,将其值逐个写入到连续的内存中,这样不仅需要更多的计算时间,还可能在内存分配上引入额外的开销。

  回头来看Hash表,数组可以直接寻址,但是缺点很明显,必须定长,元素大小相等,实际中使用的时候,往往可能不知道需要多长,希望是一个动态集合。

  这个时候可以定义一个很大的数组,但是存在一种情况,当要存放的元素远远小于定义某个长度的数组的时候,就会造成资源浪费。

  所以我们需要一种数据结构来实现上面的功能,可以根据要放的元素动态的定义数组的大小,这也就是哈希表,算法导论中也叫散列表。

  哈希表会通过哈希函数把要放的元素转换为一个哈希值,往往是一个 Int 型 的数值,如何得到索引,最简单的方法就是余数法,使用 Hash 表的数组长度对哈希值求余, 余数即为 Hash 表数组的下标,使用这个下标就可以直接访问得到 Hash 表中存储的数据。。每次读写元素的时候会计算哈希值得到索引然后读写。

  因为哈希函数的执行时间是常量,数组的随机访问也是常量,时间复杂度就是O(1)。

  在编程语言中,为了避免哈希冲突,会对哈希函数的数据做进一步处理,对于 Java 来讲,HashMap的hash方法接收一个Object类型的key参数,然后根据key的hashCode()方法计算出的哈希值h。

  然后会执行位运算h 16(将h的高 16 位右移 16 位),然后将结果与原始哈希值h进行异或操作(^),最后返回计算得到的哈希值。

  Object 的 哈希函数是一个原生的方法,即由 JVM 提供,可能通过 C 或者 C++ 实现。

  通过一个具体的例子来解释 Java 中HashMap的hash方法是如何工作的,以及为什么通过对原始哈希值的高 16 位和低 16 位进行异或操作可以减少哈希冲突

  通过对原始哈希值的高 16 位和低 16 位进行异或操作,HashMap的hash方法试图达到以下目的:

  当调用putVal方法插入键值对时,会传入通过hash方法计算得到的哈希值作为hash参数,然后计算索引

  索引的问题解决了,那么长度是如何解决的,我们知道既然使用数组,那么一定是定长才行

  和ArrayList类似,在Java中,Hash表的长度是有一个一个默认长度的,当负载因子超过阈值时会自动扩容,扩容同样涉及数组拷贝,哈希值计算。所以一般也需要指定初始容量。

  所以 Java 中在创建HashMap时,会根据初始容量和负载因子来确定实际的对象数组大小。需要注意HashMap的内部实现会确保实际容量为最接近且大于或等于给定初始容量的 2 的幂次方。这样可以充分利用位运算的优势,提高哈希表的性能。

  实际中指定初始容量后还会进行进一步的运算,例如,如果初始容量为 16,实际对象数组大小将为 16;如果初始容量为 17,实际对象数组大小将为 32(最接近且大于 17 的 2 的幂次方)。

  可以看到在 Java 中,这里使用了位运算,而不是之前我们讲的取模运算,

  位与运算(bitwise AND)和取模运算(modulo operation,使用%符号)都可以用来将哈希值映射到哈希表的索引范围内,但它们的工作原理和适用场景有所不同。

  位与运算(bitwise AND) ,当哈希表的大小是2的幂时,可以使用位与运算来计算索引,这种方法的优点是速度快,因为它只涉及一次位运算。但是,它要求哈希表的大小必须是2的幂。

  取模运算(modulo operation),取模运算可以用于任何大小的哈希表,不仅限于2的幂:

  这也是上面为什么要容量是2的幂,除法运算通常比位运算慢,位运算可以直接映射到硬件层面操作。

  那么位运算又是如何计算出索引的?这里的原理是基于二进制的特性以及位运算的规则。

  首先,数组的大小是 2 的幂次方,例如 16(2^4)。当数组大小为 2 的幂次方时,它的二进制表示形式中只有一个位为 1,其余位为 0。例如,16 的二进制表示为10000。

  对哈希码和数组大小减 1(例如 15,见上面的公式)进行按位与运算时,实际上是在将哈希码的二进制表示中的高位全部置为 0,只保留低位的数值。这是因为数组大小减 1 的二进制表示形式中,所有低位都为 1,而高位都为 0。例如,15 的二进制表示为01111。

  通过按位与运算,我们可以得到哈希码的低 4 位(在这个例子中),这些低 4 位就是我们要找的索引值。这个过程相当于对哈希码进行模运算(取余数),使用位运算来实现会更高效。这里也可以看到扰动函数的作用,利用高位影响低位。

  在Java 中当哈希表的元素个数超过容量乘以加载因子(默认为0.75)时,会触发扩容,扩容会重新计算大小,扩容后的大小为。newCap = oldCap 1,即左移一位,增加当前容量的一倍。

  实际上在 Java 中,,如果类实现了哈希方法,会使用自己覆盖的哈希方法,如果关键字是字符串,会使用BKDR哈希算法将其转换为自然数,再,对它进行求余,就得到了数组下标。

  当多个不同的元素通过哈希函数生成的哈希值后计算的索引一样,就会触发哈希冲突

  我们看一个生产的 Demo,下面为两个楼宇编码,需要批量生成每栋楼房间的锁号,这里我们通过楼宇编码生成哈希值,拼接到锁号最前面当楼宇标识。

  这两个字符串都会落到下标 4 中,这就产生了冲突。就会促发哈希冲突,解决办法一般有两种:

  落到数组同一个位置中的多个数据,通过链表串在一起。使用哈希函数查找到这个位置后,再使用链表遍历的方式查找数据。Java 中的哈希表就使用链接法解决冲突。在 Java8 之后,链表节点超过8个自动转为红黑树,小于6个会自动转为链表。

  链表法即把冲突的元素放到一个链表里面,链表第一个元素地址放到哈希表索引的元素位置。

  所以说最坏的情况下,即所有的元素都哈希冲突,时间复杂度为链表的时间复杂度O(n).

  插入时若发现对应的位置已经占用,或者查询时发现该位置上的数据与查询关键字不同,开放寻址法会按既定规则变换哈希函数(例如哈希函数设为 H(key,i),顺序地把参数 i 加 1),计算出下一个数组下标,继续在哈希表中探查正确的位置,

  实际中可能还要做容量检测,避免死循环。在选择冲突解决策略时,需要综合考虑以下因素:

  内存使用:如果内存连续性和序列化效率是关键,开放寻址法可能更适合,尤其是在需要高效序列化的情况下。链接法虽然更灵活,但可能会因为指针和内存不连续性导致序列化和备份成本增加。

  数据大小和存储:对于大型哈希表,应该关注内存布局和存储策略,采用分块、压缩或稀疏存储等方式来优化序列化过程。

  性能和一致性:在使用内存映射等技术时,确保数据的一致性和完整性依然是关键,可能需要额外的同步操作。

  理论上频繁发生哈希冲突时,会直接影响时间复杂度,所以检索速度会急剧降低,通过哪些手段减少冲突概率?

  装载因子(当前元素个数/数组容量)越接近于 1,冲突概率就会越大。不能改变元素的数量,只能通过扩容提升哈希桶的数量,减少冲突。

  哈希表的扩容会导致所有元素在新数组中的位置发生变化,因此必须在扩容过程中同时保留旧哈希表和新哈希表。扩容时,需要遍历旧哈希表中的所有元素,并使用新的哈希函数将它们重新放入合适的新哈希桶中。

  上面我们讲到Java中HashMap会在数组元素个数超过数组容量的0.75进行扩容, 扩容机制与上面类似,扩容后的容量始终为 2的幂,

  比如如何HashMap的初始容量设置为100,那么扩容后的容量将按照以下公式计算:

  在这种情况下,oldCapacity 是初始容量 100。但是,HashMap 的容量始终是 2 的幂次方,因此实际的初始容量会被调整为大于或等于100的最小的 2 的幂次方,即128(2^7)。

  当HashMap需要扩容时,新的容量将是当前容量的两倍。因此,如果初始容量为 128,扩容后的新容量将是:

  所以,初始容量设置为 100,扩容后的容量将为 256。这一过程涉及大量数据操作,扩容是一个极其耗时的操作,尤其在元素数量达到亿级时。

  所以在初始化的时候制定容量很有必要,会避免多次扩容,同时可以考虑其他的扩容手段,比如渐进式扩容和双缓存技术.

  上面我们讲到 Java 中 String 类通过 BKDR 哈希算法计算哈希值,这里的31为基数,哈希函数为什么基数必须是素数,欢迎小伙伴们留言讨论 ^_^

  它的计算量很小:n*31,实际上可以通过先把 n 左移 5 位,再减去 n 的方式替换,即(n*31 == n5 - n),因为理论上位运算通常比乘法运算更快

  也可以使用其他的哈希算法,或者双重哈希处理,在分布式场景通过一致性哈希来处理数据的均匀分布,分散数据,降低局部密度,提交分布均匀性,减少冲突的概率。

  分布式系统中数据分布和负载均衡会经常使用一种叫一致性哈希(Consistent Hashing)的技术。用于解决在集群节点变化(如添加或移除节点)时,如何最小化数据迁移的问题(Ceph,Redis)。以及在网络协议层流量负载均衡如何选择合适的后端节点(haproxy)。

  一致性哈希将整个哈希值空间视为一个虚拟的环。每个节点(如服务器)和数据项(如缓存中的数据)都通过哈希函数映射到这个环上。

  比如Redis Cluster将整个数据集划分为 16384 个哈希槽。每个键通过哈希函数(CRC16)计算出一个哈希值,然后对 16384 取模,得到该键对应的哈希槽。每个节点负责一部分哈希槽。

  节点和数据项都被哈希到这个环上。数据项被存储在顺时针方向的第一个节点上。例如,如果数据项A被哈希到位置x,而节点N1在x的顺时针方向上,那么A就存储在N1上。

  通过将数据均匀地分布在环上,可以实现负载均衡。即使添加或删除节点,也只会影响到少量数据项的迁移。总体的哈希容量不变,所以计算完的哈希值不会变,只是对 Hash 空间细划。

  最小化数据迁移:当节点加入或离开时,只需重新映射少量数据项,而不是重新分配所有数据。这使得系统在扩展或缩减时更为高效。

  动态扩展:系统可以在不影响现有数据的情况下动态扩展,增加新的节点或移除旧的节点。

  输出结果,可以看到删除 Node2 之后,Node3 和 Node1 之前映射的数据并有没有改变,只是原来Node2 的数据被映射到了 Node3