PHP散列密钥数组

Question

我在搜索布隆过滤器时，在GitHub上发现了这个简单的PHP类，它被称为"Bloom Filter"，但我认为它更像是一个"哈希表"，不管怎样，我很好奇，这个类非常容易理解。

它读取一个单词文件，并为每个单词创建一个哈希数组键，然后可以检查单词是否存在于哈希数组中。

不过，我很好奇使用这种方法是否有任何好处，与将实际单词存储为数组键或值，然后检查该单词是否存在于数组中相比，理论上这只会增加开销并执行相同的操作，请帮助我理解我错过了什么？

<?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';
}
?>

- JasonDavis

---

在我看来，你可以使用普通的 PHP 数组来实现这个功能，它们就像哈希表一样。 - hackartist

@hackartist：这正是我所想的，但我认为肯定有人费了很大的劲才做出这个东西，不然就没有意义了吧？ - JasonDavis

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：此代码将无法按预期工作，因为每个单词都会包含换行符，因此您需要先删除它。但我希望您能理解这个想法。）

- Niko

Answer 2

这种方法通常用于处理非常大的字符串。我曾在创建图库时使用过这种方法。上传的文件将以整个文件的sha1校验和命名（实际名称保存在数据库中）。这样，如果上传了重复的文件，它会被轻松拒绝。

我不知道从散列3个字母字符串（甚至是50个字母字符串）中获得什么好处。我不会这样做。您需要询问原始开发人员。

- Madara's Ghost

Answer 3

如果你在Github上发现了它，那么询问代码的作者可能是值得的。

字典类确实有两个优点——修剪键和避免重复，但以下代码大多等效，并且很可能更快：

$words = file($filepath);
$words = array_map('trim', $words);
$words = array_unique($words);
sort($words); // just for convenience debugging

...

if (in_array($test, $words)) {
    return true;
} else {
    return false;
}

如果有疑问，对每种（或任何一种）竞争技术进行基准测试应该能清楚地表明哪种是给定用例的最佳解决方案。

- AD7six

Answer 4

我认为那个构造函数和直接使用单词作为键之间没有任何功能上的区别。在php中，具有非数字键的数组本质上是哈希表（如果我没记错的话，语法和实现都是如此）。考虑以下代码片段：

$contents = file($filepath);
$dictionary = array();
foreach($contents as $word) {
    $dictionary[$word] = $word;
}

if(array_key_exists('den', $dictionary){
    echo 'The Word den Exist in the Hash Table';
}else{
    echo 'The Word den DOES NOT Exist in the Hash Table';
}

它和示例类做的事情是一样的。唯一失去的是->语法，但你可以在存在条件中使用$dictionary['den']...如果没有设置，则返回null，这将被评估为false，因此...

该类还违反了计算机科学中的一个规则，在不需要加密安全性的情况下使用密码哈希函数。与常规的非安全（相对而言；到这个时候，称MD5为安全的是可疑的）哈希函数相比，MD5算法的运行成本要高得多。使用字典类会更慢，而且实际上并没有提供任何东西。正如Truth指出的那样，比较非常长字符串的摘要可以节省时间。但计算摘要仍然很昂贵，为3个字母字符串计算摘要只是浪费时间。

- Patrick M