散列表又称哈希表，是线性表中一种重要的存储方式和检索方法。在这种结构中有一个散列函数 h，它以查找键（散列键）为参数并计算出一个介于 0 到 B-1 的整数，其中 B 是桶的数目。桶数组表示一个序号从 0 到 B-1 的数组，其中包含了 B 个数据集合，每个对应于数组中的一个桶。如果记录的查找键为 K，那么我们通过将该记录映射到 h(K) 的桶中来存储它。
在主存中，桶数组通常由指向链表头的指针组成，每个数据集合由链表构成。
在记录更多的辅存中，桶数组通常由一个或多个存储块组成，多个存储块可以通过存储附加信息来链接，或是将存储块顺序存放，通过存储块号取余来划分同一个桶中的多个存储块。以 B=4 为例，第 5 块存储块可以作为第 0 号桶的第 2 个存储块。
当一个查找键为 k 的新纪录需要被插入时，首先计算 h(k)。
-
如果桶号为 h(k) 的桶还有空间
-
把该记录存放在该桶的存储块中，如 h(k)=2。
-
存储在多个存储块中尚有空间的存储块中，如 h(k)=1。
-
-
如果该桶没有空间，那么就增加一个新的存储块并链接到该桶当前的最后一个存储块，然后将记录存入该块，比如 h(k)=3。
删除记录与插入记录的操作方式相同。当查找键为 c 的记录需要被删除时，首先找到桶号为 h(c) 的桶且从中搜索查找键为 c 的记录，继而将找到的记录删除。如果可以将记录在块中移动，那么删除记录后可以选择合并前后两个存储块。
由于记录的无序性，散列表无法支持范围查询，通常的做法是使用混合索引结构或多索引结构来额外支持范围查询。
此外，散列表在理想情况下是有足够的桶，绝大多数桶都只由单个块组成，这样一般查询只需要一次磁盘 I/O，且插入删除也只需两次磁盘 I/O。但如果记录数不断增长，最终就会出现一个桶由许多存储块构成的情况，导致我们需要在多个块中进行查找，每个块至少需要一次磁盘 I/O。
因此，我们必须设法减少每个桶的块数，比如通过减小哈希冲突，使用多个哈希函数的布谷哈希算法，来减少每个存储块的记录数，从而间接减少每个桶的块数。
但更有效的方法其实是减少无效访盘。我们都知道，为了查找一个键是否在块中，通常需要从磁盘读取该块，然后对其中的记录进行比较，而如果该块中不存在查找键，那么这次访盘就相当于一次无效的访盘。如果我们能够尽可能减少这样无效的访盘，那么桶的块数就不是大问题了。
关于这一点，目前常见的解决方案是引入布隆过滤器，这里简单介绍一下原理。布隆过滤器由一个固定大小的二进制向量或位图和多个映射函数组成。初始状态下，对于长度为 m 的位数组，它的所有位都为 0，当有元素加入集合时，通过 K 个映射函数将这个元素映射到位数组中的 k 个点，并把它们置为 1，这里以 3 个映射函数为例。
那么在查询某个元素时，我们只需要查看这些映射位是否都为 1 即可，如果任意一位为 0，被查询元素一定不存在，如果都为 1，则表示可能存在。将布隆过滤器应用在哈希桶的存储块中，则可以过滤元素不存在的存储块。但布隆过滤器是存在误判的，如果映射位都为 1，我们并不能准确判断是否存在，此时必须去读取存储块，这仍可能是一次无效的访盘。
前面介绍的散列表都为静态散列表，因为桶的数目 B 从不改变。但实际上散列表中还有一些动态散列表，它们允许桶的数目 B 改变，通过桶的数目增长同样能够间接减少每个桶的块数。
这里简单介绍一种动态散列表——可扩展散列表。它使用指向块的指针数组来表示桶，与主存的散列表类似。指针数组能够增长，其长度总是 2 的幂，数组每增长一次桶的数目就翻倍。在某些情况下多个桶可能共享一个存储块。散列函数 h 为每个键计算得到一个 K 位的二进制序列，桶的数目使用 2 的 i 次幂表示，其中 i 指从二进制序列第一位或最后一位算起的 i 位。
如下图所示假设 K=4，当前 i=1，因此桶数组只有两项，分别对应 0 或 1，其中第一个桶存储的是键被散列成以 0 开头的二进制序列的记录，第二个桶存储的是键被散列成以 1 开头的二进制序列的记录。可以注意到每个存储块都存储了一个数字，该数字表示由散列函数得到的二进制序列中有多少位用于确定记录在该块的成员资格。
当我们向其中插入一个散列值为 1010 序列的记录时，因为第一位是 1，所以该记录属于第二块，但该块已满，因此需要分裂，此时发现该块的数字 1 等于 i，因此我们需要将桶数组加倍，从而变成 i=2 的情况。
当我们再向其中分别插入散列值为 0000 和 0111 的记录，这两个记录都属于第一个存储块，于是该块会溢出，此时块内的数字 1 小于 i，因此我们不需要调整桶数组，只需要分裂该块，分别将记录调整到对应的存储块，并将桶数组中的 01 项指向新块。
最后我们再插入一个散列值为 1000 的记录，以相同的逻辑，散列表将扩展成如上图中所示的样子。
可扩展散列表有一个明显的好处是查找一个记录时总是只需要查找一个数据块，并且桶数组通常可以一直存留在主存。