（點(diǎn)擊上方公號(hào)，可快速關(guān)注）

原文：Dennis Gao 的博客

鏈接：http://www.cnblogs.com/gaochundong/p/3813252.html

常用數(shù)據(jù)結(jié)構(gòu)的時(shí)間復(fù)雜度

如何選擇數(shù)據(jù)結(jié)構(gòu)

Array (T[])

• 當(dāng)元素的數(shù)量是固定的，并且需要使用下標(biāo)時(shí)。

Linked list (LinkedList)

• 當(dāng)元素需要能夠在列表的兩端添加時(shí)。否則使用 List。

Resizable array list (List)

• 當(dāng)元素的數(shù)量不是固定的，并且需要使用下標(biāo)時(shí)。

Stack (Stack)

• 當(dāng)需要實(shí)現(xiàn) LIFO（Last In First Out）時(shí)。

Queue (Queue)

• 當(dāng)需要實(shí)現(xiàn) FIFO（First In First Out）時(shí)。

Hash table (Dictionary)

• 當(dāng)需要使用鍵值對(duì)（Key-Value）來(lái)快速添加和查找，并且元素沒(méi)有特定的順序時(shí)。

Tree-based dictionary (SortedDictionary)

• 當(dāng)需要使用價(jià)值對(duì)（Key-Value）來(lái)快速添加和查找，并且元素根據(jù) Key 來(lái)排序時(shí)。

Hash table based set (HashSet)

• 當(dāng)需要保存一組唯一的值，并且元素沒(méi)有特定順序時(shí)。

Tree based set (SortedSet)

• 當(dāng)需要保存一組唯一的值，并且元素需要排序時(shí)。

Array

在計(jì)算機(jī)程序設(shè)計(jì)中，數(shù)組（Array）是最簡(jiǎn)單的而且應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)之一。在任何編程語(yǔ)言中，數(shù)組都有一些共性：

• 數(shù)組中的內(nèi)容是使用連續(xù)的內(nèi)存（Contiguous Memory）來(lái)存儲(chǔ)的。

• 數(shù)組中的所有元素必須是相同的類型，或者類型的衍生類型。因此數(shù)組又被認(rèn)為是同質(zhì)數(shù)據(jù)結(jié)構(gòu)（Homegeneous Data Structures）。

• 數(shù)組的元素可以直接被訪問(wèn)。比如你需要訪問(wèn)數(shù)組的第 i 個(gè)元素，則可以直接使用 arrayName[i] 來(lái)訪問(wèn)。

對(duì)于數(shù)組的常規(guī)操作包括：

• 分配空間（Allocation）

• 數(shù)據(jù)訪問(wèn)（Accessing）

在 C# 中，可以通過(guò)如下的方式聲明數(shù)組變量。

int allocationSize = 10;

bool[] booleanArray = new bool[allocationSize];

FileInfo[] fileInfoArray = new FileInfo[allocationSize];

上面的代碼將在 CLR 托管堆中分配一塊連續(xù)的內(nèi)存空間，用以容納數(shù)量為 allocationSize ，類型為 arrayType 的數(shù)組元素。如果 arrayType 為值類型，則將會(huì)有 allocationSize 個(gè)未封箱（unboxed）的 arrayType 值被創(chuàng)建。如果 arrayType 為引用類型，則將會(huì)有 allocationSize 個(gè) arrayType 類型的引用被創(chuàng)建。

如果我們?yōu)?FileInfo[] 數(shù)組中的一些位置賦上值，則引用關(guān)系為下圖所示。

.NET 中的數(shù)組都支持對(duì)元素的直接讀寫操作。語(yǔ)法如下：

// 讀數(shù)組元素

bool b = booleanArray[7];

// 寫數(shù)組元素

booleanArray[0] = false;

訪問(wèn)一個(gè)數(shù)組元素的時(shí)間復(fù)雜度為 O(1)，因此對(duì)數(shù)組的訪問(wèn)時(shí)間是恒定的。也就是說(shuō)，與數(shù)組中包含的元素?cái)?shù)量沒(méi)有直接關(guān)系，訪問(wèn)一個(gè)元素的時(shí)間是相同的。

ArrayList

