2014-01-21 45 views
2

我有比较大量的字符串数据(csv文件)的问题。这些文件具有唯一标识符,但没有排序,它们非常大。.Net C#String.GetHashCode()替代

所以我试图创建两个字典,其中key是来自文件的uniqueID,Value是int,它返回我感兴趣的字符串的GetHashCode()。

但是,简单的例子:

if ("30000100153:135933:Wuchterlova:335:2:Praha:16000".GetHashCode() == 
    "30000263338:158364:Radošovická:1323:10:Praha:10000".GetHashCode()) 
{ 
    Console.WriteLine("Hmm that's strange"); 
} 

那么,有没有任何其他方式如何做到这一点。

我需要尽可能少footprit尽可能(由于以下两个dictionarie两个CSV文件中的内存分配,其中包含有关3M行) 谢谢

+0

我想你会发现这个线程有趣!http://stackoverflow.com/questions/735317/hashtable-dictionary-collisions –

+3

散列码不是唯一的。它们根本不可能,因为即使在长度为3((2^16)^ 3 = 2^48)的字符串中,可能的字符串值也比可能的散列值(2^32)多。 –

+0

'GetHashCode'实现针对速度而不是唯一性进行了优化。如果您希望将冲突风险降至最低,请改用加密函数(如SHA)。 – Douglas

回答

17

首先,对于string.GetHashCode 文档专门说不要为任何需要长时间保持稳定的应用程序使用字符串散列码,因为它们不是。您应该只使用字符串哈希代码,仅用于一个目的,即将字符串放入字典中。

其次,哈希码不是唯一的。只有40亿个可能的散列码(因为散列码是32位整数),但显然有40多亿个字符串,所以必须有许多具有相同散列码的字符串。仅包含几千个字符串的集合具有包含具有相同哈希码的两个字符串的可能性极高。概率的曲线是在这里:

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

所以,你可能想知道字典是如何工作的,在所有的话,如果它使用的GetHashCode但可以有冲突。答案是:当你在具有相同散列码的字典中放入两件事X和Y时,它们会进入同一个“桶”。当您搜索X时,字典会使用哈希码进入右边的存储桶,然后对存储桶中的每个元素进行昂贵的相等性检查,直到找到合适的存储单元为止。由于每个桶都很小,所以大部分时间这个检查仍然足够快。

我不知道如何解决你的问题,但使用32位哈希显然不是正确的方式来做到这一点,所以试试别的。如果您需要管理大量数据,我的建议是开始使用数据库而不是CSV文件。这就是数据库的用途。

我已经写上串散列许多文章,你可能感兴趣的:

http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/

http://blogs.msdn.com/b/ericlippert/archive/2011/07/12/what-curious-property-does-this-string-have.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/10/24/do-not-use-string-hashes-for-security-purposes.aspx

http://blogs.msdn.com/b/ericlippert/archive/tags/hashing/

+0

可能会使用类似于懒加载字典,将根据需要加载文件的内容? –

+0

好吧,即使他将自己的字符串存储在字典中,即使他确实碰到了散列冲突,他仍然可以逃避它。 Dictionary类应该处理冲突,但是对于他的应用程序来说性能影响可能太大了。 –

+0

问题是我需要比较旧的/新的文件来查找添加/删除或更改的行,其中第一列有uniqueID。它必须具有足够的内存和速度。 – avojacek

0

你实际上并不想用的GetHashCode 。你应该直接比较字符串。但是,将每个3M字符串与另一个3M字符串进行比较在任何合理的时间内都会很困难,而无法首先对列表进行排序。

我的做法是先解决每个列表(如何做到这一点取决于很多的东西),阅读首先从各分类 - 让通话则A和B:

  1. 如果A =然后B做什么,读下一个A和一个B-和重复
  2. 如果A < B没有什么和下一个读取A和重复
  3. 如果A> B做什么和阅读下一B和重复

。 where'd o无论什么意思做任何需要在那种情况下,重复的手段回到第1步。

(这个过程是如何使用大型计算机合并堆叠卡,并有一个特定的名称,但我不能为我的生活还记得吧)

干杯 -