关联数组

维基百科,自由的百科全书
跳转至: 导航搜索

计算机科学中,关联数组英语:Associative Array),又称映射Map)、字典Dictionary)是一个抽象的数据结构,它包含着类似于(键,值)的有序对。一个关联数组中的有序对可以重复(如C++中的multimap)也可以不重复(如C++中的map)。

这种数据结构包含以下几种常见的操作:

  • 向关联数组添加配对
  • 从关联数组内删除配对
  • 修改关联数组内的配对
  • 根据已知的键寻找配对[1][2]

字典问题是设计一种能够具备关联数组特性的数据结构。解决字典问题的常用方法,是利用散列表,但有些情况下,也可以直接使用二叉查找树或其他结构。[1][2][3]

许多程序设计语言内置基本的数据类型,提供对关联数组的支持。而内容定址存储器则是硬件层面上实现对关联数组的支持。

各语言 / 库中的实现[编辑]

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 的多重集

C++/CLI 中另有 .net 所提供的托管实现,见下。

.Net Framework[编辑]

类 / 接口 说明
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>
按键排序的数组

参考[编辑]

  1. ^ 1.0 1.1 Goodrich, Michael T.; Tamassia, Roberto, 9.1 The Map Abstract Data Type, Data Structures & Algorithms in Java 4th, Wiley: 368–371, 2006 .
  2. ^ 2.0 2.1 Mehlhorn, Kurt; Sanders, Peter, 4 Hash Tables and Associative Arrays, Algorithms and Data Structures: The Basic Toolbox, Springer: 81–98, 2008 
  3. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford, 11 Hash Tables, Introduction to Algorithms 2nd, MIT Press and McGraw-Hill: 221–252, 2001, ISBN 0-262-03293-7  .

外部链接[编辑]