PHP哈希密钥数组

Question

我在搜索Bloom过滤器时在GitHub上遇到了这个简单的PHP类,这被称为"Bloom过滤器",但我认为它更像是一个"哈希表",无论是我好奇的方式,它都很容易理解.

它读入一个单词文件并为每个单词创建一个哈希数组键,然后您可以检查该单词是否存在于哈希数组中.

我很好奇,虽然使用这个有什么好处,只是将实际的单词存储为数组键或值,然后检查数组中是否存在该单词,理论上这只会增加开销并做同样的事情,请帮忙我明白我错过了什么？

<?php
class Dictionary {
    private $words;
    private $wordsHash;
    public $hashLength;

    public function __construct($filepath, $hashLength) {
        $this->words = file($filepath);
        $this->hashLength = $hashLength;
        foreach($this->words as $word){
            $this->wordsHash[$this->createHash($word)] = true;
        }
        echo 'words: ' . count($this->words) . '   hashes: ' . count($this->wordsHash) . "\n";
    }

    public function createHash($str){
        $hash = substr(md5(trim($str)), 0, $this->hashLength);
        return $hash;
    }

    public function checkDictionary($str){
        $hash = $this->createHash(trim($str));
        if(array_key_exists ($hash , $this->wordsHash)){
            return true;
        }
        return false;
    }

}
?>

dictionary.txt文件中有10,000个单词,我只会展示一些用于演示

der
die
und
in
den
von
zu
das
mit
sich
des
auf
für
ist

用法示例:

<?php
$dictionary = new Dictionary('dictionary.txt', 30);

if($dictionary->checkDictionary('den')){
    echo 'The Word den Exist in the Hash Table';
}else{
    echo 'The Word den DOES NOT Exist in the Hash Table';
}
?>

Answer 1

与此相关的想法似乎是搜索密钥要比在数组中搜索特定值快得多.对于非常大的阵列尤其如此.但是,我建议采用一种更简单的方法(如您所说)避免开销和冲突:

$words = array_flip( file($filename) );

// The actual values are now the keys!
// So checking for a word works like this:
if (isset($words['und'])) {
    // ...

// Travling through the words works like this:
foreach ($words as $word => $i) {
    // ...

(PS:这段代码不会按预期工作,因为每个单词都会包含换行符,所以你需要先删除它.但我希望你明白这一点.)