Se dovessi scegliere tra una tabella di hash e un albero binario di ricerca, se fossi in te implementerei, per questo caso, un buon BST basato su alberi 2-3-4 magari attraverso l'implementazione di un red-black.