相关疑难解决方法(0)

这个问题仅供我使用,因为我总是喜欢编写优化的代码,这些代码也可以在便宜的慢速服务器(或具有大量流量的服务器)上运行

我环顾四周,无法找到答案.我想知道这两个例子之间的速度有多快,记住我的情况下数组的键并不重要(伪代码自然):

<?php
$a = array();
while($new_val = 'get over 100k email addresses already lowercased'){
    if(!in_array($new_val, $a){
        $a[] = $new_val;
        //do other stuff
    }
}
?>

<?php
$a = array();
while($new_val = 'get over 100k email addresses already lowercased'){
    if(!isset($a[$new_val]){
        $a[$new_val] = true;
        //do other stuff
    }
}
?>

由于问题的关键不在于数组冲突,我想补充一点,如果你害怕碰撞插入$a[$new_value],你可以使用$a[md5($new_value)].它仍然可能导致冲突,但是当从用户提供的文件中读取时会从可能的DoS攻击中消失(http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html)

该djb2算法对字符串的哈希函数.

unsigned long hash = 5381;
int c;

while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

为什么5381和33如此重要？

我正在尝试编写一个使用哈希表来存储不同单词的C程序,我可以使用一些帮助.

首先,我创建一个哈希表,其中素数的大小最接近我必须存储的单词的数量,然后我使用哈希函数来查找每个单词的地址.我从最简单的功能开始,将字母加在一起,结果是88%的碰撞.然后我开始尝试该功能,发现无论我改变它,碰撞都不会低于35%.现在我正在使用

unsigned int stringToHash(char *word, unsigned int hashTableSize){
  unsigned int counter, hashAddress =0;
  for (counter =0; word[counter]!='\0'; counter++){
    hashAddress = hashAddress*word[counter] + word[counter] + counter;
  }
  return (hashAddress%hashTableSize);
}

这只是我提出的随机功能,但它给了我最好的结果 - 大约35%的碰撞.

过去几个小时我一直在阅读有关散列函数的文章,我尝试使用一些简单的函数,比如djb2,但是所有这些都给了我更糟糕的结果.(djb2导致了37%的碰撞,这是'更糟糕的是,但我期待更好而不是更糟糕的事情)我也不知道如何使用其他更复杂的一些,例如murmur2,因为我不知道参数是什么(关键,len ,种子)他们接受了.

即使使用djb2,或者我做错了什么,获得超过35%的碰撞是正常的吗？什么是关键,len和种子价值？

我正在阅读K&R的"The C Programming Language"一书.在"结构"一章中,在"表查找"(页144)的子主题下,我找到了此哈希生成函数

#define HASHSIZE 101

struct nlist {
    struct nlist *next;
    char *name;
    char *defn;
}

static struct nlist *hashtab[HASHSIZE];

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

我不明白的是这个功能实际上是做什么的.

我认为它为给定的字符串(char*s)生成一个唯一的地址(作为hashtab的索引).

但我认为两个不同的字符串可以被赋予相同的索引,因为(hashval%HASHSIZE)是给定的地址(203%101 = 405%101 = 1).

为什么HASHSIZE 101和hashval乘以31？为什么不是100或32？