淺談哈希表存儲效率一般不超過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的時間復雜度計算公式為：

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++中的類模板詳解及示例
我們在定義函數(shù)時，可以通過定義函數(shù)模板，來簡化一些功能相同而數(shù)據(jù)類型不同的函數(shù)的定義和調(diào)用過程
2013-10-10
C語言實現(xiàn)經(jīng)典24點紙牌益智游戲
這篇文章主要為大家詳細介紹了C語言實現(xiàn)經(jīng)典24點紙牌益智游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2019-10-10
關(guān)于STL中的map容器的一些總結(jié)
對于map的學習，或者說是對STL中的容器的學習，要知道每種容器的實現(xiàn)原理，每種適合適合解決什么問題的，才是關(guān)鍵
2013-09-09
C++中關(guān)于constexpr函數(shù)使用及說明
這篇文章主要介紹了C++中關(guān)于constexpr函數(shù)使用及說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-11-11
C++取得本機IP的方法
這篇文章主要介紹了C++取得本機IP的方法,代碼簡單功能實用,具有不錯的借鑒參考價值,需要的朋友可以參考下
2014-10-10
C語言學習筆記之字符串間的那些事
字符串是C語言中最重要的數(shù)據(jù)類型之一,最近借助《C Primer Plus》一書來學習C中的常用字符串操作,在此作為筆記記錄,下面這篇文章主要給大家介紹了C語言學習筆記之字符串間的那些事,需要的朋友可以參考下
2022-04-04
vscode工程中c_cpp_properties.json文件作用詳細說明
c_cpp_properties.json是Visual Studio Code的一個配置文件,用于定義C/C++編譯器的路徑、默認包含路徑和預處理器定義,這篇文章主要給大家介紹了關(guān)于vscode工程中c_cpp_properties.json文件作用詳細說明的相關(guān)資料,需要的朋友可以參考下
2024-08-08
Objective-C限制函數(shù)調(diào)用的頻率詳解
這篇文章主要給大家介紹了關(guān)于Objective-C限制函數(shù)調(diào)用的頻率的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧。
2017-12-12
C++中move的使用及說明
這篇文章主要介紹了C++中move的使用及說明,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2023-08-08
用C語言實現(xiàn)簡單的三子棋
這篇文章主要為大家詳細介紹了用C語言實現(xiàn)三子棋，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-06-06