Der Übergang von Linear Quadratic Probing zu Probing (Hashkollisionen)

Question

Meine aktuelle Implementierung einer Hash-Tabelle verwendet Linear Probing und jetzt will ich Quadratic bewegen Probing (zu und später zu verketten und vielleicht Doppel-Hashing). Ich habe ein paar Artikel, Tutorials, wikipedia lesen, etc ... Aber ich weiß noch nicht genau, was ich tun soll.

Linear Probing, hat grundsätzlich einen Schritt von 1 und das ist einfach zu tun. Bei der Suche, Einfügen oder ein Element aus der Hash-Tabelle zu entfernen, muss ich einen Hash berechnen und dafür möchte ich dies tun:

index = hash_function(key) % table_size;

Dann, während der Suche, Einfügen oder Entfernen ich Schleife durch den Tisch, bis ich einen freien Eimer, wie diese finden:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

Wie bei Quadratic Probing, ich denke, was ich tun muß, ist die Veränderung, wie die „Index“ Schrittgröße berechnet wird, aber das ist, was ich verstehe nicht, wie ich es tun soll. Ich habe verschiedene Teile des Codes zu sehen, und alle von ihnen sind etwas anders aus.

Auch ich habe einige Implementierungen von Quadratic gesehen Probing, wo die Hash-Funktion geändert wird, untergebracht, dass (aber nicht alle von ihnen). Wird diese Änderung wirklich benötigt oder kann ich vermeiden, dass die Hash-Funktion zu modifizieren und nach wie vor verwenden Quadratic Probing?

EDIT: Nach der Lektüre alles von Eli Bendersky wies darauf hin, unten Ich glaube, ich die allgemeine Idee. Hier ist ein Teil des Codes unter http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

Es gibt zwei Dinge, die ich nicht bekommen ... Sie sagen, dass quadratische Sondieren in der Regel unter Verwendung von c(i)=i^2 erfolgt. Doch oben im Code, tut es etwas mehr wie c(i)=(i^2-i)/2

Ich war bereit, diese auf meinem Code zu implementieren, aber ich würde einfach tun:

index = (index + (index^index)) % table_size;

... und nicht:

index = (index + (index^index - index)/2) % table_size;

Wenn überhaupt, würde ich tun:

index = (index + (index^index)/2) % table_size;

... verursacht ich anderes Code-Beispiele Tauchen von zwei gesehen habe. Obwohl ich verstehe nicht, warum ...

1) Warum ist es den Schritt subtrahieren?
2) Warum ist es tauchen sie durch 2?

Answer 1

Sie müssen nicht die Hash-Funktion für quadratische Sondieren ändern. Die einfachste Form der quadratischen Sondieren ist wirklich einfach nur mit daraus folgenden Quadrate auf die berechnete Position anstelle von linearen 1, 2, 3.

Es gibt eine gute Ressource hier . Im Folgenden wird von dort übernommen. Dies ist die einfachste Form der quadratischen Sondieren, wenn die einfache Polynom c(i) = i^2 verwendet wird:

In dem allgemeineren Fall lautet die Formel:

Und Sie können Ihre Konstanten holen.

Halt, beachten Sie jedoch, dass quadratisches Sondieren ist sinnvoll, nur in bestimmten Fällen. Als Wikipedia-Eintrag heißt es:

  

Quadratic bietet Sondieren gutes Gedächtnis   Cachen, weil es einige bewahrt   Lokalität der Referenz; jedoch lineare   Sondieren hat eine größere Lokalität und,   somit bessere Cache-Leistung.   Quadratic Sondieren besser vermeidet die   Clustering-Problem, das mit auftreten kann   lineare Sondieren, obwohl dies nicht der Fall   immun.

---

EDIT: Wie viele Dinge in der Informatik, die genauen Konstanten und Polynome quadratischen Sondieren sind Heuristik. Ja, die einfachste Form ist i^2, aber Sie können anderes Polynom wählen. Wikipedia gibt das Beispiel mit h(k,i) = (h(k) + i + i^2)(mod m).

