哈希表大小取決於密鑰的長度？

-2

散列表大小取決於負載因子。
它必須是最大素數，並使用該素數作爲哈希函數的模值。
素數不能太接近2的冪和10

懷疑我有權力，

是否哈希表的大小取決於密鑰長度？

本書後面的段落由Cormen介紹算法。是否n = 2000字符串的平均長度或將存儲在散列表中的元素的數量？

對米佳值是素數不是太接近2確切權力對於例如，假設我們要分配一個哈希表，由鏈解決衝突，持有大約N = 2000字符串，其中一個字符有8位。我們不介意在不成功的搜索檢查3個元素的平均值，所以我們分配的大小爲m = 701號701的哈希表的選擇，因爲它是一個素近= 2000/3但不靠近任何2.功率處理每個密鑰k爲整數，我們散列函數將是

H（K）= K MOD 701。

有人可以解釋它>

來源

2016-07-25 sunil sarode

你是指「大小」是什麼意思？桶的數量？平均。每個桶的元素數量？平均。鏈長？ RAM中與表相關的「全部」使用的字節數？ – AnoE

長度的鑰匙 –

我不明白你。我問道：「你的意思是'大小'」，顯然就你的問題「是否......」而你回答「密鑰的長度」......沒有計算。 – AnoE

下面是用哈希表的權衡的概述。假設您有一個散列表，其中有m個存儲區，存儲鏈總共存儲着n個對象。

如果存儲對象中的引用，所消耗的總內存爲O (m + n)。

現在，假設對於一個普通對象，其大小爲s，需要O (s)時間來計算其散列一次，而O (s)來比較兩個這樣的對象。考慮檢查散列表中是否存在對象的操作。該存儲桶平均有n/m個元素，所以該操作將花費O (s n/m)時間。

所以，權衡是這樣的：當你增加桶數m時，增加內存消耗，但減少單個操作的平均時間。

對於原來的問題 - 是否哈希表的大小取決於密鑰長度？ - 不，它不應該，至少不是直接。

您引用的段落僅提及字符串作爲存儲在散列表中的對象的示例。提到的一個屬性是它們是8位字符串。另一個是「我們不介意在不成功的搜索中檢查3個元素的平均值」。然後，將存儲對象的屬性包裝爲表單：我們想要放置在單個存儲桶中的平均數量是多少？字符串本身的長度在任何地方都沒有提及。

來源

2016-07-25 12:27:31 Gassa

所以如果對於n = 10^5如果我做10^5/3將散列表的大小平均爲單個桶中的3個元素 –

@sunilsarode確實如此。每個元素都必須進入一個桶。當有10^5個元素但是10^5/3個桶時，平均每桶三個元素。 – Gassa

非常感謝您的回答。 –

（2）和（3）爲假。只要您使用正確的散列函數，通常使用帶有2^n存儲桶（ref）的散列表。在（1）上，哈希表所佔用的內存等於桶的數量乘以密鑰的長度。請注意，對於字符串鍵，我們通常保留指向字符串的指針，而不是字符串本身，因此鍵的長度是指針的長度，在64位機器上是8個字節。

來源

2016-07-25 12:10:47 user172818

可以請你解釋一下嗎？n = 2000表示將存儲在散列表中的元素的平均數量？ –

您的報價很混亂。我不確定這意味着什麼。 – user172818

算法明智，不！這裏關鍵字的長度是無關緊要的。另外，密鑰本身並不重要，重要的是你預測你將擁有的不同密鑰的數量。

執行方面，是的！由於您必須將密鑰本身保存在散列表中，因此它會反映其大小。

關於第二個問題，「N」是指持有不同鑰匙的數量。

來源

2016-07-25 12:12:34

所以散列表的大小= 701，它將有n = 2000個不同密鑰的鏈接形式 –

哈希表大小取決於密鑰的長度？

回答

相關問題