The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?
You could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions.
This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.
