c - 存在表中的键索引搜索

Question

我对我书中的一个陈述有疑问。

谈到符号表中的键索引搜索，在某一点上它说:“如果没有记录(但只有键)，我们可以使用位表。在这种情况下，符号表之所以称为存在表，是因为我们可以把第k位看成表中有无第k个键的标志。例如，在32位计算机上使用一个313字的表，我们可以使用此方法快速确定给定的 4 位内部电话号码是否已分配。"

好吧，我知道单词是什么，因此在这种情况下，存在表应该是 10.016 位表。但是这是什么意思？ 4 位电话号码的事实与它有什么关系？那么，当记录对应于键时，如何实现带有键索引搜索的符号表？

Answer 1

有 9000 个四位数(以 10 为基数，十进制)和 10000 个(非负)最多四位数的数字，因此具有超过 10,000 位的表足以指示这些数字中的每一个是否存在(位 no n 是否设置？)。对于 90,000 个五位数数字，您需要更大的表格。

由于位表只能告诉您“是的，我们有”或“不，我们没有”，如果您需要任何超出此范围的信息，则不能使用它。但是，如果这就是您需要知道的全部内容，那么键到表(数组)中索引的任何单射映射都可以让您访问该信息，并紧凑地存储。对于电话号码，映射很简单。