我对我书中的一个陈述有疑问。
谈到符号表中的键索引搜索，在某个点上它说：“如果没有记录（但只有键），我们可以使用位表。在这种情况下，符号表称为存在表，因为我们可以将第 k 位作为表中是否存在 k 键的指标。例如，在 32 位计算机上使用 313 字表，我们可以使用这种方法快速确定是否已分配给定的 4 位内部电话号码。 "
好吧，我知道单词是什么，因此在这种情况下，存在表应该是一个 10.016 位的表。但是这是什么意思？4位电话号码的事实与它有什么关系？那么，当记录对应于键时，如何实现具有键索引搜索的符号表？
您可以使用 10000 位的位表（每个位对应一个电话号码），适合 313 个字节（10000/32 = 312.5 ~= 313）
有 9000 个四位数字（以 10 为底，十进制）和 10000 个（非负）数字，最多有四位数字，所以一个超过 10,000 位的表足以表明每个数字是否存在（是位没有n设置吗？）。对于五位数字（其中 90,000 个），您需要一个更大的表格。
由于位表只能告诉您“是的，我们有”或“不，我们没有”，因此如果您需要任何超出此范围的信息，则无法使用它。但是，如果这就是您需要知道的全部内容，那么任何将键映射到表（数组）中的索引都可以让您访问该信息，并紧凑地存储。在电话号码的情况下，映射是微不足道的。