我有一张很大的 table ：
id1 id2 count
1 234 4
1 5 123
1 432 5
23 234 7
id1和id2有许多不同的值 . count具有有限的数值（1-30000或其他），我知道它们中的大多数等于1 .
当我将它存储在.net字典中时，此表占用大约10GB的内存 . 我想找到内存高效的数据结构来存储这些数据 .
完美哈希可能是理想的解决方案，但问题是冲突 . 我可以得到表中没有的id的值 . 也许DAWG可以提供帮助？或者是其他东西？
数据结构的主要目的是通过id1和id2进行计数 .
2 回答
如果几乎所有的计数都是1，那么你可以使用两个数据结构：一个包含所有id对的计数为1的HashSet，以及一个计数大于1的id-pair的Dictionary . 这使得递增和检查计数有点慢，但它应该节省一些空间 . （我不知道.Net数据结构是如何在内部布局的，所以我不敢猜测，但如果它是C，我会说它会减少25-30％的空间消耗，具体取决于值“几乎所有” . ）
如果没有足够的空间节省，这里有一些可能性的概述，尽管可能需要做很多不确定的工作：
通常，容器数据结构的成本由元素数据的大小加上一些每元素开销加上一些每数据结构开销组成 . 散列表具有中等量的每元素开销（一个指向存储桶中下一个元素的链接，加上分配/对齐开销）;和二进制树有很多每元素开销（两个或多个通常是三个链接，加上分配/对齐开销） . 向量技术上没有每个元素的开销，但它们通常被分配以减少插入时间，因此您应该将它们视为每个元素的开销为50-100％ .
一个结果是，如果你想出一种减少元素数量的方法，你通常可以节省空间 . 例如，您可以使用id-pairs的HashSet，如上所述 . 但是如果个别id1值比成对少得多 - 即，如果id重复 - 那么你可以用字典映射id1替换为id2的向量，这可能会减少开销 . 这有一个很大的缺点：它使查找和插入更加昂贵;此外，它只有在散列表每元素开销超过预期的向量分配开销时才有用 .
你在id1和id2上有一个相当小的上限吗？如果是这样，那么您可以将它们存储为单个数字;例如，如果你在两个数字上都有255的上限，那么你可以将它们存储为id = id1 id2 * 256;如果需要，你可以提取id1 = id％256和id2 = id / 256（使用整数除法）
既然每个id对都有一个索引，并且因为大多数计数都是1，你可以将它存储为sparse array（通常稀疏数组的"empty"值为0或null，在你的情况下它们是1）
如果没有将两个ID组合成单个索引的好方法，那么您可以将其存储为sparse matrix，其中id1为x值，id2为y值（反之亦然）