由于數(shù)組是固定長(zhǎng)度的，并且數(shù)組中只能存儲(chǔ)同一種類型或類型的衍生類型。這在使用中會(huì)受到一些限制。.NET 提供了一種數(shù)據(jù)結(jié)構(gòu) ArrayList 來(lái)解決這些問(wèn)題。

ArrayList countDown = new ArrayList();

countDown.Add(3);

countDown.Add(2);

countDown.Add(1);

countDown.Add('blast off!');

countDown.Add(new ArrayList());

ArrayList 是長(zhǎng)度可變的數(shù)組，并且它可以存儲(chǔ)不同類型的元素。

但這些靈活性是以犧牲性能為代價(jià)的。在上面 Array 的描述中，我們知道 Array 在存儲(chǔ)值類型時(shí)是采用未裝箱（unboxed）的方式。由于 ArrayList 的 Add 方法接受 object 類型的參數(shù)，導(dǎo)致如果添加值類型的值會(huì)發(fā)生裝箱（boxing）操作。這在頻繁讀寫 ArrayList 時(shí)會(huì)產(chǎn)生額外的開(kāi)銷，導(dǎo)致性能下降。

List

當(dāng) .NET 中引入泛型功能后，上面 ArrayList 所帶來(lái)的性能代價(jià)可以使用泛型來(lái)消除。.NET 提供了新的數(shù)組類型 List。

泛型允許開(kāi)發(fā)人員在創(chuàng)建數(shù)據(jù)結(jié)構(gòu)時(shí)推遲數(shù)據(jù)類型的選擇，直到使用時(shí)才確定選擇哪種類型。泛型（Generics）的主要優(yōu)點(diǎn)包括：

• 類型安全（Type Safety）：使用泛型定義的類型，在使用時(shí)僅能使用指定的類型或類型的衍生類型。

• 性能（Performance）：泛型移除了運(yùn)行時(shí)類型檢測(cè)，消除了裝箱和拆箱的開(kāi)銷。

• 可重用（Reusability）：泛型打破了數(shù)據(jù)結(jié)構(gòu)與存儲(chǔ)數(shù)據(jù)類型之間的緊耦合。這提高了數(shù)據(jù)結(jié)構(gòu)的可重用性。

List 等同于同質(zhì)的一維數(shù)組（Homogeneous self-redimensioning array）。它像 Array 一樣可以快速的讀取元素，還可以保持長(zhǎng)度可變的靈活性。

// 創(chuàng)建 int 類型列表

List myFavoriteIntegers = new List();

// 創(chuàng)建 string 類型列表

List friendsNames = new List();

List 內(nèi)部同樣使用 Array 來(lái)實(shí)現(xiàn)，但它隱藏了這些實(shí)現(xiàn)的復(fù)雜性。當(dāng)創(chuàng)建 List 時(shí)無(wú)需指定初始長(zhǎng)度，當(dāng)添加元素到 List 中時(shí)，也無(wú)需關(guān)心數(shù)組大小的調(diào)整（resize）問(wèn)題。

List powersOf2 = new List();

powersOf2.Add(1);

powersOf2.Add(2);

powersOf2[1] = 10;

int sum = powersOf2[1] + powersOf2[2];

List 的漸進(jìn)運(yùn)行時(shí)（Asymptotic Running Time）復(fù)雜度與 Array 是相同的。

LinkedList

在鏈表（Linked List）中，每一個(gè)元素都指向下一個(gè)元素，以此來(lái)形成了一個(gè)鏈（chain）。

向鏈表中插入一個(gè)新的節(jié)點(diǎn)的漸進(jìn)時(shí)間取決于鏈表是否是有序的。如果鏈表不需要保持順序，則插入操作就是常量時(shí)間O(1)，可以在鏈表的頭部或尾部添加新的節(jié)點(diǎn)。而如果需要保持鏈表的順序結(jié)構(gòu)，則需要查找到新節(jié)點(diǎn)被插入的位置，這使得需要從鏈表的頭部 head 開(kāi)始逐個(gè)遍歷，結(jié)果就是操作變成了O(n)。下圖展示了插入節(jié)點(diǎn)的示例。

