關聯陣列

在電腦科學中，關聯陣列（英語：Associative Array），又稱對映（Map）、字典（Dictionary）是一個抽象的資料結構，它包含著類似於（鍵，值）的有序對。一個關聯陣列中的有序對可以重複（如C++中的multimap）也可以不重複（如C++中的map）。

這種資料結構包含以下幾種常見的操作：

• 向關聯陣列添加配對
• 從關聯陣列內刪除配對
• 修改關聯陣列內的配對
• 根據已知的鍵尋找配對^[1][2]

字典問題是設計一種能夠具備關聯陣列特性的資料結構。解決字典問題的常用方法，是利用雜湊表或搜尋樹^[1][2][3][4]。有些情況下，也可以使用直接定址的陣列、二元搜尋樹或其他專門的結構。

關聯陣列有許多應用，包括諸如記憶化和修飾模式的編程模式。^[5]

許多程式設計語言內建基本的資料類型，提供對關聯陣列的支援。而內容定址記憶體（英語：Content-addressable memory）則是硬體層面上實現對關聯陣列的支援。

操作

關聯陣列中，鍵與值的關聯通常稱作「對映」，「對映」一詞也指新增的關聯的過程。

關聯陣列所定義的操作有：^[1][2]

• 添加或插入：添加一個新的鍵值對，建立從新鍵到新值的對映。該操作的參數是要添加的鍵和值。
• 重新賦值：更改一已有的鍵值對的值，把原有的鍵對映到新的值。和插入一樣，參數為鍵和值。
• 刪除：移除一個鍵值對，取消從該鍵到該值的對映。參數為要刪除的鍵。
• 查詢：尋找到給出鍵對應的值（如果該鍵存在）。這個操作的參數是要尋找的鍵，返回的是對應的值。如果沒有相應的鍵值對，有些實現會引發異常，而另外一些則會使用所給的鍵建立並添加新的鍵值對，其中的「值」為其類型的預設值（零、空容器等）

添加和重新賦值的操作常作為一個賦值的操作出現，即如果存在鍵值對則更新它，反之添加。

關聯陣列也可能包括其他操作，比如查詢已有的對映數目和構造迭代器以遍歷所有對映。遍歷的順序通常由關聯陣列的實現決定。

多重關連陣列是關聯陣列的推廣，它允許多個值與一個鍵關聯。^[6]

範例

假設需要在一種資料結構中表示圖書館的借書情況。一本書一次只能借給一位讀者，但一位讀者同時可以借閱多本書。因此有關哪本書被哪位讀者借出的資訊可以用關聯陣列表示。這個資料結構用Python或JSON的記法可以表示如下：

{
    "傲慢与偏见": "小红",
    "呼啸山庄": "小红",
    "远大前程": "小李"
}

對鍵「遠大前程」的查詢操作會返回「小李」。如果小李還了書，就需要一個刪除操作。如果小陳外借了一本書，就需要一個插入操作，導致關聯陣列更新：

{
    "傲慢与偏见": "小明",
    "卡拉马佐夫兄弟": "小陈",
    "呼啸山庄": "小红"
}

實現

對於非常小的關聯陣列來說，使用關聯列表，即以對映為節點的鏈結串列實現較為合理。在這種實現下，進行基本操作的時間與對映的總數呈線性關係。但是這樣的實現難度低、執行時間中的常數小，因此仍為較好的選擇。^[1][7]

在鍵僅限於較窄範圍時，還有另外一種簡單的實現技巧。可以將鍵直接用於陣列的定址：比如鍵k對應的值就儲存在陣列元素A[k]，如果k還沒有對映，那麼在A[k]儲存一個特殊的哨兵值（英語：Sentinel value）來表示。這種實現既簡單又很快，每個操作只需要常數時間。其不足之處在於需要相當於整個鍵空間的儲存空間，這意味著除非鍵空間很小，這種方法並不實用。

實現關聯陣列的主要方法是雜湊表和搜尋樹。^[1][2][3][4]

雜湊表實現

主條目：雜湊表

這張圖比較了使用鏈結串列法和線性探測在大型雜湊表（遠大於快取容量）中查詢元素分別所需要的CPU快取不命中次數。線性探測的表現更好，是因為它有更好的訪問局部性，儘管在雜湊表快填滿時其效能急劇下降。

