Detailed explanation of map set

    Today is mainly to give you a detailed explanation Map aggregate , If you are interested in collections , You can look at the previous two articles , Explained it to you in detail list and set aggregate .

Catalog

One .Map aggregate

Two .Map Set common methods

1. add to

2. Delete

3. obtain

4. Judge

3、 ... and .HashMap aggregate

1.HashMap data structure

2. Why use red black trees ？

3. What is a red-black tree ？

4.HashMap Of put Execution process

5. Code implementation

Four .HashTable aggregate  

5、 ... and .ConcurrentHashMap aggregate

6、 ... and .TreeMap aggregate

7、 ... and .LinkedHashMap aggregate

---

One .Map aggregate

 HashMap aggregate ,HashTable aggregate ,ConcurrentHashMap aggregate ,TreeMap aggregate ,LinkedHashMap It's all inherited Map aggregate , The following is a detailed introduction to these collections .

• Map Sets are unordered .
• Map It's a key （key） Container for storing elements , key （key） Much like subscript , stay List The middle subscript is an integer . stay Map In the key （key） You can make any type of object .Map There cannot be duplicate keys in the （Key）, Each key （key） Have a corresponding value （value）. If the key is repeated , Then it will be covered .
• There is no inherited interface collection Interface , Only list The collection and set The collection inherits collection Interface .
• Capacity expansion ： Initial capacity 16, Load factor 0.75, Expansion increment 1 times .
• Map Adding elements is not using add To increase the , But use put Add elements .
• Traverse ：Map There is no way for a collection to take elements directly , Instead, it turns into Set aggregate , Get elements through iteration .

Two .Map Set common methods

1. add to

• put（key,value）（ The entered value can be the same key, But if the same key, The new addition will cover the original , The returned value is the previous , If not, go back null）

2. Delete

•   remove（） Delete the elements inside according to the key
•   clear()  Empty all elements in the collection

3. obtain

• get（key） Get the value according to the key
• keySet（） Get all of it first key aggregate , When you need to query value When , We go through key To query .
• entrySet（） Yes, it will key and value Take out all the key value pairs of , Only once .

        Later, I will explain how to use it in detail in the code .

4. Judge

•  boolean isEmpty()   The length is 0 return true otherwise false
• boolean containsKey(Object key)   Determines whether the set contains the specified key
• boolean containsValue(Object value)   Determines whether the set contains the specified value

  notes ： Inherit Map All sets of sets have Map The way to assemble

3、 ... and .HashMap aggregate

• HashMap Thread unsafe , But fast , The most commonly used set
• It uses arrays to store data internally

1.HashMap data structure

jdk1.8 Before ： Array + Linked list

jdk1.8 after ： Use arrays + Linked list + Red and black trees , When the chain length is greater than 8 when , The linked list structure is transformed into a red black tree structure . 

2. Why use red black trees ？

      Why is it jdk1.8 Red and black trees will be added , Mainly because List insertion although fast , Search slow , If the linked list is very long , And the data we need to find is at the end , Then the query will be very slow , Red and black trees can make queries faster , It uses left-hand and right-hand rotation , Speed up the search .

3. What is a red-black tree ？

   Red black tree is a kind of specialized AVL Trees （ Balanced binary trees ）, It is to maintain the balance of binary search tree through specific operations when inserting and deleting , For high discovery performance . 

  Take a look at the following picture

 

 

4.HashMap Of put Execution process

We are using put The method will be passed into key and value Parameters

After we pass in these two parameters ,

• First step , our put The method will judge this hashmap Is it null Or if the length is 0, If so, yes hashmap Array resize() Capacity expansion ,
• The second step ,put The method will be based on this key Calculation hash Code to get the position of the array ,（ There's a little bit of explanation here , our hashmap By default, it is composed of an array and a linked list ）, After getting the position, of course, we continue to judge whether the subscript value of this array is null, by null Nature is directly inserted into our value value , If not, proceed to step 3
• The third step , Judge key Is it null, When key！=null We can cover value value ,key==null continue
• Step four , If key The value is also empty , Then judge whether the node type is a linked list or a red black tree
• Step five , If the node type is red black tree , Then perform the red black tree insertion operation

    If the node type is linked list , that put Method will traverse the linked list ,for Loop through the linked list until the end of the linked list , Then tail insert , When the list length >=8 when , Will enter the linked list to the red black tree method ,treeifyBin Method also determines the length of the array , The length of the array >=64, Chain length >=8 At the same time satisfy , Will turn the linked list into a red black tree ; stay for During loop traversal , If key identical , Then insert the element directly

• Step five , Record the number of operations variable modCount+1, Finally, judge the current map How many elements are there in , Compare with the threshold , If the threshold is exceeded, the capacity will be expanded. When the array capacity exceeds the maximum capacity, the capacity will be doubled （ That is, binary carry ）, No return null

    picture ： From the Internet      

5. Code implementation

•   Use put Method to add data to the set

package com.yjx.test;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

import org.junit.Before;
import org.junit.Test;

public class MapDeome {
	
	// Define the type of keys and values , The key can be any type .
	 private Map<Integer, String> map=new HashMap<Integer, String>();
	
