CODEWITHSUNDEEP
javahashmapresize
Dale Sun
Dale Sun

Reputation: 31

I have some troubles with HashMap from JDK1.8

Here is a part of code. when node length over 7, it will turn Node to TreeNode, but in function treeifyBin(), if tab length less than 64 it just execute resize().

// binCount is length of Node,  TREEIFY_THRESHOLD is default 8
if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

// tab is Node[],  MIN_TREEIFY_CAPACITY is default 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

I can't understand why node length is relating to resize().

Upvotes: 0

Views: 146

Answers (2)

Saptarshi Basu
Saptarshi Basu

Reputation: 9283

The core objective of creating a HashMap is, you want to retrieve a value in constant time O (1). However, it doesn't remain O(1), when you have a collision. In case of collision, you'd have to search for the key either in a linked list or a tree.

Here you are within the function treeifyBin(). That means you have already encountered collision. But we hate collision. We want to avoid collision by all means. But creating the tree is a lot of work. So, before creating the tree we check if the array (or tab) is still small enough (< MIN_TREEIFY_CAPACITY). If it is, instead of creating the tree we increase the size of the array to avoid collision.

Now let's see how incrasing array size avoids collision. Let's say the initial array size is 16. Now to map the hash code to an array index, you do a bitwise AND (hashCode & (sizeOfArray - 1)). Here, binary of (16-1) is 1111. If the hash code is 17 (binary = 10001), after the bitwise AND, all you get is 0001 i.e. 1. Now, if you resize, your array size would be 32. Therefore (sizeOfArray - 1) = 11111. Now, if you do a bitwise AND with the same hash code 17, you'd get 10001 i.e. 17. So, the element will be moved from tab [1] to tab[17]. If the other key that was earlier colliding, had a hash code of 1 or 33 earlier, it would still go in tab[1].

Upvotes: 0

prasannajoshi
prasannajoshi

Reputation: 157

As you know , from java-8 hashmap's internal working changes as internal linked list reaches to threshold it gets converted into tree (RB Tree to be specific).The logic for converting tree depends on length of nodes in bucket so its worth checking before converting list into tree if the node can be inserted just by resizing the linkedlist instead of converting list into tree which is costly operation. One more thing need to consider here as with frequent removal from map can cause conversion of tree again back to list ,hence inside your treeifybin() method , there is check for resize and then your current structure gets changed to tree.

For more information just check following : http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

Cheers :)

Upvotes: 2

Related Questions