This exists, it's just generally not done because your buckets should be small enough that linear search is fastest. From the wikipedia hash table article (htt

This exists, it's just generally not done because your buckets should be small enough that linear search is fastest. From the wikipedia hash table article (http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_other_structures http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_wi...): Instead of a list, one can use any other data structure that supports the required operations. By using a self-balancing tree, for example, the theoretical worst-case time of a hash table 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 expects to have many entries hashed to the same slot (e.g. if one expects extremely non-uniform or even malicious key distributions).