我們先看Hashtable。
MSDN的解釋:表示鍵/值對的集合,這些鍵/值對根據鍵的哈希代碼進行組織。
Hash算法是把任意長度的輸入(又叫做預映射, pre-image),通過散列算法,變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小於輸入的空間,不 同的輸入可能會散列成相同的輸出,而不可能從散列值來唯一的確定輸入值。
Hashtable 對象由包含集合元素的存儲桶組成。存儲桶是 Hashtable 中各元素的虛擬子組,與大多數集合中進行的搜索和檢索相比,存儲桶 可令搜索和檢索更為便捷。每一存儲桶都與一個哈希代碼關聯,該哈希代碼是使用哈希函數生成的並基於該元素的鍵。
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.buckets = new bucket[num2];
this.loadsize = (