Deepak Vadgama bio photo

Deepak Vadgama

Software developer, amateur photographer

Email Twitter Google+ LinkedIn Github Stackoverflow Youtube Subscribe (RSS)

Introduction

I love ‘Concurrency in Practice’. Its a Java concurrency book written by Brian Goetz, Doug Lea and Joshua Bloch. It is considered a definitive guide on the subject. These fine folks were also involved in JSR166 and have authored many of the concurrency/collection classes in JDK. It is fascinating to walk through their code. There is lot to learn about code structure, performance, trade-offs etc.

Let’s start with HashMap and its cousin LinkedHashMap.

Basics

If you want to understand how HashMaps are typically implemented at basic level, I highly recommend this video explaining Go’s HashMap

In short, HashMap is backed by an array. During put operation, hashcode of key is calculated, and Entry (key+value) is inserted in array (based on hashcode % array’s size). If more keys are added with same hashcode, linkedlist is formed with previously added keys.

Let’s focus on the interesting parts of the class (whole code here: HashMap & LinkedHashMap)

Initialization

  • If the initial capacity and load-factors are not provided, they default to 16 and 0.75 respectively.
  • Closest factor of 2 If initial capacity is given, it is increased to the closest factor of 2 by using this bit twiddling algorithm.
  • Why factor of 2: When table is resized (doubled), the elements in linked list can easily be assigned to new indexes without performing modulo operation. This is awesome! Eg: If hash=9, oldTableSize=8, oldIndex=1 (9%8), newTableSize=16, newIndex=9 (9%16) = oldTableSize + oldIndex
  • Table not initialized yet: Interesting that the array (variable table) is not initialized in constructor. So no memory allocated yet.
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
        
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    

Linked-Lists vs Trees

If there are multiple elements with same hashcode, they are linked to each other forming linked-list (also called as Bins). Starting with Java 8 as part this JEP, if number of elements with same hashcode crosses certain threshold, the list is converted to a balanced Red-Black tree.

Red-Black tree is a sorted tree, in which search takes max log(n) operations. Though, for the sorting to work, all the keys need to be comparable to each other (i.e. they need to implement Comparable interface).

If keys are not comparable then ofcourse it will be a tree with each node with only 1 child. This consumes twice the space is generally twice as slow.

Hashcode

  • Best Case: O(1). Hashcode of all the keys are distinct, then get and put operations run in O(1) i.e. constant time (independent of the number of keys in the map).

  • Worst Case (Bins): O(n). Hashcodes of all keys are same then same operations can take O(n) time (n = number of keys in the map).

  • Worst Case (Trees): O(log(n)). Hashcodes of all keys are same then same operations can take O(log(n)) time (n = number of keys in the map).

Note: Technically hashcode % table-length need to be distinct, because even distinct hashcodes can end up in same bin/tree i.e. collide.

String class: Special hash function and a new private field hash32 (to cache the hashcode) was added to String class in Java 7 to to use more complex hashing to generate unique hashes. This was specifically to improve performance in HashMaps (all variants). After implementing Trees instead of Bins (see section below), the field was removed since now the worst case operations take O(log(n)) instead of O(n).

Probability of list of size k

Unless there are programming mistakes or malicious code, hashcodes generally follow poisson distribution

In layman terms, typical keys inserted in the HashMap have hashcodes which are generally unique. The probability of 2 elements having same hashcode is low, 3 of them having same is even lower, and 8 elements having same hashcode is extremely rare (1 in 10 million).

Thus probability of having to create trees is very low (although, if you use custom class as key, and its hashcode is badly written then its still very much probable).

Code for computing hash

So in addition to the hashcode that we write for our keys, hashcode itself is (bitwise) shifted. This because some values with same lower bits can increase probability of same hashcodes.

   /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

Example of such floats:

binary values of 2.0f, 18.0f and 215.0f all have same lower bits.
 
System.out.println(Long.toBinaryString(Float.floatToRawIntBits(2.0f)));
System.out.println(Long.toBinaryString(Float.floatToRawIntBits(18.0f)));
System.out.println(Long.toBinaryString(Float.floatToRawIntBits(215.0f)));

