Set detailed map + interview questions

Set detailed explanation Map + Interview questions

The collection has two big interfaces ：Collection and Map, This article focuses on another common set type in sets Map.

Here are Map The inheritance diagram of ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-gie5PyWl-1657027809501)(https://images.gitbook.cn/e9786a20-e691-11e9-80c2-21d8cc9d922e)]

Map brief introduction

Map The commonly used implementation classes are as follows ：

• Hashtable：Java A hash table implementation provided earlier , It's thread safe , I won't support it null Key and value , Because its performance is not as good as ConcurrentHashMap, So it's rarely recommended .
• HashMap： The most commonly used hash table implementation , If there is no need for multithreading in the program ,HashMap Is a good choice , Support null Key and value , If available in multithreading ConcurrentHashMap replace .
• TreeMap： Based on a red black tree to provide sequential access to Map, Self actualization key Natural ordering , You can also specify Comparator From defining sort .
• LinkedHashMap：HashMap A subclass of , Saved the insertion order of records , It can be traversed in the same order as the insert .

Map Common methods

Common methods include ：put、remove、get、size etc. , All methods are as follows ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-QNXeN6Ee-1657027809502)(https://images.gitbook.cn/319c8410-ccc7-11e9-93b3-c35630e1847c)]

Examples of use , Please refer to the following code ：

Map hashMap = new HashMap();
//  Add elements 
hashMap.put("name", " Lao Wang ");
hashMap.put("age", "30");
hashMap.put("sex", " Have a guess ");
//  Remove elements 
hashMap.remove("age");
//  Find individual elements 
System.out.println(hashMap.get("age"));
//  Cycle all  key
for (Object k : hashMap.keySet()) {
    System.out.println(k);
}
//  Cycle all values 
for (Object v : hashMap.values()) {
    System.out.println(v);
}

The above is HashMap Use example of , The use of other classes is similar .

HashMap data structure

HashMap The underlying data is that arrays are called hashbuckets , Each bucket is a chain table , Every node in the list , Namely HashMap Every element in . stay JDK 8 When the chain length is greater than or equal to 8 when , It will turn into the data structure of the red black tree , To improve the efficiency of query and insert .

HashMap data structure , Here's the picture ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-Sy3fuTqw-1657027809502)(https://images.gitbook.cn/54a52ca0-ccc7-11e9-b229-e35eb1d6e740)]

HashMap Important method

1） Add method ：put(Object key, Object value)

The execution process is as follows ：

• Yes key Conduct hash operation , Compute storage index;
• Determine whether there is hash collision , If there is no collision, put it directly in the hash bucket , If there is a collision, it will be stored in the form of a linked list ;
• Determine the type of existing elements , Decide whether to add a tree or a list , When the list is greater than or equal to 8 when , Turn the list into a red black tree ;
• Replace the old value if the node already exists ;
• Judge whether the threshold value is exceeded , If it's over, we need to expand the capacity .

Source code and description ：

public V put(K key, V value) {
    
    //  Yes  key  Conduct  hash()
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    
    int h;
  //  Yes  key  Conduct  hash()  The concrete realization of 
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab If it is empty, create 
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //  Calculation  index, Also on  null  Do the processing 
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
    
        Node<K,V> e; K k;
        //  Nodes exist 
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //  The chain is a tree 
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //  The chain is a list 
        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);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //  write in 
        if (e != null) {
     // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //  exceed load factor*current capacity,resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put() The execution flow chart is as follows ：

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-KB3kpJlA-1657027809503)(https://images.gitbook.cn/727836f0-ccc7-11e9-a9bd-857608719494)]

2） Access method ：get(Object key)

The execution process is as follows ：

• First, compare the first node , If the hash Values and key Of hash Same value , And the key object of the first node and key identical （ Same address or equals equal ）, Then return the node ;
• If the first node comparison is not the same 、 Let's see if the next node exists , If it exists , We can continue to compare , If it doesn't exist, it means key There is no matching key value pair .

Source code and description ：

public V get(Object key) {
    
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/** *  The method is  Map.get  The concrete implementation of the method  *  Receive two parameters  * @param hash key  Of  hash  value , according to  hash  Values are addressed in the node array , The  hash  Value is passed  hash(key)  Got  * @param key key  object , When it exists  hash  collision , Compare one by one to see if they are equal  * @return  If it is found, it will return the key value to the node object , Otherwise return to  null */
final Node<K,V> getNode(int hash, Object key) {
    
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //  Declare the node array object 、 The first node object of the list 、 Loop through the current node object 、 The length of the array 、 The key object of the node 
    //  Node array assignment 、 Array length assignment 、 The first node of the linked list is determined by the result of module calculation through bit operation 
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
    
        if (first.hash == hash && //  First, compare the first node , If the  hash  Values and  key  Of  hash  Same value , And the key object of the first node and  key  identical （ Same address or  equals  equal ）, Then return the node 
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first; //  Return to the first node 

        //  If the first node comparison is not the same 、 Let's see if the next node exists , If it exists , We can continue to compare , If it doesn't exist, it means  key  There is no matching key value pair  
        if ((e = first.next) != null) {
    
            //  If there is a next node  e, Let's see if the first node is a tree node 
            if (first instanceof TreeNode)
                //  If the first node is a tree node , So go through the tree to find 
                return ((TreeNode<K,V>)first).getTreeNode(hash, key); 

            //  If the first node is not a tree node , It means it's still a common linked list , Then one by one traversal comparison can be  
            do {
    
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) //  When comparing, we should first look at  hash  Is the value the same 、 Look at the address or  equals
                    return e; //  If the current node e Key objects and key identical , Then the return  e
            } while ((e = e.next) != null); //  See if there is another node , If there is , Go on to the next round of comparison , Otherwise jump out of the loop 
        }
    }
    return null; //  The tree nodes that should be compared after the comparison   Or all the linked list nodes   They didn't match  key, So return  null

Relevant interview questions

1.Map What are the common implementation classes ？

answer ：Map The common implementation classes of are as follows ：

• Hashtable：Java A hash table implementation provided earlier , It's thread safe , I won't support it null Key and value , Because its performance is not as good as ConcurrentHashMap, So it's rarely recommended ;
• HashMap： The most commonly used hash table implementation , If there is no need for multithreading in the program ,HashMap Is a good choice , Support null Key and value , If available in multithreading ConcurrentHashMap replace ;
• TreeMap： Based on a red black tree to provide sequential access to Map, Self actualization key Natural ordering , You can also specify Comparator From defining sort ;
• LinkedHashMap：HashMap A subclass of , Saved the insertion order of records , It can be traversed in the same order as the insert .

2. Use HashMap What may be the problem ？ How to avoid ？

answer ：HashMap In a concurrent scenario, there may be a problem of a dead cycle , This is because HashMap In the process of capacity expansion, the list will be processed in reverse order , Suppose two threads perform the expansion operation at the same time , The first thread is executing B→A When , The second thread executes again A→B , This is the time when B→A→B The problem of , Create a dead cycle .
solution ： upgrade JDK edition , stay JDK 8 After that, the capacity expansion will not be reversed , So the problem of the dead cycle has been greatly improved , But this is not the ultimate solution , because HashMap It's not used in the multithreaded version , If multithreading is available ConcurrentHashMap replace HashMap.

3. The following statement is correct ？

A：Hashtable and HashMap It's all non thread safe
B：ConcurrentHashMap allow null As key
C：HashMap allow null As key
D：Hashtable allow null As key
answer ：C
title ：Hashtable It's thread safe ,ConcurrentHashMap and Hashtable It's not allowed null As keys and values .

4.TreeMap How to realize the basis value Reverse order of values ？

answer ： Use Collections.sort(list, new Comparator<Map.Entry<String, String>>() Custom comparator implementation , The first TreeMap Convert to ArrayList, In the use of Collections.sort() according to value In reverse order , The complete implementation code is as follows .

TreeMap<String, String> treeMap = new TreeMap();
treeMap.put("dog", "dog");
treeMap.put("camel", "camel");
treeMap.put("cat", "cat");
treeMap.put("ant", "ant");
// map.entrySet()  Turn into  List
List<Map.Entry<String, String>> list = new ArrayList<>(treeMap.entrySet());
//  Compare and sort by comparator 
Collections.sort(list, new Comparator<Map.Entry<String, String>>() {
  public int compare(Map.Entry<String, String> m1, Map.Entry<String, String> m2) {
    return m2.getValue().compareTo(m1.getValue());
  }
});
//  Print the results 
for (Map.Entry<String, String> item : list) {
  System.out.println(item.getKey() + ":" + item.getValue());
}

Program execution result ：

dog:dog
cat:cat
camel:camel
ant:ant

5. Which of the following Set Automatic sorting is realized ？

A：LinedHashSet
B：HashSet
C：TreeSet
D：AbstractSet

answer ：C

6. What is the result of running the following program ？

Hashtable hashtable = new Hashtable();
hashtable.put("table", null);
System.out.println(hashtable.get("table"));

answer ： Program execution error ：java.lang.NullPointerException.Hashtable Don't allow null Key and value .

7.HashMap What are the important parameters ？ What are the uses of each ？

answer ：HashMap There are two important parameters ： Capacity （Capacity） And load factor （LoadFactor）.

• Capacity （Capacity）： Refer to HashMap The number of barrels in , The default initial value is 16.
• Load factor （LoadFactor）： Also known as load factor ,LoadFactor It's used to judge HashMap Basis for capacity expansion , The default value is 0.75f, Calculation formula of loading factor = HashMap Deposited KV The sum of the （size）/ Capacity.

8.HashMap and Hashtable What's the difference? ？

answer ：HashMap and Hashtable The difference between the following ：

• Hashtable Used synchronized Keyword to ensure thread safety , and HashMap It's not thread safe ;
• HashMap allow K/V All for null, and Hashtable K/V Not allowed null;
• HashMap Inherited from AbstractMap class ; and Hashtable Inherited from Dictionary class .

9. What is hash conflict ？

answer ： When two different values are entered , The phenomenon of calculating the same hash value according to the same hash function , We call it collision （ Hash collision ）.

10. What are the ways to resolve hash conflicts ？

answer ： The common solutions to hash conflicts are as follows 4 Kind of .

• Open addressing ： When the key hash address p=H（key） When there is a conflict , With p Based on , Generates another hash address p1, If p1 Still conflict , And then to p Based on , Generates another hash address p2, Loop through this process until you find a non conflicting hash address , Store the corresponding element in it .
• Then the hash method ： This method is to construct several different hash functions at the same time , When hash address Hi=RH1（key） In conflict , Calculate again Hi=RH2（key）, Loop through this process until you find a non conflicting hash address , The only disadvantage of this method is that it increases the calculation time .
• Chain address ： The basic idea of this method is to set all hash addresses to i The elements of constitute a single chain table called a synonym chain , And store the header pointer of the single chain table in the first... Of the hash table i In units , So find 、 Inserts and deletes are mainly performed in the synonym chain . The chain address method is suitable for frequent insertions and deletions .
• Establish a common overflow area ： The hash table is divided into two parts: basic table and overflow table , Any element that conflicts with the base table , Fill in the overflow form .

11.HashMap Which method to use to resolve hash conflict （ Hash collision ）？

answer ：HashMap Use linked list and red black tree to solve hash conflict , See article for details put() Method execution process .

12.HashMap Why is the expansion of 2^n ？

answer ： The goal is to make the hash more uniform , This reduces hash collisions , To provide code execution efficiency .

13. In case of hash conflict HashMap How to value ？

answer ： If there is a hash conflict ,HashMap Will loop through every item in the list key Conduct equals contrast , Return the corresponding element . The relevant source code is as follows ：

do {
    
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k)))) //  When comparing, we should first look at  hash  Is the value the same 、 Look at the address or  equals
        return e; //  If the current node  e  Key objects and  key  identical , Then the return  e
} while ((e = e.next) != null); //  See if there is another node , If there is , Go on to the next round of comparison , Otherwise jump out of the loop 

