闲聊哈希表 （中）
作者 帅云霓 | 2010-03-04 06:20 | 类型 专题分析 | 6条用户评论 »
|
闲聊哈希表 （中） 上期，我们说到了散列函数(Hash Function)。它又名哈希函数，是计算机科学中一个重要的课题。什么是散列函数呢？其实，这个概念并没有一个严格的定义。一般说来，散列函数满足以下的条件： 1、对输入值运算，得到一个固定长度的摘要(Hash value)； 2、不同的输入值可能对应同样的输出值； 以下的函数都可以认为是一个散列函数： f(x) = x mod 16; (1) f(x) = (x2 + 10) * x; (2) f(x) = (x | 0x0000FFFF) XOR (x >> 16); (3) 不过，仅仅满足上面这两条的函数，作为散列函数，还有不足的地方。我们还希望散列函数满足下面几点： 1、散列函数的输出值尽量接近均匀分布； 2、x的微小变化可以使f(x)发生非常大的变化，即所谓“雪崩效应”(Avalanche effect)； 上面两点用数学语言表示，就是： 1， 输出值y的分布函数F(y)=y/m, m为散列函数的最大值。或记为y~U[0, m] 2，|df(x)/dx| >> 1； 从上面两点，大家看看，前面举例的三个散列函数，哪个更好呢？对了，是第三个： f(x) = (x | 0x0000FFFF) XOR (x >> 16); 它很完美地满足“好的散列函数”的两个附加条件。 那么，为什么散列函数要带有这两个附加条件呢？原来，这是为了减少“哈希冲突”（Hash collision），也就是两个不同输入产生了相同输出值的情况。根据抽屉原理，Hash算法不可能没有冲突(collision)，但是，由于冲突会造成一些问题，可能会影响到应用Hash函数的某些算法的效率，所以，我们需要尽量避免之。这样，对Hash算法的选择，就是很重要的了。密码学中的著名摘要算法的MD5和SHA1，以及另一种用于字符串摘要计算的Jenkins Hash算法，都是很经典的Hash算法，有兴趣的同学可以阅读参考。 顺便延伸阅读一下，对计算机信息安全感兴趣的同学，一定听说过密码学家王小云教授。王教授成名的贡献，就是发现了大大加速找出MD5和SHA1等Hash算法冲突的方法。譬如，根据“生日攻击”理论，对于Hash value为160bit的SHA1算法，找出一个Hash冲突需要280次运算，而王小云找出了一个269次运算就能找出冲突的算法，也就是提高了211=2048倍的效率！所以说，王教授的成果大大动摇了现代密码学的基础。 今天的最后，给大家留下了一个问题：上次说到，Hash表中，数据存储的位置，是通过Hash函数计算得到的。那么，如果两条数据记录的Hash值发生冲突，应该怎么办呢？ | |
 (3个打分， 平均：5.00 / 5) |
雁过留声
“闲聊哈希表 （中）”有6个回复
SHA-1：2^63是最好的bound，但是5年过去了，谁也没有找到一对Collision，包括xiaoyun自己。SHA-2是现在的推荐选择。即将出炉的SHA-3是另一个热点.
》也就是提高了211=2048倍的效率！
这个不算什么，搞2k计算机来并行运算就行了。关键是理论下限2^80被突破了。对于hash function，密码学家将任何优于Exhaustive Search的解法叫Attack。
很好，通俗易懂。
解冲突的办法很多，但解冲突本身的代价使得我们不妨去思考如何“不冲突”
我提供两个比较“时髦”的方案：
1）用signature替换key进行比较，通过存储多个signature来解决hash冲突（其实一种分层的hash）
2）bloomfilter，用multi-hash减少“哈错”的可能性
3）perfect hash，也就是没有冲突的hash；理论上很漂亮，大多情况不可行，但不是没有价值。
二次散列函数，可以大大减小冲突的产生
概念搞混淆了
secure hash算法的定义，要求给定一对m0，hash(m0)。在有效时间内你不能找到一个m1，使hash(m1) = hash(m0)
冲突的概率与你的算法的均衡性与digest length有关。根据birthday paradox理论上计算次数是2^(digest length/2)。王小云的贡献就是发现了sha1算法中那微小的一点点的bias。使sha1的理论计算速度突破了密码学中的安全底线。
工程上的hash，需要观察message的特性，给出冲突概率最小的算法。这种算法在设计上本身就是有bias的。而且你哪怕4GB的hash table，digest length也不过30bit。