密鑰索引搜索存在表

Question

我對我的一本書的聲明有疑問。

說到鍵符號表中的鍵索引搜索，在某個點上它說：「如果沒有記錄（但只有鍵），我們可以使用一個位表，在這種情況下，符號表被稱爲存在表，因爲我們可以考慮第k位作爲k鍵是否存在於表中的指示符，例如，在32位計算機上使用313字表，我們可以使用這種方法可以快速確定給定的4位內部電話號碼是否已被分配「

嗯，我知道一個單詞是什麼，因此在這種情況下，存在表應該是10.016位表。但是這是什麼意思？ 4位數電話號碼的事實與它有什麼關係？那麼，當記錄對應於鍵時，如何使用鍵索引搜索實現符號表？

Answer 1

有9000四位數字（在基數10，十進制）和10000（非負）數字，最多四位數，所以一個超過10,000位的表就足以表明這些數字是否存在（位是否爲n？）。對於五位數字 - 其中90,000 - 你需要一個更大的表格。由於位表只能告訴你「是的，我們有它」或「不，我們沒有」，如果你需要任何超過這個數據的信息，你就不能使用它。但如果這就是你所需要知道的一切，那麼鍵到索引到表（數組）的任何映射映射都可以訪問這些信息，並且緊湊地存儲。在電話號碼的情況下，映射是微不足道的。

Answer 2

可以使用的10000個比特的bittable（對應於電話號碼的每個比特），其適合在313個字節（=32分之10000312.5〜= 313）