Warum verringert die zunehmende Größe der Hashtabelle die Anzahl der Kollisionen?

Question

Von dem, was ich online gelesen haben, gibt es zwei Möglichkeiten, um die Anzahl der Kollisionen abnehmend:

1. Verwenden Sie eine bessere Hash-Funktion
2. die Größe der Hash-Tabelle erhöhen

ich das verstehen kann, erster Grund, aber ich kann mich nicht um den zweiten Kopf kümmern.

Wenn sagen wir, ich habe 5 Schlüssel alle, deren Hashes gleich sind. Sagen wir, wir verwenden Verkettung für Kollisionsauflösung. Alle 5 Schlüssel bilden eine Kette beginnend mit dem Index, der dem Hash-Wert entspricht. Jetzt, sagen wir, verdopple ich die Größe der Tabelle und rehash alle 5 Schlüssel. Die 5 Schlüssel werden immer noch Hash auf den gleichen Index und wird noch eine Größenänderung 5. Wie hat die Erhöhung der Größe der Hash-Tabelle Kollisionen verringern?

Answer 1

Dies ist, weil bei der Berechnung von Hash es auch die Berücksichtigung der Array-Größe. Wenn man also Hash berechnet, wenn die Array-Größe groß ist, braucht es einen größeren Modulo-Wert.

Eg:
nehme an, wenn Feldgrße 3 und übergeben Werte sind 2 und 5
dann 2% 3% 3 und 5 nehmen gleichen Stelle dh 1.

Nun Beispiel Feldgrße 5
dann 2% nehmen 5 und 5% 5 nehmen einen anderen Platz ein, dh 2 bzw. 0.

Mit der Zunahme der Hash-Tabelle Größe, Anzahl der Kollision sinkt.
Ich hoffe, diese Erklärung hilft Ihnen.

Answer 2

Ich fand heraus.

Das Hashing besteht aus zwei Teilen: Hash-Funktion und Komprimierungsfunktion. Durch Ändern der Größe der Hash-Tabelle wird die Komprimierungsfunktion geändert, was dazu führt, dass die Schlüssel verschiedenen Buckets zugewiesen werden.