Ciò che chiedi è possibile, dati i tuoi limiti.
Analisi
Il punto di forza di una tabella hash è la sua rapida ricerca e velocità di inserimento. Per ottenere quella velocità, si deve rinunciare a qualsiasi parvenza di ordine nella tabella: le voci sono tutte mescolate. Una lista è accettabile da usare come voce di una tabella perché mentre l'attraversamento è O (n), gli elenchi tendono ad essere brevi supponendo che la tabella hash sia sufficientemente grande e gli oggetti memorizzati nella tabella siano sottoposti a hashing utilizzando un algoritmo di hashing di buona qualità.
Un albero di ricerca binario (BST) ha un rapido inserimento e ricerca su O (log 2 n). Impone anche una restrizione sugli elementi che memorizza: ci deve essere un modo per ordinare gli elementi. Dati due elementi A e B memorizzati nell'albero, deve essere possibile determinare se A viene prima di B o se hanno un ordine equivalente.
Una tabella hash non impone restrizioni di questo tipo: gli elementi in una tabella hash devono avere due proprietà. In primo luogo, ci deve essere un modo per determinare se sono equivalenti; secondo, ci deve essere un modo per calcolare un codice hash deterministico. L'ordine non è un requisito.
Se gli elementi della tabella hash hanno un ordine, è possibile utilizzare un BST come voce della tabella hash per contenere oggetti con lo stesso codice hash (collisioni). Tuttavia, a causa di un BST che ha O (log 2 n) ricerca e inserimento, ciò significa che il caso peggiore per l'intera struttura (tabella hash più BST) è tecnicamente migliore rispetto all'utilizzo di un elenco come voce di tabella . A seconda dell'implementazione di BST, richiederà più spazio di archiviazione di un elenco, ma probabilmente non molto di più.
Si noti che normalmente il sovraccarico e il comportamento di un BST non portano nulla alla tabella nelle situazioni del mondo reale come bucket hash della tabella, motivo per cui la prestazione teorica di una lista è accettabile. In altre parole, la tabella hash compensa la debolezza dell'elenco inserendo meno elementi in ogni elenco (bucket). Tuttavia : il problema indicava esplicitamente che la tabella hash non può aumentare di dimensioni e che le collisioni sono più frequenti di quelle tipiche di una tabella hash.
Attuazione
Non inserirò il codice qui perché sinceramente non è veramente necessario e comunque non hai dato una lingua.
Quello che farei è semplicemente copiare qualsiasi tabella standard di hash contenuta nella libreria standard della tua lingua in una nuova classe, quindi modificare il tipo di bucket di tabella da un elenco a un albero. A seconda della lingua e della sua libreria standard, questa può essere una cosa molto banale da fare.
Normalmente non vorrei difendere la codifica di copia e incolla come questa. Tuttavia, è un modo semplice per ottenere rapidamente molto una struttura di dati testata in battaglia.