14. What will the following program output ？

class Person {
    private Integer age;
    public boolean equals(Object o) {
        if (o == null || !(o instanceof Person)) {
            return false;
        } else {
            return this.getAge().equals(((Person) o).getAge());
        }
    }
    public int hashCode() {
        return age.hashCode();
    }
    public Person(int age) {
        this.age = age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public Integer getAge() {
        return age;
    }
    public static void main(String[] args) {
        HashMap<Person, Integer> hashMap = new HashMap<>();
        Person person = new Person(18);
        hashMap.put(person, 1);
        System.out.println(hashMap.get(new Person(18)));
    }
}

answer ：1
title ： because Person Rewrote equals and hashCode Method , all person Objects and new Person(18) The key value of is the same , So the result is 1.

15. Why rewrite equals() It must be rewritten hashCode()？

answer ： because Java Regulations , If two objects equals More equal （ The result is true）, So called hashCode It must also be equal . If I rewrite it equals() But it didn't rewrite hashCode(), It's against the rules , For example, the following code （ Comment out on purpose hashCode Method ）：

class Person {
    private Integer age;
    public boolean equals(Object o) {
        if (o == null || !(o instanceof Person)) {
            return false;
        } else {
            return this.getAge().equals(((Person) o).getAge());
        }
    }
//    public int hashCode() {
//        return age.hashCode();
//    }
    public Person(int age) {
        this.age = age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    public Integer getAge() {
        return age;
    }
    public static void main(String[] args) {
        Person p1 = new Person(18);
        Person p2 = new Person(18);
        System.out.println(p1.equals(p2));
        System.out.println(p1.hashCode() + " : " + p2.hashCode());
    }
}

Results of execution ：

true
21685669 : 2133927002

If rewritten hashCode() after , The result of the execution is ：

true
18 : 18

This is in line with Java The provisions of the , So rewrite equals() It must be rewritten hashCode().

16.HashMap stay JDK 7 What's the problem with multithreading ？

answer ：HashMap stay JDK 7 It will lead to the problem of dead cycle . Because in JDK 7 in , Multithreading HashMap Expanding the capacity will result in circular reference of the linked list , At this time get() Getting elements causes a dead loop , cause CPU 100% The situation of .

17.HashMap stay JDK 7 and JDK 8 What are the differences between ？

answer ：HashMap stay JDK 7 and JDK 8 The main differences are as follows .

• Storage structure ：JDK 7 Using arrays + Linked list ;JDK 8 Using arrays + Linked list + Red and black trees .
• Rules for storing data ：JDK 7 When there is no conflict , Store array ; When the conflict , Store the list ;JDK 8 Store arrays directly without conflicts , When there is a conflict , When the chain length is less than 8 when , Stored in a single chain table structure , When the chain length is greater than 8 when , Tree and store in the data structure of the red black tree .
• How to insert data ：JDK 7 It's head insertion （ First, move the data from the original location to the later 1 position , Then insert the data into the location ）;JDK 8 It's tail insertion （ Insert directly at the end of the list / Red and black trees ）.

summary

We can learn from this article ：

• Map Common implementation classes of Hashtable yes Java Early thread safe hash table implementation ;
• HashMap Is the most commonly used hash table implementation , But it's non thread safe , You can use ConcurrentHashMap replace ;
• TreeMap It is a hash table implementation based on red black tree that provides sequential access ;
• LinkedHashMap yes HashMap A subclass of , Saved the insertion order of records , It can be traversed in the same order as the insert .

HashMap stay JDK 7 It may cause circular reference of linked list during capacity expansion CPU 100%,HashMap stay JDK 8 When the data structure changes to ： Array + Linked list + How to store red black trees , Store arrays directly without conflicts , There are conflicts , When the chain length is less than 8 when , Stored in a single chain table structure , When the chain length is greater than 8 when , Tree and store in the data structure of the red black tree .

Click here to download the source code of this article