Some hash tables promote updated entries to the front of the chain for faster access next time. It occurs to me that a good old splay tree would do that.

The thing is, you're not supposed to have buckets so large that you need a fancy data structure. If the table is not resizeable, it might not be avoidable.