1000000000000000000000000000000
1000001100100000000000000000000
1000011010101110000000000000000

Put Key-Value

  • Lets skip hash function for now.
  • (n - 1) & hash is same as hash % n, who knew!
  • Code comments inline
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        
        // 1. Create table here by calling resize()
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
        // 2. Find table index based on hash, if that table entry is empty, create new node and add
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            
        // 3. If table entry exists, then need to append (either to linked-list or the tree)
        else {
            Node<K,V> e; K k;
            
            // 4. If first element in the table is same as new element to be added, get the element in e.
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) 
                // 5. Above: Performance: Comparing int hash which is faster, if same then only call equals
                e = p;
                
            // 6. If this list is already converted to tree, add to element to the tree
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
             
            // 7. Else add to the linked list
            else {
                for (int binCount = 0; ; ++binCount) {
                
                    // 8. Traverse the list until the end (one element at a time)
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        
                        // 9. If elements in linked list are more than threshold, convert to tree
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    
                    // 10. If while traversing, any element equals and element-to-add then, get element in e
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            
            // 11. If element already exists
            if (e != null) { 
                V oldValue = e.value;
                
                // 12. Update with new value and return old value.
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        
        // 13. Increase modificationCount and Size
        ++modCount;
        
        // 14. If after adding element, threshold is reached, increase table size. 
        if (++size > threshold)
            resize();
            
        // 15. Callback used for linkedhashmap not this regular hashmap
        afterNodeInsertion(evict);
        
        return null;
    }

Tree

  • A linked list is converted to Red-Black tree only if list’s size exceeds threshold (8) and table size is greater than threshold (64).
  • Code comments inline
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        
        // 1. If table size is less than MIN_TREEIFY_CAPACITY(64), then 
        // instead of creating tree, resize the table. 
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
            
        // 2. Convert linked list to tree
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
            
                // 3. create TreeNode for each element, and link using just prev/next 
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            
            // 4. Convert list of TreeNodes with prev/next to tree
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

    // 5. Method from within TreeNode class.
    final void treeify(Node<K,V>[] tab) {
        TreeNode<K,V> root = null;
        for (TreeNode<K,V> x = this, next; x != null; x = next) {
            next = (TreeNode<K,V>)x.next;
            x.left = x.right = null;
            
            // 6. For root i.e. first element
            if (root == null) {
                x.parent = null;
                x.red = false;
                root = x;
            }
            
            // 7. For all other TreeNodes
            else {
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
                for (TreeNode<K,V> p = root;;) {
                    int dir, ph;
                    K pk = p.key;
                    
                    // 8. Sort to left or right, by comparing hash values
                    // 9. Imp: All elements of this tree have same (hash % table-size) values, but their 
                    // actual hashes are different
                    if ((ph = p.hash) > h)
                        dir = -1;
                    else if (ph < h)
                        dir = 1;
                        
                    // 10. If by chance 2 elements have exact same hash, then break tie using System.identityHashCode
                    else if ((kc == null &&
                              (kc = comparableClassFor(k)) == null) ||
                             (dir = compareComparables(kc, k, pk)) == 0)
                        dir = tieBreakOrder(k, pk);

                    // 11. Traverse TreeNode until appropriate (left/right) null child is found
                    TreeNode<K,V> xp = p;
                    if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    
                        // 12. Attach TreeNode as appropriate (left/right) child
                        x.parent = xp;
                        if (dir <= 0)
                            xp.left = x;
                        else
                            xp.right = x;
                        
                        // 13. Tree can become unbalanced after addition of TreeNode, rebalance
                        // The root can change during balancing, re-assign to root
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
            }
        }
        
        // 14. If during balancing root node changed, then table[hash % size] != root, 
        // fix this by change table's index to root
        moveRootToFront(tab, root);
    }

    // 15. Called when number of elements in tree are less than threshold
    final Node<K,V> untreeify(HashMap<K,V> map) {
        Node<K,V> hd = null, tl = null;
        for (Node<K,V> q = this; q != null; q = q.next) {
            Node<K,V> p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }
    

Get value from key

Not much to see here. Straight forward code.

  • If its a list traverse till the end (if its a tree, traverse the tree).
  • Code comments inline.
    
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        
        // 1. Validate table not null, and hash table entry is not null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            
            // 2. Check first element, for performance,
            // since in most cases, where hashcodes are unique, there will be only 1 element
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            
            // 3. If there are more elements, traverse tree or linked-list accordingly
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }  
   
    final TreeNode<K,V> getTreeNode(int h, Object k) {
        return ((parent != null) ? root() : this).find(h, k, null);
    }
    
    // Method within TreeNode class
    final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
        TreeNode<K,V> p = this;
        do {
            int ph, dir; K pk;
            TreeNode<K,V> pl = p.left, pr = p.right, q;
            
            // 4. If node's hash greater than h, store left child tree in p
            if ((ph = p.hash) > h)
                p = pl;
                
            // 5. If node's hash less than h, store right child tree in p
            else if (ph < h)
                p = pr;
                
            // 6. If node's hash and key match, then return the node
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
                
            // 7. If left child tree is null, then store right child tree in p
            else if (pl == null)
                p = pr;
                
            // 8. If left child tree is null, then store right child tree in p
            else if (pr == null)
                p = pl;
                
            // 9. If keys are comparable, compare and decide left or right child tree
            else if ((kc != null ||
                      (kc = comparableClassFor(k)) != null) &&
                     (dir = compareComparables(kc, k, pk)) != 0)
                p = (dir < 0) ? pl : pr;
                
            // 10. Search recursively in right tree first.
            else if ((q = pr.find(h, k, kc)) != null)
                return q;
                
            // 11. Set p as left child tree, and let while loop recursively search with p
            else
                p = pl;
        } while (p != null);
        return null;
    }
    

Resizing table

  • Used for both resizing and initializing table for first time.
  • Code Comments inline
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;

        if (oldCap > 0) {
            // 1. Validate less than MAX
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            
            // 2. Double capacity and threshold
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 3. Create table 
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
        
            // 4. Loop through old table to reassign all elements
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    
                    // 5. Just assign for single element
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                        
                    // 6. Split the tree in 2 if a TreeNode
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        
                    // 7. Split the linked list
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            
                            // 8. Take advantage of factor of 2 size of table
                            // Either new index of element will be the same, or oldTableSize + oldIndex
                            // Assign to appropriate list
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        
                        // 9. Attach list to appropriate table indexes
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

LinkedHashMap

  • Its Node extends HashMap node and adds before, after Entry references to keep track of insertion order.
  • Note that these new references form a doubly linked list, and is completely unrelated to the HashMap’s list, which keeps track of all elements with same hashcode.
  • Code comments inline
   // 1. Extra references to keep track of insertion order. 
   static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    
    // 2. Adjust doubly linked list once a node is removed
    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }
    
    // 2. Adjust doubly linked list once a node is added
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
    
    // 3. If a node is replaced, move it to the end (its treated as newly added node)
    void afterNodeAccess(Node<K,V> e) { 
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

Skipped

  • Iterators
  • Serialization
  • Red-Black Tree balancing
  • Splitting the Tree
  • EntrySet and Values methods

Conclusion

  • For a core data structure being used billions (probably trillions) of times, its okay to introduce complexity to gain extra performance.
  • There are always trade offs between performance and space overhead.
  • Bitwise operators are performant and powerful.
  • HashMap class has 2734 lines of code (& comments)!
  • Seemingly simple looking operations can involve huge amount of code.

Cake and the cherry

I got the following Twitter reply from Joshua Bloch which just made my day.

Goes to show the power of Twitter in democratizing communication (eg: between rockstar and average programmers) and also that programmer community at large is kind, helpful and generous.

Thanks: Special thanks to my friend Neerav Vadodaria for proof-reading the article.


Tags: