本文主要是講"哈希表的存儲(chǔ)效率一般不超過(guò)50%"的原因。

Hash Table 常用于頻繁進(jìn)行 key/value 模式的查找中。(查找模式，如匹配查找)

哈希表最大的優(yōu)點(diǎn)在于查找速度快，但存儲(chǔ)時(shí)可能發(fā)生collision(沖突)。

哈希表大多使用open addressing來(lái)解決collision，此時(shí)search的時(shí)間復(fù)雜度計(jì)算公式為：

1/( 1 - n/m )

其中，n與m分別表示存儲(chǔ)的記錄數(shù)與哈希表的長(zhǎng)度，即裝填因子( load factor )

故，若哈希表半滿，即 n/m >= 1/2，則每次的search次數(shù)可能會(huì) >= 2

因此，為了保證Hash Table在 key/value 查找模式中的優(yōu)勢(shì)，一般，其存儲(chǔ)效率不會(huì)超過(guò)50%。

以上就是小編為大家?guī)?lái)的淺談哈希表存儲(chǔ)效率一般不超過(guò)50%的原因全部?jī)?nèi)容了，希望大家多多支持我們~