關聯陣列最常用的通用實現是使用雜湊表——陣列和雜湊函式的結合。該雜湊函式把每個鍵分散到各自的「桶」中。雜湊表背後的基本原理是：用下標訪問陣列是一個簡單的常數時間的操作。因此對雜湊表的操作所需的平均開銷只包括計算雜湊值，和在陣列中訪問對應的「桶」。正因如此，使用雜湊表的時間複雜度通常為O(1)，大多數情況下優於其他方法。

雜湊表需要能處理衝突——雜湊函式把兩個不同的鍵對映到同一個「桶」的情況。解決這個問題的兩個最普遍的方法是單獨鏈結串列法和開放定址法。^[1][2][3][8]單獨鏈結串列法中，陣列不是直接儲存值本身，而是儲存一個指向另一個容器的指標。這個容器常常是一個關聯表，儲存著對應同個雜湊值的所有值。而在開放定址法中如果出現雜湊衝突，雜湊表會在陣列中決定性地找到一個空位，通常就是檢視鄰近的下一個位置。

當雜湊表大部分空著時，開放定址法比單獨鏈結串列法有著更低的快取不命中率。但是隨著雜湊表被更多的元素填充，開放定址法的效能指數級地下降。此外，單獨鏈結串列法使用的主記憶體在多數情況下更少，除非值的大小非常小（小於四倍的指標大小）。

樹實現

主條目：搜尋樹

自平衡二元搜尋樹

實現關聯陣列另一個常用的方法是使用自平衡二元搜尋樹，例如AVL樹或紅黑樹。^[9]

與使用雜湊表相比，使用樹有其優點和不足。就最壞情況而言，自平衡二元搜尋樹遠好於雜湊表。使用自平衡二元樹的最壞情況的時間複雜度用大O表示法表示，為O(log n)。相比之下，使用雜湊表的最壞情況的時間複雜度則為O(n)。此外，和所有二元搜尋樹一樣，自平衡二元搜尋樹中的元素始終按順序排列。因此，對使用樹實現的關聯陣列的遍歷是按從小到大的順序進行的，而遍歷雜湊表則會呈現看似隨機的序列。然而，雜湊表平均情況的時間複雜度（O(1)）比樹要好得多，而且若雜湊函式選擇恰當，最壞情況出現的概率很小。

值得注意的是，自平衡二元搜尋樹也可以用來實現採用單獨鏈結串列法的雜湊表的「桶」。這種實現保留了雜湊表的常數查詢時間，且保證最壞情況也有O(log n)的表現。但是這種做法給實現增添了額外的複雜性且可能降低小型雜湊表的效能，因為在較小的雜湊表裡，在樹中插入元素並維護樹的平衡所需的時間會長於直接對鏈結串列或類似資料結構中進行線性搜尋所需的時間。^[10][11]

各語言 / 庫中的支援

關聯陣列的內建語法上的支援是在1969年由SNOBOL4最早介入的，當時名字叫做「表格」。TMG提供帶有字串鍵和整數值的表格。MUMPS將多維關聯陣列作為它的關鍵資料結構，帶有可選的永續性。SETL支援它們作為集合和對映的一種可能實現。

C++（標準模板庫）

STL 提供了 8 個關聯陣列容器模板：

類別模板	說明
std::map<K, V> std::unordered_map<K, V>	從 K 到 V 類型的一對一字典 不帶 unordered_ 字首的為根據 K 排序的紅黑樹、帶字首的為雜湊表（即不排序，故名）
std::multimap<K, V> std::unordered_multimap<K, V>	從 K 到 V 的一對多字典
std::set<T> std::unordered_set<T>	T 的集合
std::multiset<T> std::unordered_multiset<T>	T 的多重集

.Net Framework

C++/CLI 中另有 .Net 所提供的代管實現，見下。

類 / 介面	說明
System.Collections.IDictionary System.Collections.Generic.IDictionary<K, V>	字典的介面 System.Collections 命名空間中為非泛型版本，即其內容類型為 System.Object 類型
System.Collections.HastTable System.Collections.Generic.Dictionary<K, V>	雜湊表實現的字典
System.Collections.Generic.SortedDictionary<K, V>	二元搜尋樹
System.Collections.SortedList System.Collections.Generic.SortedList<K, V>	按鍵排序的陣列