hashtable詳細介紹

作者: Leo Young 來源: 博客園發布時間: 2010-11-18 22:00 閱讀: 3158 次推薦: 0 原文鏈接 [收藏]

摘要：Hashtable是非泛型的集合，所以在檢索和存儲值類型時通常會發生裝箱與拆箱的操作。

　　Hashtable的定義

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

　　Hashtable存儲結構如下

　　Hashtable是非泛型的集合，所以在檢索和存儲值類型時通常會發生裝箱與拆箱的操作。

　　當把某個元素添加到 Hashtable 時，將根據鍵的哈希代碼將該元素放入存儲桶中，由于是散列算法所以會出現一個哈希函數能夠為兩個不同的鍵生成相同的哈希代碼，該鍵的后續查找將使用鍵的哈希代碼只在一個特定存儲桶中搜索，這將大大減少為查找一個元素所需的鍵比較的次數。

　　Hashtable 的加載因子確定元素與Hashtable 可擁有的元素數的最大比率。加載因子越小，平均查找速度越快，但消耗的內存也增加。默認的加載因子 0.72通常提供速度和大小之間的最佳平衡。當創建 Hashtable 時，也可以指定其他加載因子。

　　元素總量/ Hashtable 可擁有的元素數=加載因子

　　當向 Hashtable 添加元素時，Hashtable 的實際加載因子將增加。當實際加載因子達到指定的加載因子時，Hashtable 中存儲桶的數目自動增加到大于當前 Hashtable 存儲桶數兩倍的最小素數。

　　擴容時所有的數據需要重新進行散列計算。雖然Hash具有O(1)的數據檢索效率，但它空間開銷卻通常很大，是以空間換取時間。所以Hashtable適用于讀取操作頻繁，寫入操作很少的操作類型。

　　代碼一、

static void Main(string[] args)
{
Hashtable hashtb = new Hashtable();
hashtb.Add(1, "aa");
hashtb.Add(2, "bb");
hashtb.Add(3, "cc");
hashtb.Add(4, "dd");
foreach (DictionaryEntry item in hashtb)
{
Console.WriteLine(item.Value);
item.Value = "ee";
}
Console.Read();
}

　　編譯出錯：item為foreach的迭代變量，無法修改其成員。

　　原因：如果運行foreach處理語句試圖修改迭代變量值，或將變量值作為ref參數或out參數傳遞，那么都會發生編譯錯誤，迭代變量相當于一個局部只讀變量。

　　代碼二、

　　item.Value = "ee";改成hashtb[item.Key] = "ee";

　　運行報錯：集合已修改；可能無法執行枚舉操作。

　　原因：.NET Framework 提供枚舉數作為循環訪問一個集合的簡單方法。枚舉數只讀取集合中的數據，無法用于修改基礎集合。

　　foreach 語句用于循環訪問集合，以獲取您需要的信息，但不能用于在源集合中添加或移除項，否則可能產生不可預知的副作用。如果需要在源集合中添加或移除項，請使用 for 循環。

　　代碼三、

Thread tr1 = new Thread(new ThreadStart(() =>
{
foreach (DictionaryEntry item in hashtb)
{
Console.WriteLine(item.Value);
}
}));
tr1.Start();
Thread tr2 = new Thread(new ThreadStart(() =>
{
for (int i = 1; i < 4; i++)
{
hashtb[i] = "ee";
Console.WriteLine(hashtb[i]);
}
}));
tr2.Start();

　　線程tr1用來讀hashtable，線程tr2用來foreach來枚舉修改hashtable，

　　運行時錯誤：集合已修改；可能無法執行枚舉操作。

　　代碼四、

//讀取

Thread tr1 = new Thread(new ThreadStart(() =>
{
for (int i = 1; i <= 4; i++)
{
Console.WriteLine(hashtb[i]);
}
}));
tr1.Start();
Thread tr2 = new Thread(new ThreadStart(() =>
{
for (int i = 1; i <= 4; i++)
{
Console.WriteLine(hashtb[i]);
}
}));
tr2.Start();

//修改
Thread tr3 = new Thread(new ThreadStart(() =>
{
for (int i = 1; i <= 4; i++)
{
hashtb[i] = "ee";
}
}));
tr3.Start();

　　運行結果：正常

　　說明：Hashtable 是線程安全的，可由多個讀取器線程和一個寫入線程使用。多線程使用時，如果只有一個線程執行寫入（更新）操作，則它是線程安全的，從而允許進行無鎖定的讀取（若編寫器序列化為 Hashtable）

　　代碼五、

Thread tr1 = new Thread(new ThreadStart(() =>
{
lock (hashtb)
{
foreach (DictionaryEntry item in hashtb)
{
Console.WriteLine(item.Value);
}
}
}));

tr1.Start();
Thread tr2 = new Thread(new ThreadStart(() =>
{
lock (hashtb)
{
for (int i = 1; i <= 4; i++)
{
hashtb[i] = "ee";
}
}
}));
tr2.Start();

　　運行結果：正常

　　說明：由于兩個線程里面都加了lock (hashtb)所以是線程安全的。 從頭到尾對一個集合進行枚舉本質上并不是一個線程安全的過程。即使一個集合已進行同步，其他線程仍可以修改該集合，這將導致枚舉數引發異常。若要在枚舉過程中保證線程安全，可以在整個枚舉過程中鎖定集合，或者捕捉由于其他線程進行的更改而引發的異常。

　　Hashtable 提供的線程安全方法

　　Hashtable的Synchronized靜態方法提供線程安全的實例，如下：

　　Hashtable ht = Hashtable.Synchronized(new Hashtable());

　　內部實現如下：

public override void Add(object key, object value)
{
lock (this._table.SyncRoot)
{
　　this._table.Add(key, value);
}
}

　　按輸入方式輸出

　　因為hashtable內部是無序的，所以輸出不一定，hashtable取數據的機制沒搞明白。按照下面代碼可以實現先進先出。

可以通過控制ArrayList里面keys的排序來控制hashtable的輸出，當然也可以用SortedDictionary和SortedList實現排序集合。

public class NoSortHashtable : Hashtable
{
private ArrayList keys = new ArrayList();

public NoSortHashtable()
{
}

public override void Add(object key, object value)
{
base.Add (key, value);
keys.Add (key);
}

public override ICollection Keys
{
get
{
return keys;
}
}

public override void Clear()
{
base.Clear ();
keys.Clear ();
}

public override void Remove(object key)
{
base.Remove (key);
keys.Remove (key);
}
public override IDictionaryEnumerator GetEnumerator()
{
return base.GetEnumerator ();
}

}

標簽：hashtable