本文主要是讲“哈希表的存储效率一般不超过50%”的原因。
哈希表常用于频繁进行键/值模式的查找中。(查找模式,如匹配查找)
哈希表最大的优点在于查找速度快,但存储时可能发生碰撞(冲突)。
哈希表大多使用开放寻址法来解决碰撞,此时搜索的时间复杂度计算公式为:
<强> 1/(1 - n/m)
其中,n与m分别表示存储的记录数与哈希表的长度,即装填因子()
故,若哈希表半满,即n/m祝辞=1/2,则每次的搜索次数可能会在=2
因此,为了保证哈希表在键/值查找模式中的优势,一般,其存储效率不会超过50%。
以上就是小编为大家带来的浅谈哈希表存储效率一般不超过50%的原因全部内容了,希望大家多多支持~