鏈表與數(shù)組的不同之處在于，數(shù)組的中的內(nèi)容在內(nèi)存中時(shí)連續(xù)排列的，可以通過(guò)下標(biāo)來(lái)訪問(wèn)，而鏈表中內(nèi)容的順序則是由各對(duì)象的指針?biāo)鶝Q定，這就決定了其內(nèi)容的排列不一定是連續(xù)的，所以不能通過(guò)下標(biāo)來(lái)訪問(wèn)。如果需要更快速的查找操作，使用數(shù)組可能是更好的選擇。

使用鏈表的最主要的優(yōu)勢(shì)就是，向鏈表中插入或刪除節(jié)點(diǎn)無(wú)需調(diào)整結(jié)構(gòu)的容量。而相反，對(duì)于數(shù)組來(lái)說(shuō)容量始終是固定的，如果需要存放更多的數(shù)據(jù)，則需要調(diào)整數(shù)組的容量，這就會(huì)發(fā)生新建數(shù)組、數(shù)據(jù)拷貝等一系列復(fù)雜且影響效率的操作。即使是 List 類，雖然其隱藏了容量調(diào)整的復(fù)雜性，但仍然難逃性能損耗的懲罰。

鏈表的另一個(gè)優(yōu)點(diǎn)就是特別適合以排序的順序動(dòng)態(tài)的添加新元素。如果要在數(shù)組的中間的某個(gè)位置添加新元素，不僅要移動(dòng)所有其余的元素，甚至還有可能需要重新調(diào)整容量。

所以總結(jié)來(lái)說(shuō)，數(shù)組適合數(shù)據(jù)的數(shù)量是有上限的情況，而鏈表適合元素?cái)?shù)量不固定的情況。

在 .NET 中已經(jīng)內(nèi)置了 LinkedList 類，該類實(shí)現(xiàn)了雙向鏈表（doubly-linked list）功能，也就是節(jié)點(diǎn)同時(shí)持有其左右節(jié)點(diǎn)的引用。而對(duì)于刪除操作，如果使用 Remove(T)，則運(yùn)算復(fù)雜度為 O(n)，其中 n 為鏈表的長(zhǎng)度。而如果使用 Remove(LinkedListNode)， 則運(yùn)算復(fù)雜度為 O(1)。

Queue

當(dāng)我們需要使用先進(jìn)先出順序（FIFO）的數(shù)據(jù)結(jié)構(gòu)時(shí)，.NET 為我們提供了 Queue。Queue 類提供了 Enqueue 和 Dequeue 方法來(lái)實(shí)現(xiàn)對(duì) Queue 的存取。

Queue 內(nèi)部建立了一個(gè)存放 T 對(duì)象的環(huán)形數(shù)組，并通過(guò) head 和 tail 變量來(lái)指向該數(shù)組的頭和尾。

默認(rèn)情況下，Queue 的初始化容量是 32，也可以通過(guò)構(gòu)造函數(shù)指定容量。

Enqueue 方法會(huì)判斷 Queue 中是否有足夠容量存放新元素。如果有，則直接添加元素，并使索引 tail 遞增。在這里的 tail 使用求模操作以保證 tail 不會(huì)超過(guò)數(shù)組長(zhǎng)度。如果容量不夠，則 Queue 根據(jù)特定的增長(zhǎng)因子擴(kuò)充數(shù)組容量。

默認(rèn)情況下，增長(zhǎng)因子（growth factor）的值為 2.0，所以內(nèi)部數(shù)組的長(zhǎng)度會(huì)增加一倍。也可以通過(guò)構(gòu)造函數(shù)中指定增長(zhǎng)因子。Queue 的容量也可以通過(guò) TrimExcess 方法來(lái)減少。

Dequeue 方法根據(jù) head 索引返回當(dāng)前元素，之后將 head 索引指向 null，再遞增 head 的值。

Stack

當(dāng)需要使用后進(jìn)先出順序（LIFO）的數(shù)據(jù)結(jié)構(gòu)時(shí)，.NET 為我們提供了 Stack。Stack 類提供了 Push 和 Pop 方法來(lái)實(shí)現(xiàn)對(duì) Stack 的存取。

