Menu
As of Java8, our beloved HashMap behaves a little different.
If the key implements a comparable interface, each hash would contain a balanced tree instead of a linked-list.
This reduces the worst-time complexity in case of collisions from O(n) to O(log(n)), see JEP180
Is there a situation in which upgrading from Java7 to Java8 would cause a degradation of performance of the HashMap as a result ?
492
In HashMap, hashCode() is used to calculate the bucket and therefore calculate the index. equals() method: This method is used to check whether 2 objects are equal or not. This method is provided by the Object class. You can override this in your class to provide your implementation.
since HashMap uses hashCode to calculate which bucket to use in the hashtable if you return 1 from hashCode you effectively make your HashMap 's performance be like an (unsorted) LinkedList 's performance. Returning random values will simply blow your HashMap up since equal objects will no longer have equal hashCode s.
Hashmap uses the array of Nodes(named as table), where Node has fields like the key, value (and much more). Here the Node is represented by class HashMapEntry. Basically, HashMap has an array where the key-value data is stored. It calculates the index in the array where the Node can be placed and it is placed there.
Java8 will use balanced tree in number of entries in the bucket in > N, where N is chosen empirically, and use list once again if that number is < K. I'd expect worse performance if number of entries in bucket changes in way that "treefyng / untreeifying" happens often. That might happen due to specific hash function.
Also I'm not sure if overhead for creating and querying tree is worth the profit for small N.
148
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
