程序员学数据结构

第6章　字典：关键字数据集

字典（dictionary）是一种抽象的数据结构，它是由一组关键字（键）与其相关联的值（值）构成的数据集，每个键只会在该数据集中出现一次。键与对应值互相关联，正是因为这种关系，字典有时会被称作关联数组（associative array）。字典也叫作映射（map），或更确切地说，有用于散列字典（哈希字典，hash table-based dictionary）的散列映射（哈希映射，hash map），以及用于查找树字典（search tree-based dictionary）的树映射（tree map）。字典中最常见的4种功能为增加、更新、获取和删除。其他常见的操作还有计数、重分配、置入和判断当前字典是否已存在指定键。以上每种操作都会在本章的后续内容中进行深入探究。

字典的关联特性或是映射特性支持非常高效的插入、查找和更新操作。在一个设计良好的字典中，对一个指定键的值进行新建、修改或获取操作时，其代价最低可为O(1)。正是出于这种高效性，字典或许是你在日常开发中能遇到的最常见的数据结构。

你也许会好奇，为什么会将键与值相关联的数据集称为字典。其实这个名称来源于实际意义上的字典，其中的每个词（键）都有一个与其相关联的定义（值）。如果这样的解释对你而言还有点抽象，那么就想象一下停车服务。当你停车参加一个活动时，服务人员会在你下车时递给你一张停车票，再把你的车开走停车。这张停车票代表且仅代表你的车。其他停车票都与你所持有的停车票不同。因此，只有出示这张唯一的停车票才能从停车服务处取回你的车。一旦出示了停车票，会有人开来你的车，给了小费就能开走了。

这个过程就是字典数据结构的一个具体示例。每张停车票都代表了一个键，而每辆车都代表某类型的一个值。每个键都是唯一的，并且唯一地标识一个特定的值。当代码调用了一个值，则数据集就像停车服务一样，使用键来定位和返回所查找的值。当然，用不用给开发机“小费”完全取决于你。 ...