溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

淺談哈希表存儲效率一般不超過50%的原因

發(fā)布時間：2020-09-09 10:06:46 來源：腳本之家 閱讀：357 作者：jingxian 欄目：編程語言

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

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

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

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

1/( 1 - n/m )

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

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

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

以上就是小編為大家?guī)淼臏\談哈希表存儲效率一般不超過50%的原因全部內(nèi)容了，希望大家多多支持億速云~

向AI問一下細節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手