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

更新時間：2017年01月06日 09:01:22 投稿：jingxian

下面小編就為大家?guī)硪黄獪\談哈希表存儲效率一般不超過50%的原因。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

本文主要是講"哈希表的存儲效率一般不超過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)容了，希望大家多多支持腳本之家~

您可能感興趣的文章:

相關(guān)文章

C++實現(xiàn)LeetCode(141.單鏈表中的環(huán))
這篇文章主要介紹了C++實現(xiàn)LeetCode(141.單鏈表中的環(huán)),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
2021-07-07
C語言實現(xiàn)的猜數(shù)字小游戲
這篇文章主要為大家詳細介紹了C語言實現(xiàn)的猜數(shù)字小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-01-01
C/C++實現(xiàn)7bit與8bit編碼互相轉(zhuǎn)換
這篇文章主要為大家詳細介紹了如何使用C/C++實現(xiàn)7bit與8bit編碼互相轉(zhuǎn)換功能,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學習一下
2024-10-10
C和C++中argc和argv的含義及用法詳解
argv 是 argument vector的縮寫，表示傳入main函數(shù)的參數(shù)序列或指針，這篇文章主要介紹了C和C++中argc和argv的含義以及用法,需要的朋友可以參考下
2022-11-11
C語言中sizeof函數(shù)踩過的坑總結(jié)
sizeof是C語言的一種單目操作符，如C語言的其他操作符++、--等。它并不是函數(shù)。sizeof操作符以字節(jié)形式給出了其操作數(shù)的存儲大小。操作數(shù)可以是一個表達式或括在括號內(nèi)的類型名。操作數(shù)的存儲大小由操作數(shù)的類型決定
2022-04-04
C++11的新特性簡單匯總介紹 (二)
最近學習了C++11的新特性，將學習內(nèi)容整理下來以鞏固記憶，這里分享給大家，希望對大家學習C++11能夠有所幫助
2016-07-07
詳解C++的String類的字符串分割實現(xiàn)
這篇文章主要介紹了詳解C++的String類的字符串分割實現(xiàn)的相關(guān)資料,需要的朋友可以參考下
2017-07-07
C++事件處理中__event與__raise關(guān)鍵字的用法講解
這篇文章主要介紹了C++事件處理中__event與__raise關(guān)鍵字的用法,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下
2016-01-01
C語言指針用法總結(jié)
本文詳細講解了C語言指針用法，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2021-12-12
C++實現(xiàn)LeetCode(120.三角形)
這篇文章主要介紹了C++實現(xiàn)LeetCode(120.三角形),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
2021-07-07