Warum verwendet „std::unordered_map' Open Hashing?

Implementierung von std::unordered_map

Durch die Analyse des C-Standards wird deutlich, dass die Implementierung von std::unordered_map verwenden muss eine Methode, die als offenes Hashing oder auch als separate Verkettung bekannt ist. Diese Methode besteht aus einem Array von Buckets, von denen jeder den Kopf einer verknüpften Liste enthält, was eine effiziente Iteration ermöglicht, ohne leere Buckets zu umgehen.

Die Wahl des offenen Hashings wurde absichtlich getroffen, um spezifische Leistungsanforderungen zu erfüllen, die in C dargelegt sind Standard. Erstens ist der standardmäßige maximale Auslastungsfaktor auf 1,0 eingestellt, was bedeutet, dass die Größe der Tabelle immer dann geändert wird, wenn die Größe die Bucket-Anzahl um den Faktor 1,0 übersteigt. Zweitens wird garantiert, dass die Tabelle nicht erneut aufbereitet wird, es sei denn, sie wird über diesen Auslastungsfaktor hinaus vergrößert. Diese Anforderungen machen offenes Hashing erforderlich, da geschlossenes Hashing unpraktisch wird, wenn sich der Lastfaktor aufgrund übermäßiger Kollisionen 1 nähert.

Während einige argumentieren, dass offenes Hashing nicht die effizienteste Methode für alle Anwendungsfälle ist, bleibt es eine vernünftige Wahl Für den allgemeinen Gebrauch aufgrund der zuverlässigen Handhabung von Kollisionen, der Anpassungsfähigkeit an Schlüssel-/Werttypen unterschiedlicher Größe und der allgemeinen Effizienz bei der Verarbeitung großer Mengen von Einfügungen und Löschungen ohne Leistung Verschlechterung.

Daher nutzt std::unordered_map offenes Hashing, um die angegebenen Leistungsanforderungen zu erfüllen, und bleibt aufgrund seiner Vielseitigkeit und Effizienz eine robuste Wahl für die meisten Anwendungen.

Das obige ist der detaillierte Inhalt vonWarum verwendet „std::unordered_map' Open Hashing?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!