title: How does Java 8's HashMap degenerate to balanced trees when many keys have the same hash code?
body: <p>How does Java 8's HashMap degenerate to balanced trees when many keys have the same hash code?  I read that keys should implement <code>Comparable</code> to define an ordering.  How does HashMap combine hashing and natural ordering to implement the trees?  What about classes that do not implement <code>Comparable</code>, or when multiple, non-mutually-comparable <code>Comparable</code> implementations are keys in the same map?</p>