Stack 中存儲(chǔ)的元素可以通過(guò)一個(gè)垂直的集合來(lái)形象的表示。當(dāng)新的元素壓入棧中（Push）時(shí)，新元素被放到所有其他元素的頂端。當(dāng)需要彈出棧（Pop）時(shí)，元素則被從頂端移除。

Stack 的默認(rèn)容量是 10。和 Queue 類似，Stack 的初始容量也可以在構(gòu)造函數(shù)中指定。Stack 的容量可以根據(jù)實(shí)際的使用自動(dòng)的擴(kuò)展，并且可以通過(guò) TrimExcess 方法來(lái)減少容量。

如果 Stack 中元素的數(shù)量 Count 小于其容量，則 Push 操作的復(fù)雜度為 O(1)。如果容量需要被擴(kuò)展，則 Push 操作的復(fù)雜度變?yōu)?O(n)。Pop 操作的復(fù)雜度始終為 O(1)。

Hashtable

現(xiàn)在我們要使用員工的社保號(hào)作為唯一標(biāo)識(shí)進(jìn)行存儲(chǔ)。社保號(hào)的格式為 DDD-DD-DDDD（D 的范圍為數(shù)字 0-9）。

如果使用 Array 存儲(chǔ)員工信息，要查詢社保號(hào)為 111-22-3333 的員工，則將會(huì)嘗試遍歷數(shù)組的所有選擇，即執(zhí)行復(fù)雜度為 O(n) 的查詢操作。好一些的辦法是將社保號(hào)排序，以使查詢復(fù)雜度降低到 O(log(n))。但理想情況下，我們更希望查詢復(fù)雜度為 O(1)。

一種方案是建立一個(gè)大數(shù)組，范圍從 000-00-0000 到 999-99-9999 。

這種方案的缺點(diǎn)是浪費(fèi)空間。如果我們僅需要存儲(chǔ) 1000 個(gè)員工的信息，那么僅利用了 0.0001% 的空間。

第二種方案就是用哈希函數(shù)（Hash Function）壓縮序列。

我們選擇使用社保號(hào)的后四位作為索引，以減少區(qū)間的跨度。這樣范圍將從 0000 到 9999。

在數(shù)學(xué)上，將這種從 9 位數(shù)轉(zhuǎn)換為 4 位數(shù)的方式稱為哈希轉(zhuǎn)換（Hashing）?？梢詫⒁粋€(gè)數(shù)組的索引空間（indexers space）壓縮至相應(yīng)的哈希表（Hash Table）。

在上面的例子中，哈希函數(shù)的輸入為 9 位數(shù)的社保號(hào)，輸出結(jié)果為后 4 位。

H(x) = last four digits of x

上圖中也說(shuō)明在哈希函數(shù)計(jì)算中常見(jiàn)的一種行為：哈希沖突（Hash Collisions）。即有可能兩個(gè)社保號(hào)的后 4 位均為 0000。

當(dāng)要添加新元素到 Hashtable 中時(shí)，哈希沖突是導(dǎo)致操作被破壞的一個(gè)因素。如果沒(méi)有沖突發(fā)生，則元素被成功插入。如果發(fā)生了沖突，則需要判斷沖突的原因。因此，哈希沖突提高了操作的代價(jià)，Hashtable 的設(shè)計(jì)目標(biāo)就是要盡可能減低沖突的發(fā)生。

避免哈希沖突的一個(gè)方法就是選擇合適的哈希函數(shù)。哈希函數(shù)中的沖突發(fā)生的幾率與數(shù)據(jù)的分布有關(guān)。例如，如果社保號(hào)的后 4 位是隨即分布的，則使用后 4 位數(shù)字比較合適。但如果后 4 位是以員工的出生年份來(lái)分配的，則顯然出生年份不是均勻分布的，則選擇后 4 位會(huì)造成大量的沖突。

我們將選擇合適的哈希函數(shù)的方法稱為沖突避免機(jī)制（Collision Avoidance）。

在處理沖突時(shí)，有很多策略可以實(shí)施，這些策略稱為沖突解決機(jī)制（Collision Resolution）。其中一種方法就是將要插入的元素放到另外一個(gè)塊空間中，因?yàn)橄嗤墓Ｎ恢靡呀?jīng)被占用。

例如，最簡(jiǎn)單的一種實(shí)現(xiàn)就是線性挖掘（Linear Probing），步驟如下：