Daher ist es schwierig, Ihre „Warum“ beantwortende Frage. Der einzige „warum“ ist hier warum brauchen Sie quadratische haupt Sondieren? Haben Sie Probleme mit anderen Formen der Sondierung und bekommen eine gruppierte Tabelle? Oder ist es nur eine Hausaufgabe oder Selbstlern?

Beachten Sie, dass bei weitem die häufigste Kollisionsauflösungstechnik für Hash-Tabellen entweder verketten oder lineare Sondieren. Quadratic Sondieren ist ein heuristisches Option für Sonderfälle, und es sei denn, Sie wissen, was Sie sehr gut tun, würde ich nicht empfehlen es zu benutzen.

Answer 2

Es ist eine besonders einfache und elegante Art und Weise Sondierung zu implementieren quadratischen, wenn Ihre Tabellengröße eine Potenz von 2 ist:

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

Statt das Betrachtens Offsets 0, 1, 2, 3, 4 ... aus dem ursprünglichen Index, wird dies bei Offsets aussieht 0, 1, 3, 6, 10 ... (die i ^th Sonde bei Offset (i * (i + 1)) / 2, dh es ist quadratisch).

Dies wird garantiert jede Position in der Hash-Tabelle treffen (so Sie garantiert einen leeren Eimer zu finden, wenn es eine gibt) zur Verfügung gestellt die Tabellengröße ist eine Potenz von 2.

---

Hier ist eine Skizze eines Beweises:

1. eine Tabellengröße von n gegeben, wollen wir zeigen, dass wir n verschiedene Werte erhalten werden (i * (i + 1)) / 2 (mod n) mit i = 0 ... n-1.
2. Wir können dies durch Widerspruch beweisen. Es sei angenommen, dass es weniger als n verschiedene Werte: Wenn dem so ist, muss es mindestens zwei verschiedene ganzzahlige Werte für i im Bereich von [0, n-1], so dass (i * (i + 1)) / 2 (mod n ) ist dasselbe. Rufen Sie diese p und q, wobei p
3. d. (P * (p + 1)) / 2 = (q · (q + 1)) / 2 (mod n)
4. => (p ² + p) / 2 = (q ² + q) / 2 (mod n)
5. => p ² + p = q ² + q (mod 2n)
6. => q ² - p ² + q - p = 0 (mod 2n)
7. faktorisieren => (q - p) (p + q + 1) = 0 (mod 2n)
8. (q - p) = 0 der triviale Fall p = q
.
9. (p + q + 1) = 0 (mod 2n) ist unmöglich: unsere Werte von p und q liegen im Bereich [0, n-1], und q> p, so (p + q + 1) im Bereich sein muss [2, 2n-2].
10. Wie wir Modulo 2n arbeiten, müssen wir auch mit dem schwierigen Fall behandeln, in denen beiden Faktoren sind nicht Null, sondern multiplizieren 0 (mod 2n) zu geben:
    • beachten, dass der Unterschied zwischen den beiden Faktoren (q - p) und (p + q + 1) (2p + 1), die eine ungerade Zahl ist - so ist einer der Faktoren, auch sein muss, und andererseits müssen ungerade.
    • (q - p) (p + q + 1) = 0 (mod 2 n) => (q - p) (p + q + 1) durch 2 n teilbar ist. Wenn n (und somit 2n) ist eine Potenz von 2 , erfordert dies die sogar Faktor ein Vielfaches von 2n zu sein (weil alle die Primfaktoren von 2n sind 2, während keiner der Primfaktoren unser ungeraden Faktor ist).
    • Aber (q - p) einen Maximalwert von n-1 hat, und (p + q + 1) hat einen Maximalwert von 2n-2 (wie in Schritt 9 zu sehen ist), so kann weder ein Vielfaches von 2n .
    • So ist dieser Fall nicht so gut.
11. Deshalb ist die Annahme, dass es weniger als n verschiedene Werte (in Schritt 2) muss falsch sein.

(Wenn die Tabellengröße nicht eine Potenz von 2 ist diese auseinander fällt bei Schritt 10.)