我有一个Dictionary可能包含超过1000万个唯一键的潜力.我正在尝试减少这需要的内存量,同时仍然保持字典的功能.
我想的是将字符串的哈希值存储为long,这会将应用程序内存使用量减少到可接受的量(~1.5 gig到〜.5 gig),但我对我的做法感觉不太好这个.
long longKey= BitConverter.ToInt64(cryptoTransformSHA1.ComputeHash(enc.GetBytes(strKey)), 0);
基本上,这会在SHA1散列的末尾进行切换,并将其中的第一个块放入long中,然后将其用作键.虽然这是有效的,至少对于我正在测试的数据,我不认为这是一个非常可靠的解决方案,因为关键冲突的可能性增加.
有没有其他方法可以减少字典的内存占用,或者我上面提到的方法并不像我想的那样可怕？
[编辑]为了澄清,我需要保持使用字符串查找字典中包含的值的能力.将实际字符串存储在字典中会占用大量内存.我想要做的是使用一个Dictionarylong,其中long是字符串上的散列函数的结果.
所以我最近做了类似的事情,由于某些原因,我的应用程序相当独特,没有使用数据库.实际上我试图停止使用数据库.我发现GetHashCode在3.5中得到了显着改善.一个重要的注意事项,永远不要存储GetHashCode的结果.永远不能.它们不保证在框架版本之间保持一致.
因此,您确实需要对数据进行分析,因为不同的哈希函数可能对数据的效果更好或更差.您还需要考虑速度.作为一般规则,即使哈希数量变为数十亿,加密哈希函数也不应该有很多冲突.对于我需要独特的东西,我通常使用SHA1 Managed.通常,CryptoAPI具有糟糕的性能,即使底层的哈希函数表现良好.
对于64位散列,我目前使用Lookup3和FNV1,它们都是32位散列.对于发生碰撞,两者都需要碰撞,这在数学上是不可能的,而且我没有看到超过大约1亿个哈希发生.您可以在网上找到公开提供的代码.
仍然进行自己的分析.对我有用的东西可能不适合你.实际上,在我办公室内,具有不同要求的不同应用程序实际上使用不同的散列函数或散列函数的组合
我会避免任何未经证实的哈希函数.哈希函数与认为应该编写它们的人一样多.做你的研究和测试测试.
有1000万条记录,您是否考虑过使用非聚集索引的数据库？对于这类事情,数据库有很多技巧.
根据定义,在任何算法下,散列都有可能发生冲突 - 特别是在大量的情况下.根据情况,我会非常谨慎.
使用字符串可能占用空间,但它是可靠的...如果你在x64上,这不需要太大(虽然它绝对算作"大";-p)
顺便说一下,加密哈希/哈希函数对字典来说非常糟糕.他们又大又慢.通过解决一个问题(大小),你只引入了另一个更严重的问题:函数不会再均匀地扩展输入,从而破坏了良好哈希的单个最重要的属性,以接近无冲突寻址(如你好像已经注意到了自己).
/编辑:正如安德鲁所指出的,这GetHashCode是该问题的解决方案,因为这是它的预期用途.就像在真正的字典中一样,你将不得不解决碰撞问题.其中一个最好的方案是双重散列.不幸的是,唯一100%可靠的方法是实际存储原始值.否则,你已经创建了一个无限压缩,我们知道它不存在.
京公网安备 11010802040832号 | 京ICP备19059560号-6 