PHP Hash Key Array

Question

Я столкнулся с этим простым классом PHP на GitHub при поиске Bloom Filters, это было названо как «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 файл имеет 10000 слов в нем, я просто покажу несколько для демо

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: Этот код не будет работать, как и следовало ожидать, так как каждое слово будет включать разрыв строки, так что вам нужно будет но я надеюсь, что вы поняли это.)

Answer 2

Такого рода подход, как правило, делается с очень большие струны. Я использовал этот метод при создании галереи. Загруженный файл будет называться после контрольной суммы sha1 всего файла (в то время как фактическое имя сохраняется в базе данных). Таким образом, если дубликат файла будет загружен, ему будет легко отказано.

Я не знаю, какую выгоду он получит от хэширования трех буквенных строк (или даже 50 буквенных строк в этом отношении). Я бы так не сделал. У вас будет запрос оригинального разработчика.

Answer 3

Если вы нашли его на 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; 
} 

Если сомневаетесь, бенчмаркинг каждый (или любой) конкурирующий метод должен четко указывать, что является лучшим решением для данного варианта использования.

Answer 4

Нет функциональной разницы, которую я вижу между этим конструктором и просто используя сами слова в качестве ключей. Массивы в php с нечисловыми являются, по существу, hashmaps (в синтаксисе и в реализации, если я правильно помню). Рассмотрим этот фрагмент:

$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 защита, сомнительная по этой точке) хэш-функция. Использование словарного класса будет значительно медленнее, а не действительно ничего. Как указывает Истина, сравнение дайджестов очень длинных строк может сэкономить ваше время. Но вычисление дайджеста по-прежнему дорого, а вычисления для трех буквенных строк - всего лишь пустая трата времени.