从现有哈希表创建新哈希表

Question

假设我们有一个包含2^16键和值的哈希表。每个键可以表示为一个位字符串(例如，0000、0000、0000、0000)。现在我们要构造一个新的哈希表。新哈希表的键仍然是位字符串(例如0000、*)。当*取0或1时，相应的值将是旧哈希表中所有值的平均值。例如，0000、*是旧哈希表中从0000、0000、0000到0000、1111、1111、1111、1111之间的2^12值的平均值。直观地，我们需要做C(16，4) * 2^16次来构造新的哈希表。构造新哈希表的最有效方法是什么？

Answer 1

这里的哈希表根本帮不了你，尽管它也不是什么障碍。

哈希表本质上不能按键前缀进行群集键。为了提供良好的散列分布，需要在哈希值之间尽可能均匀地分配密钥。

如果以后需要按特定顺序处理密钥，则可以考虑有序关联映射，例如平衡二叉树或trie的某个变体。另一方面，需要展示按顺序处理密钥的优势，以便证明有序映射的额外开销是合理的。

在这种情况下，每个键都需要被访问，这意味着有序映射和散列映射都是O(n)，假设线性时间遍历和恒定时间处理都是合理的假设。但是，在处理每个结果值时，需要两个累积的中介体，基本上是一个正在运行的总计和一个计数。(有一种计算级数平均值的“在线”算法，但它也需要两个中间值，即运行均值和计数。因此，尽管它有优势，但减少存储需求并不是其中之一。)

您可以使用输出哈希表来存储每个输出值的中间值之一，但需要在某个地方放置另一个值。这可能是另一个相同大小的哈希表，或者类似的东西；在任何情况下，都会增加存储成本。

如果可以按前缀顺序遍历原始哈希表，则可以将此存储成本降为常数，因为每次到达新前缀时都可以回收这两个临时值。这是一种节省，但我怀疑它是否足以证明有序关联映射的开销是合理的，这也包括增加存储需求。