1. 當(dāng)插入新的元素時(shí)，使用哈希函數(shù)在哈希表中定位元素位置；

2. 檢查哈希表中該位置是否已經(jīng)存在元素。如果該位置內(nèi)容為空，則插入并返回，否則轉(zhuǎn)向步驟 3。

3. 如果該位置為 i，則檢查 i+1 是否為空，如果已被占用，則檢查 i+2，依此類推，直到找到一個(gè)內(nèi)容為空的位置。

現(xiàn)在如果我們要將五個(gè)員工的信息插入到哈希表中：

• Alice (333-33-1234)

• Bob (444-44-1234)

• Cal (555-55-1237)

• Danny (000-00-1235)

• Edward (111-00-1235)

則插入后的哈希表可能如下：

元素的插入過(guò)程：

• Alice 的社保號(hào)被哈希為 1234，因此存放在位置 1234。

• Bob 的社保號(hào)被哈希為 1234，但由于位置 1234 處已經(jīng)存放 Alice 的信息，則檢查下一個(gè)位置 1235，1235 為空，則 Bob 的信息就被放到 1235。

• Cal 的社保號(hào)被哈希為 1237，1237 位置為空，所以 Cal 就放到 1237 處。

• Danny 的社保號(hào)被哈希為 1235，1235 已被占用，則檢查 1236 位置是否為空，1236 為空，所以 Danny 就被放到 1236。

• Edward 的社保號(hào)被哈希為 1235，1235 已被占用，檢查1236，也被占用，再檢查1237，直到檢查到 1238時(shí)，該位置為空，于是 Edward 被放到了1238 位置。

線性挖掘（Linear Probing）方式雖然簡(jiǎn)單，但并不是解決沖突的最好的策略，因?yàn)樗鼤?huì)導(dǎo)致同類哈希的聚集。這導(dǎo)致搜索哈希表時(shí)，沖突依然存在。例如上面例子中的哈希表，如果我們要訪問(wèn) Edward 的信息，因?yàn)?Edward 的社保號(hào) 111-00-1235 哈希為 1235，然而我們?cè)?1235 位置找到的是 Bob，所以再搜索 1236，找到的卻是 Danny，以此類推直到找到 Edward。

一種改進(jìn)的方式為二次挖掘（Quadratic Probing），即每次檢查位置空間的步長(zhǎng)為平方倍數(shù)。也就是說(shuō)，如果位置 s 被占用，則首先檢查 s + 12 處，然后檢查s – 12，s + 22，s – 22，s + 32 依此類推，而不是象線性挖掘那樣以 s + 1，s + 2 … 方式增長(zhǎng)。盡管如此，二次挖掘同樣也會(huì)導(dǎo)致同類哈希聚集問(wèn)題。

.NET 中的 Hashtable 的實(shí)現(xiàn)，要求添加元素時(shí)不僅要提供元素（Item），還要為該元素提供一個(gè)鍵（Key）。例如，Key 為員工社保號(hào)，Item 為員工信息對(duì)象。可以通過(guò) Key 作為索引來(lái)查找 Item。

Hashtable employees = new Hashtable();

// Add some values to the Hashtable, indexed by a string key

employees.Add('111-22-3333', 'Scott');

employees.Add('222-33-4444', 'Sam');

employees.Add('333-44-55555', 'Jisun');

// Access a particular key

if (employees.ContainsKey('111-22-3333'))

{

string empName = (string)employees['111-22-3333'];

Console.WriteLine('Employee 111-22-3333's name is: ' + empName);

}

else

Console.WriteLine('Employee 111-22-3333 is not in the hash table...');

Hashtable 類中的哈希函數(shù)比前面介紹的社保號(hào)的實(shí)現(xiàn)要更為復(fù)雜。哈希函數(shù)必須返回一個(gè)序數(shù)（Ordinal Value）。對(duì)于社保號(hào)的例子，通過(guò)截取后四位就可以實(shí)現(xiàn)。但實(shí)際上 Hashtable 類可以接受任意類型的值作為 Key，這都要?dú)w功于 GetHashCode 方法，一個(gè)定義在 System.Object 中的方法。GetHashCode 的默認(rèn)實(shí)現(xiàn)將返回一個(gè)唯一的整數(shù)，并且保證在對(duì)象的生命周期內(nèi)保持不變。

