If you want a compromise that takes little space like hash tables, has average time complexity of O(log(N)) like balanced trees, and is as simple to implement as hash tables, take a look at skip lists.