假设我们有一个包含2^16个键和值的哈希表。每个密钥可以表示为一个比特串(例如，0000、0000、0000和0000(。现在我们想要构建一个新的哈希表。新哈希表的密钥仍然是一个比特串(例如0000、***、***、****(。当*取0或1时，对应的值将是旧哈希表中所有值的平均值。例如，0000、***、***、****的值将是旧哈希表中从0000、0000、0000到0000、1111、1111的2^12个值的平均值。直观地说，我们需要做C(16，4(*2^16次来构建新的哈希表。构造新哈希表最有效的方法是什么？
这里的哈希表对您没有任何帮助，尽管它也没有太大的阻碍。
从本质上讲，哈希表不能通过密钥前缀对密钥进行聚类。为了提供良好的哈希分布，密钥需要在哈希值之间尽可能均匀地分布。
如果以后需要按特定顺序处理键，可以考虑有序的关联映射，例如平衡二叉树或trie的某些变体。另一方面，为了证明有序映射的额外开销，需要证明按顺序处理密钥的优势。
在这种情况下，每个密钥都需要访问，这意味着有序映射和哈希映射都将是O(n(，假设线性时间遍历和恒定时间处理，这两个假设都是合理的。然而，在处理过程中，每个结果值都需要两个累积的中介，基本上是一个运行总数和一个计数。(有一种"在线"计算级数平均值的算法，但它也需要两个中间值，运行平均值和计数。因此，尽管它有优势，但减少存储需求并不是其中之一。(
您可以使用输出哈希表为每个输出值存储一个中间值，但您需要将另一个放在某个地方。这可能是另一个大小相同或类似的哈希表；在任何情况下，都会有额外的存储成本
如果可以按前缀顺序遍历原始哈希表，则可以将此存储成本降低为常量，因为每次到达新前缀时都可以回收这两个临时值。因此，这是一个节省，但我怀疑这是否足以证明有序关联映射的开销是合理的，其中还包括增加的存储需求。