Esiste una struttura dati standard conosciuta che è una tabella hash che risolve le collisioni utilizzando un albero binario? Se sì, qual è il nome di questa struttura di dati? Immagino che una tale struttura sarebbe utile in quanto dovrebbe ridurre il tempo di ricerca del caso peggiore a O (log (n)) rispetto a O (n) in una tabella hash, e il caso migliore sarebbe ancora O (1).
Sì, ma non esiste un nome standard più breve di quello che hai già scritto.
Wikipedia dice:
[...] by using a self-balancing tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g. in a real-time application), or if one must guard against many entries hashed to the same slot [...]
e questo è praticamente il motivo per cui.
Knuth ha trovato il nome "tabella hash ordinata" per questa strategia di collisione con benna, che può utilizzare una qualsiasi delle numerose strutture di dati di ricerca del registro n. La maggior parte delle persone non ne è al corrente e in pratica ho visto solo KyotoDB usarlo. Molti altri sono passati da semplici elenchi concatenati per aprire schemi di indirizzamento (doppio hashing, cuculo, Robin Hood) per prestazioni di cache migliori.
"Tabella hash ordinata", O Amble, D Knuth 1973 link
Puoi usare un albero bilanciato, un trie, o semplicemente un array ordinato semplice con ricerca binaria, poiché la dimensione del bucket sarà in gran parte < 8. Si tratta principalmente di un problema di cache, quindi non vorrai usare molti puntatori per un albero.
Leggi altre domande sui tag hashing binary-tree