Was ist primäres und sekundäres Clustering in Hash?

Question

Ich bin verwirrt für die letzten paar Tage in der Suche nach dem Unterschied zwischen primären und sekundären Clustering in Hash Collision Management Thema in dem Lehrbuch, das ich gerade lese.

Answer 1

Primäres Clustering bedeutet, dass die Clustergröße zunimmt, wenn ein Cluster vorhanden ist und die Anfangsposition eines neuen Datensatzes irgendwo im Cluster liegt. Lineares Sondieren führt zu dieser Art von Clusterbildung.

Sekundäres Clustering ist weniger schwer, zwei Datensätze haben nur die gleiche Kollisionskette, wenn ihre Anfangsposition gleich ist. Zum Beispiel führt quadratisches Sondieren zu dieser Art von Clusterbildung.

Answer 2

ich Forschung auf diesem tat, und möchte einige Anmerkungen teilen:

1. Primary Clustering ist die Tendenz für eine Kollisionsauflösung Schema wie lineare Longruns von gefüllten Schlitze in der Nähe zu schaffen Sondierung die Hash-Position von Schlüsseln.
2. Wenn der primäre Hash-Index x ist, gehen nachfolgende Sonden x+1, x+2, x+3 und so weiter, dies führt zu einem primären Clustering.
3. Sobald der primäre Cluster bildet, wird der Cluster umso größer, je größer der schneller wird. Und es reduziert die Leistung.

---

1. Secondary Clustering ist die Tendenz für eine Kollisionsauflösung Schema wie quadratische lange Läufe von gefüllten Schlitze entfernt aus der Hash-Position von Tasten zu schaffen Sondierung.
2. Wenn der primäre Hash-Index x ist, Sonden gehen zu x+1, x+4, x+9, x+16,x+25 und so weiter, diese Ergebnisse in Secondary Clustering.
3. Sekundäres Clustering ist in Bezug auf Leistungseinbußen weniger schwerwiegend als primäres Clustering und ist ein Versuch, die Bildung von Clustern mithilfe von Quadratic Probing zu verhindern. Die Idee ist es, weiter getrennte Zellen zu untersuchen, anstatt diese neben der primären Hash-Site.