Exo*_*ist 7 hash 32-bit 16-bit collision
我正在研究一个哈希冲突会成为问题的系统.本质上,有一个系统引用散列表+树结构中的项.但是,有问题的系统首先将包含结构中路径的文本文件编译为包含散列值的二进制文件.这是出于性能原因而完成的.但是由于这种冲突非常糟糕,因为结构不能存储具有相同散列值的2个项目; 要求物品的部分没有足够的信息来知道它需要哪一个.
我最初的想法是2个哈希,要么使用2种不同的算法,要么使用相同的算法两次,使用2种盐会更具抗冲突性.对于不同的散列算法具有相同散列的两个项目是非常不可能的.
由于空间原因,我希望保持32位的哈希值,所以我想我可以切换到使用两个16位算法而不是一个32位算法.但这不会增加可能的哈希值范围......
我知道切换到两个32位哈希会更具抗冲突性,但我想知道切换到2个16位哈希是否至少比单个32位哈希有一些增益？我不是数学上最倾向的人,所以我甚至不知道如何开始检查答案,而不是强迫它...
系统的一些背景:
项目由人类命名,它们不是随机字符串,通常由没有空格的单词,字母和数字组成.它是一个嵌套的哈希结构,所以如果你有类似{a => {b => {c =>'blah'}}}的东西,你可以通过获得a/b/c的值获得值'blah',编译请求将是直接序列中的3个哈希值,哈希值为a,b,然后是c.
当给定级别发生碰撞时,只有一个问题.顶级项目与较低级别之间的碰撞很好.您可以{a => {a => {...}}},几乎可以保证不同级别的冲突(不是问题).
实际上,任何给定级别的哈希值都可能少于100个,并且在同一级别上没有任何值会重复.
为了测试我采用的哈希算法(忘了哪一个,但我没有发明它)我下载了整个CPAN Perl模块列表,将所有命名空间/模块拆分成唯一的单词,最后散列每个搜索冲突,我遇到0碰撞.这意味着该算法对CPAN命名空间列表中的每个唯一字具有不同的散列值(或者我做错了).这对我来说似乎足够好,但它仍然在我的大脑中唠叨.
如果你有2个16位哈希值,它们产生不相关的值,那么你刚刚编写了一个32位哈希算法.这不会比任何其他32位哈希算法更好或更差.
如果你担心碰撞,请确保你使用的散列算法可以很好地散列你的数据(有些只是为了快速计算,这不是你想要的),并增加你的大小哈希,直到你感到舒服.
这提出了碰撞概率的问题.事实证明,如果你n的收藏中有东西,那么就有n * (n-1) / 2可能会碰撞的东西.如果你使用的是k比特哈希,那么一对碰撞的几率就是.如果你有很多东西,那么不同对碰撞的几率几乎是不相关的.这正是Poisson分布描述的情况.2-k
因此,您将看到的碰撞次数应大致遵循泊松分布.由此可知无哈希冲突的概率.对于32位和100项,一级碰撞的几率约为1.1525万.如果你这么做的时间足够多,有足够多的不同数据集,那么最终百万分之一的机会就会加起来.? = n * (n-1) * 2-k-1e-?
但请注意,您有许多正常大小的级别和一些大型级别,大型级别将对您的碰撞风险产生不成比例的影响.这是因为你添加到集合中的每一件事都可能与任何先前的事情相冲突 - 更多的事情等于更高的碰撞风险.因此,例如,具有1000个数据项的单个级别在10,000个失败中具有大约1个机会 - 这与具有100个数据项的100个级别大致相同.
如果散列算法没有正常工作,您的碰撞风险将迅速上升.多快取决于失败的性质.
使用这些事实以及您对应用程序使用情况的预测,您应该能够确定您是否对32位哈希值的风险感到满意,或者是否应该将其提升到更大的范围.