我在 GitHub 上搜索布隆过滤器时遇到了这个简单的 PHP 类,它被命名为"布隆过滤器",但我认为它更像是一个"哈希表",无论哪种方式我都很好奇,它很容易理解。
它读取单词文件并为每个单词创建一个哈希数组键,然后您可以检查该单词是否存在于哈希数组中。
我很好奇使用它有什么好处,而不是仅仅将实际单词存储为数组键或值,然后检查该单词是否存在于数组中,理论上这只是增加开销并做同样的事情,请帮助我了解我缺少什么?
<?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;
}
}
?>
字典.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';
}
?>
这样做的想法似乎是搜索键比搜索数组中的特定值快得多。对于非常大的数组尤其如此。但是,我建议使用一种更简单的方法来(如您已经说过的(避免开销和冲突:
$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:此代码将无法按预期工作,因为每个单词都会包含换行符,因此您需要先将其剥离。但我希望你明白这个想法。
这种方法通常是用非常大的字符串完成的。我曾经在创建画廊时使用过这种方法。上传的文件将以整个文件的sha1
校验和命名(而实际名称保存在数据库中(。这样,如果上传了重复的文件,则很容易被拒绝。
我不知道他会从散列 3 个字母字符串(甚至 50 个字母字符串(中获得什么好处。我不会那样做。您将询问原始开发人员。
如果你在github上找到了它 - 可能值得问问你找到的代码的作者。
字典类确实有 2 个好处 - 它修剪键,避免重复,但以下代码大多是等效的,并且可能要快得多:
$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;
}
如果有疑问,对每种(或任何(竞争技术进行基准测试应清楚地表明哪种是给定用例的最佳解决方案。
我看到该构造函数与仅使用单词本身作为键之间没有功能差异。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 个字母字符串的摘要只不过是浪费时间。