關聯數組

在計算機科學中，關聯數組（英語：Associative Array），又稱映射（Map）、字典（Dictionary）是一個抽象的數據結構，它包含着類似於（鍵，值）的有序對。一個關聯數組中的有序對可以重複（如C++中的multimap）也可以不重複（如C++中的map）。

這種數據結構包含以下幾種常見的操作：

• 向關聯數組添加配對
• 從關聯數組內刪除配對
• 修改關聯數組內的配對
• 根據已知的鍵尋找配對

字典問題是設計一種能夠具備關聯數組特性的數據結構。解決字典問題的常用方法，是利用散列表或搜索樹。有些情況下，也可以使用直接尋址的數組、二叉查找樹或其他專門的結構。

關聯數組有許多應用，包括諸如記憶化和修飾模式的編程模式。

許多程序設計語言內置基本的數據類型，提供對關聯數組的支持。而內容定址存儲器則是硬件層面上實現對關聯數組的支持。

操作

關聯數組中，鍵與值的關聯通常稱作「映射」，「映射」一詞也指創建新的關聯的過程。

關聯數組所定義的操作有：

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

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

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

多重關連數組是關聯數組的推廣，它允許多個值與一個鍵關聯。

示例

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

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

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

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

實現

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

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

實現關聯數組的主要方法是散列表和搜索樹。

散列表實現

主條目：散列表

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

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

散列表需要能處理衝突——散列函數把兩個不同的鍵映射到同一個「桶」的情況。解決這個問題的兩個最普遍的方法是單獨鍊表法和開放定址法。單獨鍊表法中，數組不是直接儲存值本身，而是儲存一個指向另一個容器的指針。這個容器常常是一個關聯表，儲存着對應同個散列值的所有值。而在開放定址法中如果出現散列衝突，散列表會在數組中決定性地找到一個空位，通常就是查看鄰近的下一個位置。

當散列表大部分空着時，開放定址法比單獨鍊表法有着更低的緩存不命中率。但是隨着散列表被更多的元素填充，開放定址法的性能指數級地下降。此外，單獨鍊表法使用的內存在多數情況下更少，除非值的大小非常小（小於四倍的指針大小）。

樹實現

主條目：搜索樹

自平衡二叉搜索樹

實現關聯數組另一個常用的方法是使用自平衡二叉搜索樹，例如AVL樹或紅黑樹。

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

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

各語言 / 庫中的支持

關聯數組的內置語法上的支持是在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>	按鍵排序的數組

外部連結

• NIST's Dictionary of Algorithms and Data Structures: Associative Array （頁面存檔備份，存於網際網路檔案館）