hash - 为具有低空间复杂度的固定已知值集创建哈希表

Question

我试图更好地理解低级优化，我目前正在研究哈希表/集。正如标题所暗示的那样，我正在尝试找到一种方法来节省尽可能多的空间，同时仍然保持摊销的 O(1) 时间来在表中查找值。假设我知道表中将包含哪些键以及其中有多少个（键是固定的，不会添加新键）。

关于散列本身的一些想法：

我读了一点关于最小完美散列的内容，通过它我想到我应该只散列我给出的值的一些位/字节（例如一些前缀/后缀）以降低条目的数量从而降低了表所需的指针数量（会有更多的冲突，但如果我发现大量的哈希位可能可以忽略不计）。即使这是个好主意，我也不确定如何选择这个数量。

假设我选择使用大小为 X 的前缀。关于上述问题，我的一个想法是计算键前缀的分布，如果分布接近均匀 - X 是前缀的好大小，否则我应该寻找一个不同大小的前缀（选择 X 给我最接近均匀但仍然小于某个大小的分布）。

但是再一次，假设分布总是一致的：什么大小的前缀是理想的？

我的问题有条不紊：

1. 一般来说 - 我如何才能节省空间，同时仍然保持摊销的 O(1) 时间来选择哈希表中的项目？
2. 具体来说 - 我的想法是只使用一些前缀的哈希来获得更多的冲突，但降低通常需要的表大小好吗？
3. 有没有办法以更紧凑（空间明智）的方式保存数据？即 - 如果键是字符串，则仅使用它们的一些字符表示它们或将多个字符分组以获得唯一的数字值并改用它。如果键是数字，那么可能将多个键存储在同一个 64 位整数中，前半部分表示第一个数字，后半部分表示另一个？

任何想法和方向，阅读材料，以便我可以自己思考或直接回答我的问题，将不胜感激！

标签： hashhashtablespace-complexitycomputation-theory