Learn the Map set in the Java set from the source code and have an in-depth understanding of it


The last article talked about very common Set set . From the article, we know that Set is an ordered single column Set. Of course, it can solve many problems in life, but the elements in our Set are not all isolated single elements. Some of them will have a certain corresponding relationship (mapping relationship), such as the corresponding relationship between our student number and students in school. Therefore, Java has specially designed the Map interface. The elements of the collection class implemented through this interface are elements with corresponding relationships (mapping relationships). They are also called key value pairs. The corresponding values can be found through the corresponding keys.

Features of Map interface:

  • Elements exist in pairs. They are also called key value pairs (key and value). The corresponding value of the pair can be found through the key; (also known as a two column set)
  • The elements in the set are out of order;
  • The set key in the Map cannot be repeated, but the value can be repeated; Each key can be mapped to at most one value;
  • The value of a set in a Map can be a single value, an array or a set;

Use of Map

Introduction to common methods

Unlike single column sets such as Set, Map, as a double column Set, naturally has many methods, which are different from single column sets. The following describes the methods commonly used in Map:

  • boolean isEmpty(): judge whether the collection is empty, and return true to indicate an empty collection;
  • boolean containsKey(Object key): determines whether the specified key value exists in the collection
  • boolean containsValue(Object value): judge whether the specified value exists in the collection, and return true to indicate the existence of one or more keys of the specified value;
  • V get(Object key): returns the value of the specified key mapping. If the key mapping not included in this Map returns null;
  • V put(K key, V value): add the key and its mapping. If the key already exists, replace it with a new mapping (new value);
  • Void putall (Map <? Extensions K,? Extensions V > m): add a new Map set directly to the Map set;
  • -V remove(Object key): deletes the mapping of the specified key value in the set;
  • void clear(): remove all mappings in the set;
  • Set keySet(): returns a set view of the set of key values in the set;
  • Collection values(): returns a collection view of the total value of the collection;
  • Set<Map. Entry < K, V > > entryset(): returns a set view of the mapping contained in the set;
  • int size(): returns the size of the collection

Traversal of Map collection

Unlike single column collections such as Set, the traversal of Map does not support foreach because it does not inherit Java Lang. Iterable interface, nor does it implement the iterator () method. Therefore, it can only traverse elements in the following ways:

  • Traverse key value and value value separately
  • Through Map The implementation class of entry (Map interface) to traverse the mapping relationship;

