It is well-known that the worst case performance for a chaining hashtable, is O(n), where n is the number of objects in the table. The normal assumption is that the hash is either uniform, or secure, however this is not always the case.
One possible solution to this problem would be to use a tree, or other O($\log n$) data structure, instead of the list. This would result in the worst-case performance of O($\log n$) for insertion and retrieval, at the expense of adding an extra constraint on the import data, namely that it would need to be comparable.
Is there a name for such a data structure?