字典操作时间复杂度低的原因是什么？哈希表为何查询速度快

用储物柜的类比就能很容易理解：

• 假设你有100个按顺序编号的储物柜，编号从0到99
• 每次有人要存物品时，管理员会按照寄存人姓名的特征计算出一个100以内的数字，直接把物品放到对应编号的柜子里
• 等寄存人来取物品时，管理员不需要挨个打开所有柜子查找，只要再按姓名重新算一遍编号，直接打开对应柜子就能拿到物品，耗时几乎固定
• 上述计算存储位置的过程就是哈希计算，按这种逻辑组织的存储空间就是哈希表，C#的Dictionary<TKey,TValue>底层正是基于哈希表实现的，所以查询速度接近O(1)。

当然不存在真正的「免费午餐」，哈希表也有对应的取舍：

• 极端情况下会出现两个不同的姓名算出同一个编号的情况，也就是哈希冲突，通常的处理方式是在同一个位置挂链表存储多份数据，只要冲突概率足够低，几乎不会影响查询效率
• 为了降低冲突概率，哈希表需要预留一部分空置的存储空间，所以内存占用会比顺序存储的列表更高，属于典型的空间换时间的设计思路

向字典中添加的每一项都包含一个值及其关联的键。通过键检索值的速度非常快，时间复杂度接近O(1)，因为Dictionary<TKey,TValue>类是基于哈希表实现的。

内容的提问来源于stack exchange，提问作者Erik M