Hashtable 類中的哈希函數(shù)定義如下：

H(key) = [GetHash(key) + 1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))] % hashsize

這里的 GetHash(key) 默認(rèn)是調(diào)用 key 的 GetHashCode 方法以獲取返回的哈希值。hashsize 指的是哈希表的長(zhǎng)度。因?yàn)橐M(jìn)行求模，所以最后的結(jié)果 H(key) 的范圍在 0 至 hashsize – 1 之間。

當(dāng)在哈希表中添加或獲取一個(gè)元素時(shí)，會(huì)發(fā)生哈希沖突。前面我們簡(jiǎn)單地介紹了兩種沖突解決策略：

• 線性挖掘（Linear Probing）

• 二次挖掘（Quadratic Probing）

在 Hashtable 類中則使用的是一種完全不同的技術(shù)，稱為二度哈希（rehashing）（有些資料中也將其稱為雙精度哈希（double hashing））。

二度哈希的工作原理如下：

有一個(gè)包含一組哈希函數(shù) H1…Hn 的集合。當(dāng)需要從哈希表中添加或獲取元素時(shí)，首先使用哈希函數(shù) H1。如果導(dǎo)致沖突，則嘗試使用 H2，以此類推，直到 Hn。所有的哈希函數(shù)都與 H1 十分相似，不同的是它們選用的乘法因子（multiplicative factor）。

通常，哈希函數(shù) Hk 的定義如下：

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

當(dāng)使用二度哈希時(shí)，重要的是在執(zhí)行了 hashsize 次挖掘后，哈希表中的每一個(gè)位置都有且只有一次被訪問(wèn)到。也就是說(shuō)，對(duì)于給定的 key，對(duì)哈希表中的同一位置不會(huì)同時(shí)使用 Hi 和 Hj。在 Hashtable 類中使用二度哈希公式，其始終保持 (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)) 與 hashsize 互為素?cái)?shù)（兩數(shù)互為素?cái)?shù)表示兩者沒(méi)有共同的質(zhì)因子）。

二度哈希較前面介紹的線性挖掘（Linear Probing）和二次挖掘（Quadratic Probing）提供了更好的避免沖突的策略。

Hashtable 類中包含一個(gè)私有成員變量 loadFactor，loadFactor 指定了哈希表中元素?cái)?shù)量與位置（slot）數(shù)量之間的最大比例。例如：如果 loadFactor 等于 0.5，則說(shuō)明哈希表中只有一半的空間存放了元素值，其余一半都為空。

哈希表的構(gòu)造函數(shù)允許用戶指定 loadFactor 值，定義范圍為 0.1 到 1.0。然而，不管你提供的值是多少，范圍都不會(huì)超過(guò) 72%。即使你傳遞的值為 1.0，Hashtable 類的 loadFactor 值還是 0.72。微軟認(rèn)為loadFactor 的最佳值為 0.72，這平衡了速度與空間。因此雖然默認(rèn)的 loadFactor 為 1.0，但系統(tǒng)內(nèi)部卻自動(dòng)地將其改變?yōu)?0.72。所以，建議你使用缺省值1.0（但實(shí)際上是 0.72）。

// Add some employees

employeeData.Add(455110189) = new Employee('Scott Mitchell');

employeeData.Add(455110191) = new Employee('Jisun Lee');

// See if employee with SSN 123-45-6789 works here

if (employeeData.ContainsKey(123456789))

向 Hashtable 中添加新元素時(shí)，需要檢查以保證元素與空間大小的比例不會(huì)超過(guò)最大比例。如果超過(guò)了，哈希表空間將被擴(kuò)充。步驟如下：

• 哈希表的位置空間幾乎被翻倍。準(zhǔn)確地說(shuō)，位置空間值從當(dāng)前的素?cái)?shù)值增加到下一個(gè)最大的素?cái)?shù)值。

• 因?yàn)槎裙r(shí)，哈希表中的所有元素值將依賴于哈希表的位置空間值，所以表中所有值也需要重新二度哈希。

