淺談哈希表存儲(chǔ)效率一般不超過50%的原因
更新時(shí)間：2017年01月06日 09:01:22 投稿：jingxian
下面小編就為大家?guī)?lái)一篇淺談哈希表存儲(chǔ)效率一般不超過50%的原因。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來(lái)看看吧
本文主要是講"哈希表的存儲(chǔ)效率一般不超過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ì)超過50%。
以上就是小編為大家?guī)?lái)的淺談哈希表存儲(chǔ)效率一般不超過50%的原因全部?jī)?nèi)容了，希望大家多多支持腳本之家~
您可能感興趣的文章:
- 一文徹底搞定Java哈希表和哈希沖突
- Java代碼實(shí)現(xiàn)哈希表（google 公司的上機(jī)題）
- PHP哈希表實(shí)現(xiàn)算法原理解析
- JAVA中哈希表HashMap的深入學(xué)習(xí)
- 使用python實(shí)現(xiàn)哈希表、字典、集合操作
- python 哈希表實(shí)現(xiàn)簡(jiǎn)單python字典代碼實(shí)例
- java數(shù)據(jù)結(jié)構(gòu)和算法中哈希表知識(shí)點(diǎn)詳解
- JS模擬實(shí)現(xiàn)哈希表及應(yīng)用詳解
- C語(yǔ)言基于哈希表實(shí)現(xiàn)通訊錄
- C++ 實(shí)現(xiàn)哈希表的實(shí)例
- js實(shí)現(xiàn)HashTable(哈希表)的實(shí)例分析
- C#中哈希表(HashTable)用法實(shí)例詳解(添加/移除/判斷/遍歷/排序等)
- JavaScript中實(shí)現(xiàn)鍵值對(duì)應(yīng)的字典與哈希表結(jié)構(gòu)的示例
- 輕松學(xué)習(xí)C#的哈希表
- PHP內(nèi)核探索:哈希表碰撞攻擊原理
- java中哈希表及其應(yīng)用詳解
- C#使用foreach遍歷哈希表（hashtable）的方法
- Java實(shí)現(xiàn)哈希表的基本功能
相關(guān)文章
我們?cè)诙x函數(shù)時(shí)，可以通過定義函數(shù)模板，來(lái)簡(jiǎn)化一些功能相同而數(shù)據(jù)類型不同的函數(shù)的定義和調(diào)用過程2013-10-10
C語(yǔ)言實(shí)現(xiàn)經(jīng)典24點(diǎn)紙牌益智游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)經(jīng)典24點(diǎn)紙牌益智游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-10-10
對(duì)于map的學(xué)習(xí)，或者說是對(duì)STL中的容器的學(xué)習(xí)，要知道每種容器的實(shí)現(xiàn)原理，每種適合適合解決什么問題的，才是關(guān)鍵2013-09-09
C++中關(guān)于constexpr函數(shù)使用及說明
這篇文章主要介紹了C++中關(guān)于constexpr函數(shù)使用及說明，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了C++取得本機(jī)IP的方法,代碼簡(jiǎn)單功能實(shí)用,具有不錯(cuò)的借鑒參考價(jià)值,需要的朋友可以參考下2014-10-10
字符串是C語(yǔ)言中最重要的數(shù)據(jù)類型之一,最近借助《C Primer Plus》一書來(lái)學(xué)習(xí)C中的常用字符串操作,在此作為筆記記錄,下面這篇文章主要給大家介紹了C語(yǔ)言學(xué)習(xí)筆記之字符串間的那些事,需要的朋友可以參考下2022-04-04
vscode工程中c_cpp_properties.json文件作用詳細(xì)說明
c_cpp_properties.json是Visual Studio Code的一個(gè)配置文件,用于定義C/C++編譯器的路徑、默認(rèn)包含路徑和預(yù)處理器定義,這篇文章主要給大家介紹了關(guān)于vscode工程中c_cpp_properties.json文件作用詳細(xì)說明的相關(guān)資料,需要的朋友可以參考下2024-08-08
Objective-C限制函數(shù)調(diào)用的頻率詳解
這篇文章主要給大家介紹了關(guān)于Objective-C限制函數(shù)調(diào)用的頻率的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-12-12
這篇文章主要介紹了C++中move的使用及說明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的三子棋
這篇文章主要為大家詳細(xì)介紹了用C語(yǔ)言實(shí)現(xiàn)三子棋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06