Deeply understand the difference between HashMap and treemap

brief introduction

HashMap and treemap are two classes commonly used in the map family. What are the differences between the two classes in use and essence? This paper will make an in-depth discussion from these two aspects, hoping to reveal its essence.

The essential difference between HashMap and treemap

Let's first look at the definition of HashMap:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>,Cloneable,Serializable

Look at the definition of treemap:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,java.io.Serializable

From the definition of classes, HashMap and treemap inherit from abstractmap. The difference is that HashMap implements the map interface, while treemap implements the navigablemap interface. Navigablemap is a SortedMap, which implements the sorting of keys in the map.

In this way, the first difference between the two comes out. Treemap is sorted and HashMap is not.

Let's look at the difference between the constructors of HashMap and treemap.

public HashMap(int initialCapacity,float loadFactor) 

In addition to the default parameterless constructor, HashMap can also accept two parameters, initialCapacity and LoadFactor.

The underlying structure of HashMap is an array of nodes:

transient Node<K,V>[] table

InitialCapacity is the initial capacity of the table. If you do not pass initialCapacity, HashMap provides a default value:

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

When there is too much data stored in the HashMap, the table array will be full. At this time, the capacity needs to be expanded. The capacity of the HashMap is expanded in a multiple of 2. The LoadFactor specifies when capacity expansion is required. The default LoadFactor is 0.75.

static final float DEFAULT_LOAD_FACTOR = 0.75f;

Let's look at some very interesting variables:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

What's the use of the above three variables? Before Java 8, HashMap used the form of linked list to solve hashcode conflict. In order to improve efficiency, Java 8 transformed it into treenode. When will this conversion be sent?

At this time, we need to look at the two variables treeify_ Threshold and untreeify_ THRESHOLD。

Some students may have found treeify_ Why is threshold better than untreeify_ What about threshold 2? In fact, I don't know this problem, but if you look at the source code, untreeify is used_ When threshold is used, it is < =, but treeify is used_ When threshold is used, it is > = tree_ Threshold - 1, so the two variables are essentially the same.

MIN_ TREEIFY_ Capacity means that if table converts the minimum capacity of treenode, only capacity > = min_ TREEIFY_ The conversion of treenode is allowed only when the capability is.

The difference between treemap and HashMap is that the bottom layer of treemap is an entry:

private transient Entry<K,V> root

His implementation is a red black tree, which is convenient for traversal and search.

The constructor of treemap can be passed into a comparator to implement custom comparison methods.

public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

If no custom comparison method is provided, the natural order of key is used.

Sort difference

After we have finished talking about the essence of the two, let's take an example to see the difference between the two:

    @Test
    public void withOrder(){
        Map<String,String> books = new HashMap<>();
        books.put("bob","books");
        books.put("c","concurrent");
        books.put("a","a lock");
        log.info("{}",books);
    }

    @Test
    public void withOrder(){
        Map<String,String> books = new TreeMap<>();
        books.put("bob",books);
    }

In the same code, one uses HashMap and the other uses treemap. We will find that the output results of treemap are in good order, while the output results of HashMap are uncertain.

Difference between null values

HashMap can allow one null key and multiple null values. Treemap does not allow null keys, but multiple null values can be allowed.

    @Test
    public void withNull() {
        Map<String,String> hashmap = new HashMap<>();
        hashmap.put(null,null);
        log.info("{}",hashmap);
    }

    @Test
    public void withNull() {
        Map<String,String> hashmap = new TreeMap<>();
        hashmap.put(null,hashmap);
    }

HashMap will report: NullPointerException.

Performance difference

The bottom layer of HashMap is array, so HashMap will be very fast in adding, finding, deleting and other methods. The bottom layer of treemap is a tree structure, so the speed will be relatively slow.

In addition, HashMap will cause a waste of space because it needs to save an array, while treemap only saves the nodes to be maintained, so it occupies a small space.

In case of hash conflict in HashMap, the efficiency will become worse. However, after the treenode conversion in Java 8, the efficiency has been greatly improved.

Treemap will reorder when adding and deleting nodes, which will affect the performance.

common ground

Neither of them allows duplicate keys, and neither of them is thread safe.

Examples of this article https://github.com/ddean2009/learn-java-collections