Wie wird die Hashfunktionsausgabe den Bloomfilter-Indizes zugeordnet?

Question

Kann mir jemand helfen, indem ich einen Überblick über die Zuordnung der Hash-Funktion zu den Bloom-Filter-Indizes gebe? Hier finden Sie eine Übersicht über bloomfilters.

Answer 1

eine Kontur auf, wie die Hash-Funktion Ausgabe an einen Bloom-Filter-Indizes abgebildet wird

Für jede der k Hash-Funktionen verwendet, ordnen sie in den Bloom-Filter ein Bit auf genauso Hashes mappen auf Hash-Buckets in einer Hash-Tabelle. Also, sehr häufig haben Sie vielleicht eine Hashfunktion angegeben, die 32-Bit-Ganzzahlen erzeugt, und dann den Modulo-Operator % verwenden, um einen Bitindex 0 << i < n zu erhalten, wobei n die Anzahl der Bits in Ihrem Bloom-Filter ist.

Um dies sehr konkret zu machen, sagen wir mal eine Hash-Funktion auf 2^32-1 Zahlen von 0 erzeugt, und es gibt 1000 Bits in Ihrer Blüte Filter:

int bit_index = hash_function(input_value) % 1000; 

Es ist wichtig, hier zu beachten, dass 2^32-1 ist massiv größer als 1000. Sagen wir, die Hash-Funktion erzeugt stattdessen ziemlich gleichmäßig verteilte Zahlen, aber nur zwischen 0 und 1023 einschließlich, dann wäre es nach der Modulo-Operation doppelt so wahrscheinlich, dass bit_index in der 0..23 wäre Bereich im Vergleich zu 24..999 (weil z. B. die Eingänge 2 und 1002 beide zu einem Post-Modulus-Wert von 2 führen, aber nur ein Eingang von 25 eine Ausgabe von 25 erzeugt). Wenn Sie also eine Hash-Funktion haben, die 32 Bit erzeugt, möchten Sie vielleicht einen Bloom-Filter verwenden, der auf eine Anzahl von Bits mit einer Zweierpotenz zugeschnitten ist, und dann Abschnitte des Hash-Werts als unabhängige Hash-Funktionen ausschneiden - Alles erklärt in dem Wikipedia-Artikel, den Sie verlinken. Dies erfordert jedoch eine Hash-Funktion von guter Qualität, da irgendwelche "Clustering" -Fehler in der Hash-Funktion vollständig zur Ausgabe durchgeleitet werden; eine Primzahl von Bits zu haben, ist eine Möglichkeit, solch schlechtes Hashing zu mindern. Mit guten Hash-Funktionen machen Potenzen von zwei es auch einfach, Bit-Indizes durch bitweise UND-Operationen und - falls erforderlich - Bit-Verschiebung zu extrahieren, die schneller als der Ganzzahl-Modul sein kann, obwohl die Hash-Funktionen diese Betrachtung wahrscheinlich in den Schatten stellen werden das allgemeine Leistungsprofil.

Bearbeiten - Adressierung Kommentare ...

Angenommen, Ihre MD5-Funktion ist ein unsigned char* "p" zu MD5_DIGEST_LENGTH Byte Daten zurückkehrte, schlug ich vor, Sie versuchen:

BOOST_STATIC_ASSERT(MD5_DIGEST_LENGTH >= sizeof(int)); 
int bit_index = *reinterpret_cast<unsigned int*>(p) % num_of_bloom_filter_bits; 

Das ist ein besonders eigentlich war schlecht Idee - Entschuldigung - ich werde die zwei Gründe erklären, warum in einem Moment. Zuerst, um Ihre Frage zu beantworten, was es tut: BOOST_STATIC_ASSERT() ist entworfen, um Ihnen einen Kompilierungsfehler zu geben, wenn der Ausdruck, der es übergibt, zu false ausgewertet worden ist. Hier ist im Grunde genommen eine Möglichkeit, die Anforderung zu dokumentieren, dass MD5_DIGEST_LENGTH - die Zeichengröße der textuellen Darstellung des MD5-Hashwerts - mindestens so lang ist wie die Anzahl der Byte, die Ihr System für einen Integer-Typ int verwendet. (Diese Größe ist wahrscheinlich 4 Bytes, könnte aber 8 sein.) Diese Anforderung soll sicherstellen, dass der reinterpret_cast in der nächsten Zeile sicher ist. Was das ist, liest einen Wert aus den Bytes am Anfang der textuellen Darstellung des MD5-Hash, als ob diese Bytes eine int enthalten. Also, sagen Sie Ihre int Größe ist 4, MD5-Hash ist "0cc175b9c0f1b6a831c399e269772661" wie in Ihrem Kommentar: die ersten 4 Bytes enthalten "0cc1". Die ASCII-Codes für diesen Text sind 48, 99, 99, 49 dezimal.Wenn sie in eine int gelesen werden, kann der Wert abhängig von der Endianess der CPU abweichen, aber im Grunde erhalten Sie eine dieser Zahlen mal 256^3 plus ein weiteres mal 256^2 plus ein drittes mal 256 plus das Finale Nummer.

Die Gründe, warum ich sagte, dies wäre eine besonders schlechte Idee ist:

• jedes Zeichen in dem MD5-String ist entweder eine Ziffer (ASCII-Codes 48-57) oder ein Brief von "a" bis "f" (97-102). Diese 16 Werte sind nur ein 16tel der Variation, die ein Byte haben kann, und während der int Wert, den Sie erzeugen, 32 Bits belegt, erhalten Sie wirklich nur 2^16 verschiedene Werte.
• auf einigen Computern, int s muss an einer Speicheradresse, die ein Vielfaches von 2, 4, 8 usw. ausgerichtet ist ausgerichtet sein. Die reinterpret_cast - wenn der Text geschieht zufällig an einer inkompatiblen Adresse, könnte Ihren Computer zum Absturz bringen. Hinweis: Intel & AMDs haben keine solche Ausrichtungsanforderung, obwohl es für sie möglicherweise schneller ist, mit ordnungsgemäß ausgerichteten Daten zu arbeiten.

Also, ein weiterer Vorschlag:

// create a buffer of the right size to hold a valid unsigned long in hex representation... 
char data[sizeof(unsigned long) * 2 + 1]; 

// copy as much of the md5 text as will fit into the buffer, NUL terminating it... 
sprintf(data, "%.*s", sizeof data - 1, md5); 

// convert to an unsigned long... 
m = strtoul(data, /*endptr*/ NULL, /*base*/ 16); 

Wenn hier die md5 Darstellung kürzer als der Datenpuffer war, nur der erste Teil davon sicher kopiert werden würde, so dass der BOOST_STATIC_ASSERT ist nicht erforderlich.

Es ist viel einfacher, eine nicht-kryptografische Hash-Funktion zu verwenden, da sie Ihnen im Allgemeinen nur eine Zahl und nicht eine lesbare Textpuffer-Darstellung der Zahl zurückgibt, sodass Sie all diesen Unsinn vermeiden können.