Hash-Tabelle lineare Probing-Datenstruktur

Question

Warum kann bei Verwendung von linearem Antasten für eine Hash-Tabelle kein Lastfaktor-Schwellenwert von 1,1 ausgewählt werden? Soll das für alle Zahlen funktionieren?

Answer 1

Ich bin mir nicht sicher, warum ich das vergessen habe, aber danke an izaak_pyzaak für die Erinnerung.

Wenn Sie lineares Sondieren verwenden, mache ich die Annahme, dass Sie nicht verketten Ihre Hash-Tabelle.

Wie Arunmu darauf hinweist, werden nicht verkettete Hashtabellen überlaufen, wenn der Ladegrenzwert größer als 1 ist. Dies wird zumindest die Hashtabelle beschädigen und wahrscheinlich zum Absturz des Programms führen.

In den meisten Fällen werden Hash-Tabellen mit einem maximalen Auslastungsfaktor von 0,75 implementiert, da eine Auslastung von mehr als 0,75 zu einem Leistungseinbruch wird und die Anzahl der Kollisionen in der Tabelle exponentiell ansteigt. In der Regel sollten die meisten Tabellen 2-3 Mal größer sein als die beabsichtigte Menge an Datensätzen, um Kollisionen zu reduzieren.

Ein Ladefaktor von 1 würde bedeuten, dass die Hash-Tabelle bei der Größenänderung vollständig gefüllt ist. und bevor es die Größe änderte, würde es eine Verringerung der Geschwindigkeit beim Hashing/Suchen auf dem Tisch verursachen. Ein Ladefaktor von 1,1 auf einer entfetteten Hash-Tabelle wäre ein großes Problem, wie bereits erwähnt.

Answer 2

Ich kann die Frage nicht teilweise werden verstehen, (oder überhaupt nicht.), Aber ...

Es ist, weil Sie nicht 1.1 Elemente haben können. Sie haben entweder 1 oder 0 (oder 2, 3, 4 ... n) Elemente. Auch hier können Sie keine 5.5 Elemente haben; Du kannst 5 oder 6 haben, aber nicht dazwischen. Wenn Sie Ihren Schwellenwert nach 1 Elementen erhöhen möchten, stellen Sie einfach den Schwellenwert 1 ein.