当前位置: 首页 > 编程笔记 >

浅谈哈希表存储效率一般不超过50%的原因

百里丁雨
2023-03-14
本文向大家介绍浅谈哈希表存储效率一般不超过50%的原因,包括了浅谈哈希表存储效率一般不超过50%的原因的使用技巧和注意事项,需要的朋友参考一下

本文主要是讲"哈希表的存储效率一般不超过50%"的原因。

Hash Table 常用于频繁进行 key/value 模式的查找中。(查找模式,如匹配查找)

哈希表最大的优点在于查找速度快,但存储时可能发生collision(冲突)。

哈希表大多使用open addressing来解决collision,此时search的时间复杂度计算公式为:

1/( 1 - n/m )

其中,n与m分别表示存储的记录数与哈希表的长度,即装填因子( load factor )

故,若哈希表半满,即 n/m >= 1/2,则每次的search次数可能会 >= 2

因此,为了保证Hash Table在 key/value 查找模式中的优势,一般,其存储效率不会超过50%。

以上就是小编为大家带来的浅谈哈希表存储效率一般不超过50%的原因全部内容了,希望大家多多支持小牛知识库~

 类似资料:
  • 给定两个字符串,比如hashKey和hashVal,我将这两个字符串添加到一个hash对象中。在本例中,hashVal是一个表示整数的字符串,因此我在将其存储到表中之前将其解析为整数。 现在问题来了。存储在哈希表中的值实际上是一个int32对象,这使得后面使用内部表达式很麻烦。经过长时间的查找,我无法找到一种简单的方法来存储实际的int或提取存储为int而不是int32对象的值。 下面是我尝试做的

  • 问题内容: 我对哈希表的基本概念感到困惑。如果我要编码一个哈希,我什至会开始吗?哈希表和普通数组之间有什么区别? 基本上,如果有人回答了这个问题,我想我的所有问题都会得到回答:如果我有100个随机生成的数字(作为键),那么我将如何实现哈希表,以及为什么它比数组有优势? 伪代码或Java将被视为一种学习工具… 问题答案: 到目前为止的答案已经帮助定义了哈希表并解释了一些理论,但是我认为一个示例可能会

  • HASH 哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素。但反过来,集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素,这样的映射被称为一一映射。这样的对应关系在现实生活中很常见,比如: A -> B 人 -> 身份证号 日期 -> 星座 上面两个映射中,人 ->

  • 问题内容: 如果我将函数名称存储为字符串在Hashtable中。 有没有办法通过存储的字符串访问函数? 编辑恐怕我在CLDC1.1 / MIDP2.0上工作的平台不支持反射。 有什么解决方法? 问题答案: 只需使用一长串else-ifs: (尽管我通常不喜欢尝试在源代码中进行垂直对齐,但我认为在这种情况下这样做是值得的。) 在映射中存储函子是一种替代方法,对于许多MIDP应用程序,bu可能会增加对

  • 问题内容: 当大小超过maxthreshold值时,如何在哈希表或哈希表中进行重新哈希处理? 是否所有对都已复制到新的存储桶阵列中? 编辑: 重新哈希后,同一存储桶(位于链接列表中)中的元素会发生什么情况?我的意思是说,他们在重新哈希处理后会留在同一个桶中吗? 问题答案: 问题中的最大阈值称为负载系数。 建议负载系数约为0.75。负载因子定义为(m / n),其中n是哈希表的总大小,m是在需要增加

  • 问题内容: 我在Redis中存储MessagePacked哈希时遇到问题。我在下面粘贴了一个测试用例。从Redis中提取打包数据并对其进行解压缩时,哈希会略有损坏。当哈希值超出一定长度时,似乎会发生这种情况,尽管我不能肯定地说。 我正在使用Redis 2.4.17(默认配置),Ruby 1.9.3p194,MessagePack 0.4.7和Redis gem 3.0.2。使用节点也会发生相同的问