java – 一种节省空间的数据结构,用于存储和查找大量(均匀分布的

虽然Jon Skeet的回答为小额投资带来了可观的节省,但我认为你可以做得更好.由于您的数字分布相当均匀,您可以使用插值搜索来获得更快的查找(大致为O(log log N)而不是O(log N)).对于一百万个项目,您可以计划大约4个比较而不是大约20个.

如果你想做更多的工作来将内存(大致)再次削减一半,你可以将它构建为一个两级查找表,基本上是一种简单版本的trie.

你可以将你的(大概)32位整数分成两个16位的整数.您将前16位用作查找表第一级的索引.在这个级别,你有65536个指针,每个可能的16位值对应整数的那一部分.那会把你带到桌子的第二层.对于这一部分,我们在所选指针和下一个指针之间进行二进制或插值搜索 – 即第二级中所有在前16位中具有相同值的值.

但是,当我们查看第二个表时,我们已经知道了16位的值 – 所以我们只需要存储该值的其他16位,而不是存储该值的所有32位.

这意味着代替占用4兆字节的第二级,我们已将其减少到2兆字节.除此之外,我们需要第一级表,但它只有65536×4 = 256K字节.

这几乎肯定会提高整个数据集的二进制搜索的速度.在最坏的情况下(使用二级搜索进行第二级),我们可以进行多达17次比较(1 log2 65536).平均值会比那更好 – 因为我们只有一百万个项目,每个二级“分区”中平均只能有1_000_000/65536 = ~15个项目,大约1 log2(16)= 5比较.在第二级使用插值搜索可能会进一步减少,但是当你只进行5次比较时,你没有太多空间可以进行真正的改进.鉴于二级平均只有约15项,您使用的搜索类型不会有太大差异 – 即使线性搜索也会非常快.

当然,如果你想要,你可以更进一步,而是使用一个4级表(整数中每个字节一个).然而,这可能是一个值得怀疑的问题,这是否会为你节省更多的钱来帮助你.至少马上关闭,我的直接猜测是你要做相当少的额外工作以获得相当小的节省(只存储百万个整数的最后字节显然占用1兆字节,并且三个级别的表将导致占用相当多的数量,所以你可以将节省数量增加一倍,以节省半个兆字节的费用.如果你处于一个可以节省更多一点的情况会有很大的不同,那就去吧 – 但是,除此之外,我怀疑这种回报是否能证明额外的投资是合理的.