PHP 해시 키 배열

Question

블룸 필터를 검색하는 동안 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; 
    } 

} 
?> 

하는 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 : 줄 바꿈을 포함 모든 단어 때문에 예상대로 당신이 필요합니다, 그래서이 코드는 작동하지 않습니다 먼저 그 코드를 벗겨 내고 싶습니다.하지만이 아이디어를 얻길 바랍니다.)

Answer 2

이 접근 방식의이 종류는 일반적으로 수행됩니다 매우 큰 문자열. 한 번 갤러리를 만들 때이 방법을 사용했습니다. 업로드 된 파일의 이름은 전체 파일의 sha1 체크섬 (실제 이름이 데이터베이스에 저장되는 동안)의 이름을 따서 지정됩니다. 이렇게하면 중복 된 파일이 업로드되면 쉽게 거부됩니다.

3 글자 문자열 (또는 심지어 50 글자 문자열)을 해싱하면 어떤 이점이 있는지 정확히 알 수 없습니다. 나는 그렇게하지 않을 것이다. 원래 개발자에게 물어볼 것입니다.

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

의심하는 경우, 각각의 벤치마킹 (또는 :이 키를 트림, 중복을 피하지만, 다음 코드는 주로 해당하고, 훨씬 빨리 될 가능성이 높습니다 -

사전 클래스는이 개 혜택이 있나요 모든 경쟁 기술은 주어진 유스 케이스에 가장 적합한 솔루션이 무엇인지 명확하게 나타내야합니다.

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 보안 호출은이 시점에서 모호함) 해시 함수보다 실행하는 것이 훨씬 비쌉니다. 사전 클래스를 사용하면 실제로 아무것도 제공하지 않는 것보다 훨씬 느려집니다. 진실이 지적한 것처럼 매우 긴 문자열의 다이제스트를 비교하면 시간을 절약 할 수 있습니다. 그러나 다이제스트를 계산하는 것은 여전히 ​​비싸며 3 글자 문자열에 대한 컴퓨팅 다이제스트는 시간 낭비 일뿐입니다.