		 map.put(1, " Zhang Yi ");
		 map.put(2, " Zhang Er ");
		 map.put(3, " Zhang San ");
		 map.put(4, " Zhang Si ");
	

}

•   Use map.entrySet() get data

 @Test
	 public void test01() {
		 // iterator 
		Iterator<Entry<Integer,String>> it=map.entrySet().iterator();
		 // Traversing elements through iterators 
		while(it.hasNext()) {
			Entry<Integer, String> key=it.next();
			System.out.println("key:"+key.getKey()+"value:"+key.getValue()+"-----");
		}
	 }

• Use map.keySet() get data

@Test
	 public void test02() {
		 Iterator<Integer> it=map.keySet().iterator();
		 while(it.hasNext()) {
			int key=it.next();
			System.out.println(map.get(key));
		 }
		 
	 }

Four .HashTable aggregate  

  This collection is thread safe , But the performance is too slow .

Why is the performance slow ？

  When the thread is running , He will lock it , Lock all , Only one thread is allowed to enter , When the thread finishes executing , Until the next thread enters , So the performance is too slow .

The code is as follows ：

I use it. Junit, Add... Directly to the method Test There is no need to write another main Method execution , But if you don't use this , It's just mian Just execute in the method .

package com.yjx.test;

import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

import org.junit.Before;
import org.junit.Test;

public class HashTableDeom {
	
	 private Map<Integer, String> map=new Hashtable<Integer, String>();
	 
	 @Before
	 public void put() {
		 map.put(1, " Zhang Yi ");
		 map.put(2, " Zhang Er ");
		 map.put(3, " Zhang San ");
		 map.put(4, " Zhang Si ");
	 }
	 
	 @Test
	 public void test() {
		Iterator<Entry<Integer, String>> it=map.entrySet().iterator();
		while(it.hasNext()) {
			Entry<Integer, String> obj=it.next();
			System.out.println("key:"+obj.getKey()+"value:"+obj.getValue());
		}
	 }

}

5、 ... and .ConcurrentHashMap aggregate

  Thread safety , Than HashTable Better performance .

Why is it better than HashTable Better ?

because HashTable The lock is directly locked , however ConcurrentHashMap A set is an array and a lock , So performance ratio HashTable good .

Code implementation ：

• package com.yjx.test;
  
  import java.util.Iterator;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.concurrent.ConcurrentHashMap;
  
  import org.junit.Before;
  import org.junit.Test;
  
  public class ConcurrentHashMapDeom {
   
  	private Map<Integer, String> map=new ConcurrentHashMap<Integer, String>();
  
  	 @Before
  	 public void put() {
  		 map.put(1, " Zhang Yi ");
  		 map.put(2, " Zhang Er ");
  		 map.put(3, " Zhang San ");
  		 map.put(4, " Zhang Si ");
  	 }
  	 
  	 
  	 @Test
  	 public void test01() {
  		Iterator<Entry<Integer, String>> it= map.entrySet().iterator();
  		while(it.hasNext()) {
  			Entry<Integer, String> obj=it.next();
  			System.out.println("key:"+obj.getKey()+"value:"+obj.getValue());
  		}
  	 }
  }
  

---

6、 ... and .TreeMap aggregate

• key Values are sorted in a certain order , Based on the red black tree , Unlimited capacity , Non-thread safety , More commonly used
• The performance is better when adding or getting elements HashMap slow ( It is necessary to maintain the internal red black tree , Used to guarantee key Order of values )
• Can compare the size of elements , according to key Compare ( Natural order of elements , The custom comparator in the collection can also be sorted )

  Code implementation

private TreeMap<String,Student> treeMap;
	
	@Before
	public void setup() {
		
		treeMap = new TreeMap<String,Student>(new Comparator<String>() {
 
			@Override
			public int compare(String o1, String o2) {
				//  negative    0   Positive numbers 
				return o1.compareTo(o2);
			}
 
		});
		treeMap.put("1", new Student(5, " The small white "));
		treeMap.put("2", new Student(3, " Little black "));
		treeMap.put("3", new Student(2, " Xiao Huang "));
		treeMap.put("4", new Student(4, " Xiao Ming "));
		treeMap.put("3", new Student(1, " Little black "));
		treeMap.put("4", new Student(4, " Xiao Ming "));

---

7、 ... and .LinkedHashMap aggregate

• Inherit HashMap
• One was maintained Double linked list
• LinkedHashMap yes Orderly Of , And The default is the insertion order
• By default entryset The collection order obtained is the insertion order of the nodes ( By default, they are arranged in the order of insertion , First inserted node ( The oldest node ) by head, The newly inserted node is tail) 

The code is as follows

Map<String, String> linkedHashMap = new LinkedHashMap<>();
	@Test
	public void linkedHashMap() {
        linkedHashMap.put("5", " Hey ");
        linkedHashMap.put("4", " Joy ");
        linkedHashMap.put("1", " ha-ha ");
        linkedHashMap.put("3", " ha-ha ");
        linkedHashMap.put("3", " Hi, hi ");
        linkedHashMap.put("4", " Joy ");
        linkedHashMap.put("1", " ha-ha ");
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

  That's all for the explanation of the collection , Interested in collections , You can read the previous two articles list and set aggregate .