替换.net字典

Question

给定(简化说明)

我们的一项服务在内存中有很多实例.大约85%是独一无二的.我们需要对这些项目进行非常快速的基于密钥的访问,因为它们在单个堆栈/调用中经常被查询.这个单一的上下文非常优化性能.

所以我们开始将它们放入字典中.表现还可以.

在这种情况下,尽可能快地访问项目是最重要的.确保在读取发生时没有写入操作.

问题

与此同时,我们达到了字典可以存储的项目数量的限制.

Die Arraydimensionen haben den unterstützten Bereich überschritten. 
  bei System.Collections.Generic.Dictionary`2.Resize(Int32 newSize, Boolean forceNewHashCodes)
  bei System.Collections.Generic.Dictionary`2.Insert(TKey key, TValue value, Boolean add)

这转化为The array dimensions have exceeded the supported range.

像Memcached这样的解决方案在这个特定情况下太慢了.它是一个封装在单个服务中的独立的非常具体的用例

因此,我们正在寻找替代此特定方案的字典.

目前我找不到一个支持这个.我错过了什么吗？有人能指出我吗？

作为替代方案,如果不存在,我们正在考虑自己实施一个.

我们想到了两种可能性.从头开始构建或包装多个词典.

包装多个词典

搜索一个项目时,我们可以看一下HasCode键,并使用它的起始编号作为包装词典列表的索引.虽然这似乎很容易让我闻到,但这意味着哈希码计算两次(内部字典一次由我们一次)(这种情况真的非常具有性能).

我知道像字典那样交换基类是绝对的最后一种可能性,我想避免它.但是目前看起来没有办法让对象更加独特,或者从数据库中获取字典的性能或者在其他地方保存性能.

我也意识到"要注意优化",但较低的性能会严重影响其背后的业务需求.

Answer 1

在我读完你的问题之前，我想到了简单的多词典。但你已经知道这个解决方案了。我假设您确实达到了字典中的最大项目数，而不是任何其他限制。

我想说，去吧。我认为您不应该担心对哈希值进行两次计数。如果它们的密钥有点长并且获取哈希确实是一项耗时的操作（我对此表示怀疑，但不能确定，因为您没有提到密钥是什么），那么您不需要为哈希函数使用整个密钥。只需选择您可以在自己的散列中处理的任何部分，并根据该部分分发项目即可。

您在这里唯一需要确保的是在多个词典中均匀分布项目。实现这一目标有多难实际上取决于您的密钥是什么。如果它们是完全随机的数字，您只需使用第一个字节就可以了（除非您需要超过 256 个字典）。如果它们不是随机数，您必须考虑其域中的分布，并以实现均匀分布目标的方式编码您的第一个哈希函数。