关联数组
在计算机科学中，关联数组（英語：），又称映射（）、字典（）是一个抽象的数据结构，它包含着类似于（键，值）的有序对。一个关联数组中的有序对可以重复（如C++中的multimap）也可以不重复（如C++中的map）。
这种数据结构包含以下几种常见的操作：
字典问题是设计一种能够具备关联数组特性的数据结构。解决字典问题的常用方法，是利用散列表，但有些情况下，也可以直接使用二叉查找树或其他结构。[1][2][3]
许多程序设计语言内置基本的数据类型，提供对关联数组的支持。而内容定址存储器则是硬件层面上实现对关联数组的支持。
各语言 / 库中的实现
关联数组的内置语法上的支持是在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> | 按键排序的数组 |
参考
- Goodrich, Michael T.; Tamassia, Roberto, , 4th, Wiley: 368–371, 2006.
- Mehlhorn, Kurt; Sanders, Peter, , , Springer: 81–98, 2008
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, , 2nd, MIT Press and McGraw-Hill: 221–252, 2001, ISBN 0-262-03293-7 .
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.