Code example

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapDemo {
    public static void main(String[] args) {
        //Create hashmap collection
        Map<String,String> hashMap1 = new HashMap<>();
        Map<String,String> hashMap2 = new HashMap<>();

        //Add element put(K key,V value)
        hashMap1.put("Zhang San","jack");
        hashMap1.put("Li Si","marry");
        hashMap2.put("Wang Wu","lucy");
        hashMap2.put("Zhao Liu","bob");


        //Add element putall (map <? Extensions K,? Extensions V > m)


        //Delete element remove(Object key) remove(Object key, Object value)
        hashMap1.remove("Wang Wu");
        hashMap1.remove("Wang Wu","lucy");


        //Delete element void clear()

        //Element query operation get(Object key)
        String get = hashMap1.get("Zhao Liu");

        //Operation of element query containsKey(Object key)
        boolean containsKey = hashMap1.containsKey("Wang Wu");

        //Operation containsValue(Object value) of element query
        boolean containsValue = hashMap1.containsValue("jack");

        //Operation of element query
        boolean empty = hashMap2.isEmpty();

        //Method keySet() of metaview operation
        Set<String> keySet = hashMap1.keySet();

        //Traversal key
        for(String key : keySet){

        //Methods for metaview operations values()
        Collection<String> values = hashMap1.values();

        //Traversal value
        for(String value : values){

        //Method entrySet() of the metaview operation
        Set<Map.Entry<String, String>> entries = hashMap1.entrySet();

        //Pairwise traversal
        for(Map.Entry<String, String> entry : entries){

        //Collection size()
        int size = hashMap1.size();


Implementation class of Map

Map interface also has many implementation classes, but we will only introduce the commonly used implementation classes, such as HashMap, TreeMap, LinkedHashMap and Properties. They are introduced below.


HashMap is a hash table (hash table). HashMap implements the Map interface, stores data according to the HashCode value of the key, has fast access speed, allows the key of one record to be null at most, and does not support thread synchronization (thread unsafe).

In order to successfully store and retrieve objects in the hash table, the objects used as keys must implement the hashCode method and the equals method

The source code of HashMap is as follows:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ... //Part of the code is omitted
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16, initialization capacity
    static final int MAXIMUM_CAPACITY = 1 << 30;//Maximum capacity
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//Default capacity load
	// When adding elements to make the length of the corresponding linked list reach 8, the linked list is converted into a red black tree
	static final int TREEIFY_THRESHOLD = 8;
	//When the element is deleted so that the length of the corresponding linked list is less than 6, the linked list is converted into a linked list
	static final int UNTREEIFY_THRESHOLD = 6;
	//Minimum tree capacity
	static final int MIN_TREEIFY_CAPACITY = 64;
	//An array of storage elements
	transient Node<K,V>[] table;
	//Cache entrySet()
	transient Set<Map.Entry<K,V>> entrySet;
	//Number of version iterations
	 transient int modCount;
	//Critical value (used to judge whether to expand capacity)
	int threshold;
	//Filling ratio
	final float loadFactor;

		HashMap Capacity expansion mechanism
	final Node<K,V>[] resize() {	
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold; //The length of the old table is the critical value
        int newCap, newThr = 0;
	//If the length of the old table is not empty
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
	//Set the length of the new table to twice the length of the old table, newCap=2*oldCap
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
	      //Set the new table to twice the size of the old table
                newThr = oldThr << 1; // newThr=oldThr*2
     //If the length of the old table is 0, it means that the table is initialized for the first time
        else if (oldThr > 0) // Initial capacity set to threshold
            newCap = oldThr;
        else {               // Zero initial threshold indicates that the default value is used
            newCap = DEFAULT_INITIAL_CAPACITY;
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;//New table length multiplied by load factor
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        threshold = newThr;
	//Then construct a new table and initialize the data in the table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;//Assign new table to table
        if (oldTab != null) {//The original table is not empty. Move the data in the original table to the new table	
            //Traverse the original old table		
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)//This indicates that this node has no linked list and is directly placed in the e.hash & (newcap - 1) position of the new table
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
	//If there is a linked list behind e, it means that there is a single linked list behind E. you need to traverse the single linked list and reset each node
                    else { // preserve order ensures that the new order is calculated in the position of the new table and transported					
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;//Record the next node
			  //The capacity of the new table is twice that of the old table. In the instance, the single linked table is divided into two teams,
              //e. Hash & oldcap is an even team, and e.hash & oldcap is an odd pair
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                    loTail.next = e;
                                loTail = e;
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                    hiTail.next = e;
                                hiTail = e;
                        } while ((e = next) != null);
                        if (loTail != null) {//The lo queue is not null and placed in the original position of the new table
                            loTail.next = null;
                            newTab[j] = loHead;
                        if (hiTail != null) {//hi queue is not null and placed in the position of j+oldCap in the new table
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
        return newTab; //Return to new table

		HashMap Source code of common methods
	//get method
	 public V get(Object key) {
        Node<K,V> e;
        //getNode is called and compared with ternary operator
        return (e = getNode(hash(key), key)) == null ? null : e.value;

	public boolean containsKey(Object key) {
		//getNode called
        return getNode(hash(key), key) != null;
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // Always check the first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            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;
	//put method
	public V put(K key, V value) {
		//putVal method called
        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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    p = e;
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                return oldValue;
        if (++size > threshold)
        return null;
	//remove method
	 public V remove(Object key) {
        Node<K,V> e;
        //The removeNode method was called
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
	 final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                        p = e;
                    } while ((e = e.next) != null);
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                    p.next = node.next;
                return node;
        return null;

	    public void clear() {
        Node<K,V>[] tab;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;

   public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
        return false;

From the above source code, we can see:

  • The default size of the hash table is 16 (that is, the size of the Node array is 16). If the elements in the Node [] array reach the threshold, resize the HashMap to double the original size
  • Then is the source code introduction of some common methods of HashMap


TreeMap is based on red black tree. The map is sorted according to the natural order of its keys, or according to the Comparator provided when creating the map, depending on the construction method used.

Compared with the source code, the sorting of TreeMap deserves our attention. The following is an example of its sorting

import org.junit.Test;
import java.util.Comparator;
import java.util.Map;
import java.util.Set;

public class TreeMap {

    public void test1(){
        //Create collection
        Map<String, Integer> treemap = new java.util.TreeMap<>();

        //Add element
        treemap.put("Jack", 11000);
        treemap.put("Alice", 12000);
        treemap.put("Lucy", 15000);
        treemap.put("bob", 14000);
        treemap.put("Bo", 14000);

        //String implements the Comparable interface. It is sorted by Unicode encoding value by default
        Set<Map.Entry<String, Integer>> entrySet = treemap.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {

    public void test2(){
        //Specifies a custom Comparator that sorts by Unicode encoded values, but ignores case
        Map<String, Integer> treemap = new java.util.TreeMap<>(new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o1.compareToIgnoreCase(o2);

        //Add element
        treemap.put("Jack", 11000);
        treemap.put("Alice", 12000);
        treemap.put("Lucy", 15000);
        treemap.put("bob", 14000);
        treemap.put("Bo", 14000);

        //String implements the Comparable interface and ignores the case sorting of Unicode encoded values
        Set<Map.Entry<String, Integer>> entrySet = treemap.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {



LinkedHashMap is a subclass of HashMap. Unlike HashMap, LinkedHashMap is orderly, which solves the inconvenience caused by the disorder of HashMap. The order is usually the order in which keys are inserted into the map (or access order).

In essence: the combination of HashMap and two-way linked list is LinkedHashMap

Compared with the source code, the element order of LinkedHashMap deserves more attention. Here are some examples of its order:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

public class LinkedMapDemo {
    public static void main(String[] args) {
        //Create hashmap collection
        Map<String,String> linkedHashMap = new LinkedHashMap<>();

        //Add element
        linkedHashMap.put("Zhang San","jack");
        linkedHashMap.put("Li Si","marry");

        //If the key is the same, the new value will overwrite the original value
        //Because String overrides hashCode and equals methods
        linkedHashMap.put("Li Si","marry11");

        //HashMap supports null values for key and value
        linkedHashMap.put("Wang Wu",null);
        linkedHashMap.put(null, "lucy");

        //Output results
        Set<Map.Entry<String, String>> entries = linkedHashMap.entrySet();
        for (Map.Entry<String,String> entry : entries){


The properties class is a subclass of Hashtable. Properties can be saved in or loaded from the stream. Each key and its corresponding value in the attribute list is a string. This class is mainly used to read Java configuration files. Different programming languages have their own supported configuration files. Many variables in the configuration file are often changed. In order to facilitate the user's configuration, the user can modify the relevant variable settings without the program itself. Just like in Java, its configuration file is often The properties file is used to configure parameters in the form of key value pairs.

Keywords: Java Back-end

Added by DESIGNGRAPHY on Sun, 13 Feb 2022 01:09:20 +0200