本文主要是讲”哈希表的存储效率一般不超过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%的原因分享!全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/481933.html