Learn more about the differences between HashMap and TreeMap

Introduction to the

HashMap and TreeMap are two very common classes in the Map family. What is the difference in usage and nature between the two classes? This article will carry on the in-depth discussion from these two aspects, hoping to reveal its essence.

HashMap and TreeMap are fundamentally different

Let’s look at the definition of HashMap:

public class HashMap<K.V> extends AbstractMap<K.V>
    implements Map<K.V>, Cloneable.Serializable
Copy the code

Now look at the definition of TreeMap:

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

AbstractMap and TreeMap both inherit from AbstractMap in terms of class definitions, but HashMap implements the Map interface while TreeMap implements the NavigableMap interface. NavigableMap is a SortedMap that sorts keys in a Map.

This brings up the first difference between the two. TreeMap is sorted and HashMap is not.

Look again at the differences between the constructors of HashMap and TreeMap.

public HashMap(int initialCapacity, float loadFactor) 
Copy the code

HashMap can accept two parameters initialCapacity and loadFactor in addition to the default no-parameter constructor.

The underlying structure of a HashMap is an array of nodes:

transient Node<K,V>[] table
Copy the code

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

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

When too much data is stored in the HashMap, the table array is filled up and the HashMap needs to be expanded by multiples of 2. LoadFactor specifies when an expansion operation is required. The default loadFactor is 0.75.

static final float DEFAULT_LOAD_FACTOR = 0.75 f;
Copy the code

Let’s look at a couple of very interesting variables:

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
Copy the code

What is the use of these three variables? Before Java 8, HashMap resolved hashCode conflicts in the form of linked lists, which Java 8 converted into TreeNode for efficiency. When will the transformation be sent?

Look at the two variables TREEIFY_THRESHOLD and UNTREEIFY_THRESHOLD.

Some of you may have noticed, why is TREEIFY_THRESHOLD 2 larger than UNTREEIFY_THRESHOLD? I don’t know about this, but if you look at the source code, UNTREEIFY_THRESHOLD is always <=, and TREEIFY_THRESHOLD is always >= treeify_threshold-1. So these two variables are essentially the same.

MIN_TREEIFY_CAPACITY specifies the minimum TreeNode capacity that can be converted from table. The TreeNode can be converted only when capacity >= MIN_TREEIFY_CAPACITY.

TreeMap differs from a HashMap in that the underlying TreeMap is an Entry:

private transient Entry<K,V> root
Copy the code

His implementation is a red-black tree, which is easy to traverse and search.

The TreeMap constructor can pass in a Comparator to implement a custom comparison method.

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

If no custom comparison method is provided, the Natural Order of the key is used.

Sort the difference between

Now that we’re done with the nature of the two, let’s take a look at the differences in ordering:

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

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

The same code, one using HashMap and one using TreeMap, shows that TreeMap output is sorted, while HashMap output is variable.

Null value difference

A HashMap can allow one NULL key and multiple NULL values. TreeMap does not allow null keys, but allows multiple NULL values.

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

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

HashMap will say NullPointerException.

The performance difference between

At the bottom of a HashMap is an Array, so a HashMap can be very fast in adding, finding, deleting, and so on. The underlying structure of TreeMap is a Tree structure, so the speed is slow.

In addition, since HashMap stores an Array, it wastes space, while TreeMap stores only the nodes to be held, so it takes up less space.

Hashmaps are less efficient if hash conflicts occur, but with Java 8’s TreeNode conversion, there is a big increase in efficiency.

TreeMap resorts nodes when they are added or deleted, which affects performance.

In common

Neither allows duplicate keys, and neither is thread-safe.

Examples of this article github.com/ddean2009/l…

Welcome to pay attention to my public number: procedures those things, more wonderful waiting for you! For more, visit www.flydean.com