In order to improve the performance of hash tables, why not have the buckets be something like a red-black tree instead of a linked list? (You might improve the efficiency a little by spending a bit and saying "This bucket contains a single element and here it is", or "This bucket contains multiple elements and here is the root of the red-black tree".) Then, you would get log-time search instead of linear-time search when buckets start to fill up with multiple elements.
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).
