Verknüpfte Listen oder Hash-Tabellen?

Question

Ich habe eine verknüpfte Liste von etwa 5000 Einträgen ("NOT" gleichzeitig eingefügt), und ich bin die Liste durchlaufen, auf der Suche nach einem bestimmten Eintrag bei Gelegenheiten (obwohl dies nicht sehr oft), sollte ich Hash-Tabelle als eine optimale Wahl für diesen Fall, anstelle der verknüpften Liste (die doppelt verknüpft ist & linear) ? Verwendung von C in Linux.

Answer 1

Wenn Sie nur die Auflistung durchlaufen, sehe ich keine Vorteile der Verwendung eines Hashmaps.

Answer 2

Von Hashes rate ich in fast allen Fällen ab.

Dafür gibt es zwei Gründe: Erstens ist die Größe des Hashs festgelegt.

Zweitens und viel wichtiger: der Hashing-Algorithmus. Woher weiß man, dass er richtig ist? Wie verhält er sich bei echten Daten und nicht bei Testdaten?

Ich schlage einen ausgewogenen B-Baum vor. Immer O(log n), keine Unsicherheit in Bezug auf einen Hash-Algorithmus und keine Größenbeschränkungen.