在计算机科学中，关联数组（），又称映射（）、字典（）是一个抽象的数据结构，它包含着类似于（键，值）的有序对。一个关联数组中的有序对可以重复（如C++中的multimap）也可以不重复（如C++中的map）。
这种数据结构包含以下几种常见的操作：
- 向关联数组添加配对
- 从关联数组内删除配对
- 修改关联数组内的配对
- 根据已知的键寻找配对
字典问题是设计一种能够具备关联数组特性的数据结构。解决字典问题的常用方法，是利用散列表或搜索树。有些情况下，也可以使用直接寻址的数组、二叉查找树或其他专门的结构。
关联数组有许多应用，包括诸如记忆化和修饰模式的编程模式。
许多程序设计语言内置基本的数据类型，提供对关联数组的支持。而则是硬件层面上实现对关联数组的支持。
操作
关联数组中，键与值的关联通常称作“映射”，“映射”一词也指创建新的关联的过程。
关联数组所定义的操作有：
示例
假设需要在一种数据结构中表示图书馆的借书情况。一本书一次只能借给一位读者，但一位读者同时可以借阅多本书。因此有关哪本书被哪位读者借出的信息可以用关联数组表示。这个数据结构用Python或JSON的记法可以表示如下：
{
"傲慢与偏见": "小红",
"呼啸山庄": "小红",
"远大前程": "小李"
}
对键“远大前程”的查询操作会返回“小李”。如果小李还了书，就需要一个删除操作。如果小陈外借了一本书，就需要一个插入操作，导致关联数组更新：
{
"傲慢与偏见": "小明",
"卡拉马佐夫兄弟": "小陈",
"呼啸山庄": "小红"
}
实现
对于非常小的关联数组来说，使用关联列表，即以映射为节点的链表实现较为合理。在这种实现下，进行基本操作的时间与映射的总数呈线性关系。但是这样的实现难度低、运行时间中的常数小，因此仍为较好的选择。
在键仅限于较窄范围时，还有另外一种简单的实现技巧。可以将键直接用于数组的寻址：比如键k对应的值就储存在数组元素A[k]，如果k还没有映射，那么在A[k]存储一个特殊的来表示。这种实现既简单又很快，每个操作只需要常数时间。其不足之处在于需要相当于整个键空间的储存空间，这意味着除非键空间很小，这种方法并不实用。
实现关联数组的主要方法是散列表和搜索树。单独链表法中，数组不是直接储存值本身，而是储存一个指向另一个容器的指针。这个容器常常是一个关联表，储存着对应同个散列值的所有值。而在开放定址法中如果出现散列冲突，散列表会在数组中决定性地找到一个空位，通常就是查看邻近的下一个位置。
当散列表大部分空着时，开放定址法比单独链表法有着更低的缓存不命中率。但是随着散列表被更多的元素填充，开放定址法的性能指数级地下降。此外，单独链表法使用的内存在多数情况下更少，除非值的大小非常小（小于四倍的指针大小）。
树实现
自平衡二叉搜索树
实现关联数组另一个常用的方法是使用自平衡二叉搜索树，例如AVL树或红黑树。
与使用散列表相比，使用树有其优点和不足。就最坏情况而言，自平衡二叉搜索树远好于散列表。使用自平衡二叉树的最坏情况的时间复杂度用大O表示法表示，为O(log n)。相比之下，使用散列表的最坏情况的时间复杂度则为O(n)。此外，和所有二叉搜索树一样，自平衡二叉搜索树中的元素始终按顺序排列。因此，对使用树实现的关联数组的遍历是按从小到大的顺序进行的，而遍历散列表则会呈现看似随机的序列。然而，散列表平均情况的时间复杂度（O(1)）比树要好得多，而且若散列函数选择恰当，最坏情况出现的概率很小。
值得注意的是，自平衡二叉搜索树也可以用来实现采用单独链表法的散列表的“桶”。这种实现保留了散列表的常数查询时间，且保证最坏情况也有O(log n)的表现。但是这种做法给实现增添了额外的复杂性且可能降低小型散列表的性能，因为在较小的散列表里，在树中插入元素并维护树的平衡所需的时间会长于直接对链表或类似数据结构中进行线性搜索所需的时间。
各语言 / 库中的支持
关联数组的内置语法上的支持是在1969年由SNOBOL4最早介入的，当时名字叫做“表格”。TMG提供带有字符串键和整数值的表格。MUMPS将多维关联数组作为它的关键数据结构，带有可选的持久性。SETL支持它们作为集合和映射的一种可能实现。
C++（标准模板库）
STL 提供了 8 个关联数组容器模板：
.Net Framework
C++/CLI 中另有 .Net 所提供的托管实现，见下。
参考
外部链接
*[http://www.nist.gov/dads/HTML/assocarray.html NIST's Dictionary of Algorithms and Data Structures: Associative Array]
评论 (0)