4.3. 哈希表¶
前面介绍了线性表和线性表的两种存储结构。我们知道，无论是顺序表还是链表，它们都是按顺序依次存放所有元素，元素像一系列点一样排成一条线。表中有多少元素，就相应需要占用多少空间，即表的空间占用量和元素数量是成正比的。顺序表可以用位置下标来随机访问表中指定位置的元素，时间复杂度为 \(O(1)\)，但是增删元素的时间复杂度为 \(O(n)\)；链表在任意指定位置增删元素的时间复杂度都为 \(O(1)\)，但是如果要按下标位置来访问元素，则需要 \(O(n)\) 时间。
这一部分要介绍另一种神奇的数据结构，哈希表（Hash Table），也叫做散列表。元素要存放入哈希表，除了自身有一个元素值（value）以外，还需要有一个关键字（key），然后程序使用一个特定的哈希函数，把关键字映射成一个非负整数值，也就是该元素对应的哈希函数值，简称哈希值。这个哈希值就是该元素存放在表中的位置。
提示
事实上，大量情况下元素自身的值就可以直接用做其关键字，并不需要一个额外的关键字。
通过这种方式，哈希表可以实现常数时间的元素增删查改所有操作，因为它可以通过计算一遍哈希值来直接定位元素应在的位置。但是这个常数时间的实际运行速度是取决于哈希函数计算的复杂度的，属于相对比较重量级的常数时间。另外，哈希表的空间占用量和元素的实际数量是不成比例的。
哈希表是一种非常重要的基础数据结构，在大量的软件和算法领域有广泛应用。比如在信息安全领域，MD5、sha-1等经典的密钥算法都是基于哈希函数设计的。更重要的是，基于哈希表的原理，衍生出了两种非常重要的实用数据结构：集合和映射。如其名称所示，这两种数据结构与数学中的集合与映射这两个重要概念有非常密切的联系，也是大量实用软件和高级算法的基础数据结构。
在本部分我们除了介绍哈希表的原理、常见的哈希表实现方法以外，还会介绍STL的集合容器和映射容器。