如何查找在.NET中工作的哈希表？

我試圖比較哈希表查找和線性搜索的性能。我創建了一個包含1000個項目的散列表，並發現在散列表中查找的時間爲0.0002（我使用DateTime.Now查找查找前後的系統時間並將其減去）。我在數組中有1000行，並使用線性搜索查找相同的值。事實證明，它比哈希表查找所花費的時間更少。如何查找在.NET中工作的哈希表？

我認爲哈希表比線性搜索更快。它是如何工作的？

謝謝

來源

2011-08-13 CuriousCoder

1000項目的value實在是太少了，哈希表的優勢顯示出來，當項目的數量較大。 – kd7

@ kd7：不，這根本不是問題。問題是他只做了一次查找，可能那個項目恰好在數組的前面。 – jason

在絕大多數機器上，您從DateTime.Now中獲得的最小增量爲0.0156秒。如果你殺死3只山羊並犧牲你的最年長者，那麼你可能得到0.0010。考慮到你測量了0.0002 *和*得到了反直覺結果，更大的可能性是你的測試顯然無效。簡單的假設，因爲你沒有給任何人一個機會來驗證它。 –

首先，您的時機機制不好。如果你想測試性能，你應該使用像System.Diagnostics.Stopwatch這樣的高分辨率定時器。其次，您需要找到的平均查找時間，這個查詢時間是隨機的，均勻分佈在查詢空間中的許多查詢，而不僅僅是查找某個特定項目的時間。

來源

2011-08-13 00:29:04 jason

這不回答這個問題，HashTable是如何工作的（在.Net中） – toddmo

答案可以在這篇文章中找到：

An Extensive Examination of Data Structures Using C# 2.0，

在所謂的「 的System.Collections.Hashtable類」一節

這裏是（非常）短簡介：

加入收藏（Add(object key, object value)）：

接收key和value參數
將散列算法應用於key參數。這是一個使用的Object.GetHashCode()方法，併產生在0和HASHSIZE（在哈希表時隙使用System.Collections.HashTable（內部查找結構）的數目之間的索引的位置的複雜的公式。
在插入的DictionaryEntry對象該位置

集合中訪問的項目（object this[object key] { set; get; }）：

接收key參數
使用key參數上的散列算法計算散列表中的位置。
返回存儲在該位置

來源

2013-10-15 22:50:12 toddmo

如何查找在.NET中工作的哈希表？

回答

相關問題