由此看出，對(duì)哈希表的擴(kuò)充將是以性能損耗為代價(jià)。因此，我們應(yīng)該預(yù)先估計(jì)哈希表中最有可能容納的元素?cái)?shù)量，在初始化哈希表時(shí)給予合適的值進(jìn)行構(gòu)造，以避免不必要的擴(kuò)充。

Dictionary

Hashtable 類是一個(gè)類型松耦合的數(shù)據(jù)結(jié)構(gòu)，開(kāi)發(fā)人員可以指定任意的類型作為 Key 或 Item。當(dāng) .NET 引入泛型支持后，類型安全的 Dictionary 類出現(xiàn)。Dictionary 使用強(qiáng)類型來(lái)限制 Key 和 Item，當(dāng)創(chuàng)建 Dictionary 實(shí)例時(shí)，必須指定 Key 和 Item 的類型。

Dictionary variableName = new Dictionary();

如果繼續(xù)使用上面描述的社保號(hào)和員工的示例，我們可以創(chuàng)建一個(gè) Dictionary 的實(shí)例：

Dictionaryint, Employee> employeeData = new Dictionaryint, Employee>();

這樣我們就可以添加和刪除員工信息了。

Dictionary 與 Hashtable 的不同之處還不止一處。除了支持強(qiáng)類型外，Dictionary 還采用了不同的沖突解決策略（Collision Resolution Strategy），這種新的技術(shù)稱為鏈技術(shù)（chaining）。

前面使用的挖掘技術(shù)（probing），如果發(fā)生沖突，則將嘗試列表中的下一個(gè)位置。如果使用二度哈希（rehashing），則將導(dǎo)致所有的哈希被重新計(jì)算。而新的鏈技術(shù)（chaining）將采用額外的數(shù)據(jù)結(jié)構(gòu)來(lái)處理沖突。Dictionary 中的每個(gè)位置（slot）都映射到了一個(gè)數(shù)組。當(dāng)沖突發(fā)生時(shí)，沖突的元素將被添加到桶（bucket）列表中。

下面的示意圖中描述了 Dictionary 中的每個(gè)桶（bucket）都包含了一個(gè)鏈表以存儲(chǔ)相同哈希的元素。

上圖中，該 Dictionary 包含了 8 個(gè)桶，也就是自頂向下的黃色背景的位置。一定數(shù)量的 Employee 對(duì)象已經(jīng)被添加至 Dictionary 中。如果一個(gè)新的 Employee 要被添加至 Dictionary 中，將會(huì)被添加至其 Key 的哈希所對(duì)應(yīng)的桶中。如果在相同位置已經(jīng)有一個(gè) Employee 存在了，則將會(huì)將新元素添加到列表的前面。

向 Dictionary 中添加元素的操作涉及到哈希計(jì)算和鏈表操作，但其仍為常量，復(fù)雜度為 O(1)。

對(duì) Dictionary 進(jìn)行查詢和刪除操作時(shí)，其平均時(shí)間取決于 Dictionary 中元素的數(shù)量和桶（bucket）的數(shù)量。具體的說(shuō)就是運(yùn)行時(shí)間為 O(n/m)，這里 n 為元素的總數(shù)量，m 是桶的數(shù)量。但 Dictionary 幾乎總是被實(shí)現(xiàn)為 n = m，也就是說(shuō)，元素的總數(shù)絕不會(huì)超過(guò)桶的總數(shù)。所以 O(n/m) 也變成了常量 O(1)。

參考資料

• An Extensive Examination of Data Structures Using C# 2.0 : Part 1: An Introduction to Data Structures

• An Extensive Examination of Data Structures Using C# 2.0 : Part 2: The Queue, Stack, and Hashtable

• 考察數(shù)據(jù)結(jié)構(gòu)——第一部分：數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介[譯]

• 考察數(shù)據(jù)結(jié)構(gòu)——第二部分：隊(duì)列、堆棧和哈希表[譯]

我的桌面非常無(wú)聊，因?yàn)樗褪怯蓭讉€(gè)xterm窗口組成，窗口里運(yùn)行的是我正在使用的Unix系統(tǒng)。這臺(tái)機(jī)器本身很可能是在在運(yùn)行X Window Server，而不是Windows，因?yàn)檫@么多年來(lái)，我只用x terminal。