Web 技术研究所

我一直坚信着,Web 将会成为未来应用程序的主流

关于散列冲突

  很多编程语言都通过散列表的形式来存储数据,要是散列算法不好就很容易产生冲突。 比如 PHP 就一直存在这个问题,原来 5.3 的时候我就踩过这个坑,没想到现在 5.5 还依然存在。PHP 不对自然数索引做散列计算导致了我们可以轻易地制造出冲突。
  何谓散列冲突?之前的文章中有稍微提及,但没有展开这个话题。
  我们公司对每个入职的同事都会开通一个电子邮箱,电子邮箱的用户名直接用了姓名的汉语拼音。可以把这个过程视为一个散列函数,把个人信息全部映射到「姓名的汉语拼音」这样一个散列结果上。然而这是一个非常烂的散列函数。我们组的一个小女孩入职时其名字的汉语拼音就和已经存在的一个小伙子冲突了。虽然加个前缀或后缀就可以解决问题,但之后发邮件的时候也经常会弄错,这就浪费了时间。也就是说,当散列冲突的时候,被降级为了链表存储,之后的访问就会产生性能问题。
  散列冲突的问题本来就是无法绝对防止的,我们只能尽可能地降低概率。就像两个人姓名的汉语拼音相同这种问题也只是偶然事件。但要是散列函数处理不好就会造成大规模的散列冲突,结果是很可怕的。就像一个公司里的人全叫同一个名字,结果还使用汉语拼音作为电子邮箱名一样。
  PHP 的这个问题已经是个老梗了,它对自然数索引直接不做散列计算,只是简单地使用取余来映射内存。那么如果知道了 PHP 对散列表的内存分配规则为 pow(2, ceil(log($count, 2))),分分钟就可以造出一个完全散列碰撞的情况。比如下面这个测试代码 <?php
header('Content-Type: text/plain');

$size = 1 << 15;
$max = $size * $size;

// Test 1
$startTime = microtime(true);
$array = array();
for ($key = 0; $key <= $max; $key += $size) {
    $array[$key] = 0;
}
echo microtime(true) - $startTime, "\n";

// Test 2
$startTime = microtime(true);
$array = array();
for ($key = 0; $key <= $max; $key += $size) {
    $array['字符串索引会进行散列计算,所以很快' . $key] = 0;
}
echo microtime(true) - $startTime, "\n";
?>

  看看这神奇的差异,Test 2 中每个索引用了那么复杂的字符串,结果却比 Test 1 中使用自然数所以的快得多。真是给「最好的编程语言」跪了。JavaScript 虽然也存在散列冲突的情况,但它至少目前主流的 JavaScript 引擎都对自然数索引做了散列处理,所以必须根据特定 JavaScript 的散列函数做一个冲突生成器才能造出冲突。退一步说吧,上面的测试仅仅是做一个写入而已,即使被退化成链表存储,写入速度也应该是 O(1) 才对。呵呵,除非它没存尾指针却把新写入的元素放到了末尾。
  总之散列冲突是个危险的东西,而「最好的编程语言」还是很有优化空间的。
网名:
3.80.55.*
电子邮箱:
仅用于接收通知
提交 悄悄的告诉你,Ctrl+Enter 可以提交哦
神奇海螺
[查看全部主题]
各类Web技术问题讨论区
发起新主题
本模块采用即时聊天邮件通知的模式
让钛合金F5成为历史吧!
次碳酸钴的技术博客,文章原创,转载请保留原文链接 ^_^