* TreeBins use a special form of comparison for search and
* related operations (which is the main reason we cannot use
* existing collections such as TreeMaps). TreeBins contain
* Comparable elements, but may contain others, as well as
* elements that are Comparable but not necessarily Comparable<T>
* for the same T, so we cannot invoke compareTo among them. To
* handle this, the tree is ordered primarily by hash value, then
* by getClass().getName() order, and then by Comparator order
* among elements of the same class. On lookup at a node, if
* non-Comparable, both left and right children may need to be
* searched in the case of tied hash values. (This corresponds to
* the full list search that would be necessary if all elements
* were non-Comparable and had tied hashes.)
The implementation is free to use forbidden voodoo powers. In this case it could be whatever it is also using behind the scenes to implement pointer equality for objects.
Using pointer equality is fine, but doesn't help in the case where you have a custom equals() implementation. Maybe the JVM could inspect the implementation of equals() and spot certain patterns (e.g. it's the conjunction of equals() of a set of constituent objects), but doing it in general sounds impossible to me.
For hash tables where the number of buckets is much smaller than the number of hash codes (i.e. all of them) and where hash codes are well distributed and collisions are caused by different hash codes mapping onto the same bucket (not always true, but often), the tree can be implemented by comparing hash codes, with a fallback to handle the case of multiple identical hash codes.
Comments
FWIW in JDK 8 hash map will most likely degrade into a lookup on a red-black tree rather than a linked list for buckets with more than 8 collisions.
Interesting. But wouldn't that require keys to have an ordering (e.g. implement Comparable)?
From the implementation:
The implementation is free to use forbidden voodoo powers. In this case it could be whatever it is also using behind the scenes to implement pointer equality for objects.
Using pointer equality is fine, but doesn't help in the case where you have a custom equals() implementation. Maybe the JVM could inspect the implementation of equals() and spot certain patterns (e.g. it's the conjunction of equals() of a set of constituent objects), but doing it in general sounds impossible to me.
For hash tables where the number of buckets is much smaller than the number of hash codes (i.e. all of them) and where hash codes are well distributed and collisions are caused by different hash codes mapping onto the same bucket (not always true, but often), the tree can be implemented by comparing hash codes, with a fallback to handle the case of multiple identical hash codes.
How do you know this kind of thing? I suppose you have to read OpenJDK source code to figure those things?