字典是便于信息检索的一种数据结构，鉴于信息检索在程序中无处不在，字典的使用场景也非常广泛，包括许多 python 内部机制的实现，也依赖字典结构，比如命名空间的管理等。
检索一般是根据关键字查找与它关联的信息，这些关键字应该是固定的，否则就会使原来保存的数据失效，也就是说，关键字必须是不可变对象。当然，在具体实现上，我们知道，python 是根据是否存在 __hash__ 方法来判断一个对象是否可以作为关键字的，用户可以自行实现这个方法，但也承担相应的风险。
对于信息检索来说，效率往往是关键考虑因素。如果是一个静态字典，主要考虑的是创建和查找的效率问题，而对于更常用的动态字典来说，在其中插入和删除数据的效率也很重要。
下面，我们从使用者的角度看一下字典所需要支持的操作，然后简单讨论字典的实现技术。当然，它需要支持的操作决定了它应该采用的实现技术。
从使用者的角度，我可以梳理一下字典需要支持的操作。
python 字典提供了多种创建方式：
在处理遍历时，python 提供了一个字典视图对象，这种对象提供的是一个动态视图。也就是说，如果字典的内容发生了变化，视图也会随之变化：
显然，我们可以用列表来保存字典的键和关联的数据对象。
使用普通线性表时，数据检索的效率是 O(n) ，因为必须一一比对，直到找到键值，或者确定表中不存在该键值。如果我们改进结构，采用有序表，那么，通过二分法，可以以 O(logn) 的效率找到数据，是比较快的。不过，数据并不一定都可以排序，在实践中，甚至需要使用不同类型的对象作为字典的键，这时使用有序表就会遇到一些障碍。
而对数据插入和删除来说，基于线性表实现的字典在效率上是不能让人满意的。如果采用普通线性表，添加数据的时间复杂度是 O(1)，删除数据则为 O(n)；如果采用有序表，则插入和删除数据都是 O(n) 的时间复杂度。
线性表的另一个问题是需要连续的存储空间，对于规模较大的字典来说，也会造成一些困难。
总的来说，对于频繁变动，需要支持众多类型的键，或者规模较大的字典来说，线性表可能不是最好的选择。
树形结构是检索系统的常用数据结构。它不需要连续的存储空间，可以支持大规模的数据，如果设计科学，也可以实现高效的检索和修改。
理论上说，普通二叉树可以实现平均意义上的 O(logn) 检索效率和修改效率。但这种效率是没有保证的，如果没有及时控制和调整，普通二叉树很有可能在持续的数据变动过程中发生结构退化，某个分支无限延伸，导致检索和操作效率往 O(n) 靠近。
解决结构退化问题的思路，是在数据变动过程中，不断调整其结构，使其保持相对平衡。因此，在实践中可以采用平衡二叉树，或者红黑树，从而实现稳定的 O(logn) 的检索和操作效率。
如我们所知，除了二叉树，实践中也常常使用多分支排序树，或者说 N叉树。考虑到从磁盘读取数据时，其实是按块读取的，在一个节点上存储更多数据有利于减少磁盘读写操作，因此，多分支排序树在数据库系统中得到很好的应用。比如 MySQL 的 InNoDB 引擎，采用 B+ 树作为索引结构，如果以整数字段作为索引，每个节点大约可以有 1200 个分支。
当然，python 中的字典和集合采用的并不是基于树形结构的实现，而是基于哈希表的实现，在理想情况下，可以实现 O(1) 复杂度的检索和修改。
哈希表也叫散列表，本质上是一个线性表。线性表一定有一个下标区间，比如说一个可以存放 8 个元素的列表，其下标区间就是 0-7，如果我们可以设计一种函数，把字典的键映射为这个区间内的一个整数，就可以直接根据键计算得到它存储的具体位置，因而就可以实现快速访问和修改了，这个函数就是散列函数，或者哈希函数。
散列函数的设计有很多专业的研究，总的来说，它需要实现的基本性质包括：
容易发现，采用散列表技术实现字典，会有两个绕不过去的问题：
对于第一个问题，python 字典采用的空间扩展策略和列表的空间扩展策略类似。当我们创建一个空字典或者很小的字典时，初始分配的存储区可以容纳 8 个元素，当存储区的使用超过 2/3 时，字典会更换更大的存储区，并把之前保存的内容重新散列到新存储里。当元素个数低于 50000 个时，新扩展的存储区是原存储区的 4 倍，超过之后则调整为 2 倍。
为什么元素个数超过 2/3 就进行扩展呢？这个问题涉及到散列表的冲突处理技术。简单地说，由于 python 采用的是内部消解技术，为保持散列表的平均检索速度接近常数，需要控制其负载因子，也就是元素占空间可存储元素数量的比重低于 0.7 到 0.75。
哈希表一定会有哈希值冲突问题。比如说，一个可以存放 8 个元素的表，不同键计算得到的哈希值都是 5，这时该怎么处理呢？
一种解决方案是使用外部空间，叫外部消解技术。比如说，对于所有出现冲突的键值，可以统一放到外部的某个列表，检索的时候，如果发现地址为 5 的空间存储的不是需要的键，就到外部列表查找，如果外部列表也没有找到，就判定这个键不存在。或者说，我们在哈希表中不直接保存对象(或者对象的引用)，而保存一个列表的引用，所有哈希值为 5 的对象(或其引用)都保存在这个列表里等。具体实现可以采用多种不同的策略。
另一种解决方案是内部消解技术，也就是说，如果出现冲突，后进来的值依然会保存在内部空间，只是存储的位置做了调整。具体的调整策略可以多种多样，比如说，直接使用下一个空地址，或者再次进行散列操作等。这样，检索键值的时候，如果原有位置存储着其它键，就按规则继续检索，直到找到，或者遇到一个未使用的空间，从而判断该键不存在。
python 字典采用的是内消解技术。
不论如何，哈希值冲突都是我们希望尽量避免的，最坏情况下，所有键值都冲突，哈希表就会退化为一个线性表，数据检索复杂度会从 O(1) 上升为 O(n)。
事实上，由于哈希表必然出现冲突，因此在安全领域，有哈希碰撞攻击的思路。通过精心构造的、哈希值一致的数据，对同一个 API 发起请求，导致服务器 CPU 都消耗在数据检索上，无法快速响应请求，从而实现 DOS 的目的。
在 python 中，除了内置的字典，collections 模块还提供了另外两种常用的字典： defautdict 和 OrderDict。
defaultdict 实际上只是扩展了字典的 __missing__ 方法，支持用户提供一个 default_factory 函数，用于默认值的生成。当我们从字典取值时，如果字典没有对应的键，就会调用 __missing__ 方法，如果未定义这个方法，则直接返回 KeyError 。值得注意的是，__missing__ 方法不会被 __getitem__ 以外的方法调用，也就是说，如果我们使用 get() 函数取值，依然会返回指定的默认值或 None。
和常规字典相比，OrderDict 对象内部维护着一个根据键插入顺序排序的双向链表，新插入的元素会被放到链表的尾部，从而实现记住插入顺序的功能。不过，python3.7 版本之后，内置字典已经实现了一样的能力，并在 python3.8 版本提供了 __reversed__() 方法，因此，OrderDict 已经没什么存在的必要了。
进一步了解可以参考官方文档。
python 提供了两种内置集合类型：set 和 frozenset。它们的实现技术与字典是一致的，当然，frozenset 是不可变对象，其实现不需要考虑空间扩展的问题。
fronzenset 与 set 的关系有点类似于 tuple 与 list 的关系，形式上分为不可变和可变，底层技术基本一致，在实践中却往往用于完全不同的场景。
和字典不一样的地方在于，集合需要考虑数学中的集合类计算，如交集、并集、差集与对称差集等等。如果有兴趣，也可以直接查看官方文档。