深入解析Hashtable、Dictionary、SortedDictionary、SortedList

來源： | 時間：2013/6/11 0:56:52 |

在《在線用戶實體緩存解決方案》方案中使用Dictionary來存儲，評論里同事說SortedDictionary采用二分法查找比Dictionary快，于是我們都做了測試，最后發(fā)現Dictionary是比SortedDictionary快的，前者用的是Hash算法，而后者是RB-Tree算法。

于是想深入地分析如題的4個字典的原理。

我們先看Hashtable。

MSDN的解釋：表示鍵/值對的集合，這些鍵/值對根據鍵的哈希代碼進行組織。

Hash算法是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小于輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。

Hashtable 對象由包含集合元素的存儲桶組成。存儲桶是 Hashtable 中各元素的虛擬子組，與大多數集合中進行的搜索和檢索相比，存儲桶可令搜索和檢索更為便捷。每一存儲桶都與一個哈希代碼關聯(lián)，該哈希代碼是使用哈希函數生成的并基于該元素的鍵。

Hashtable 類默認的裝填因子是 1.0，但實際上它默認的裝填因子是 0.72。所有從構造函數輸入的裝填因子，Hashtable 類內部都會將其乘以0.72。這是一個要求苛刻的數字, 某些時刻將裝填因子增減 0.01, 可能你的 Hashtable 存取效率就提高或降低了 50%，其原因是裝填因子決定散列表容量，而散列表容量又影響 Key 的沖突幾率，進而影響性能。0.72 是 Microsoft經過大量實驗得出的一個比較平衡的值。

我們看Hashtable的一些源碼：

Hashtable .ctor

public Hashtable() : this(0, (float) 1f)
{
}
public Hashtable(int capacity, float loadFactor)
{
    if (capacity < 0)
    {
        throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    }
    if ((loadFactor < 0.1f) || (loadFactor > 1f))
    {
        throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", new object[] { 0.1, 1.0 }));
    }
    this.loadFactor = 0.72f × loadFactor;
    double num = ((float) capacity) / this.loadFactor;
    if (num > 2147483647.0)
    {
        throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
    }
    int num2 = (num > 11.0) ? HashHelpers.GetPrime((int) num) : 11;
    this

該文章由石家莊網站建設

TAG：高端網站建設高端網站設計網站制作網站建設

上一篇：C#中SortedDictionary 的使用

下一篇：C#中SortedList 和 SortedDictionary集合類型 .

返回列表

Graphics.FromImage 方法？

Graphics 類？

Image.FromFile 方法 (String)？

Asp.net(C#)給圖片加上水印效果？

Path.GetExtension 方法？

MSN、QQ、阿里旺旺在線客服源代碼？

服務項目