Map introduction

This issue is wonderful

Catalog

Map The interface is introduced

Map Introduction to implementation class

HashMap

HashTable

ConcurrentHashMap

TreeMap

---

Map The interface is introduced

characteristic ：

• Key value pair (key,value), Bonds cannot be repeated , Values can be repeated , Each key can be mapped to up to one value ;
• Key repetition covers , No inheritance Collection Interface ;
• Different keys can point to the same Value;
• Support users' free binding Key Value and Value;
• You can directly access Key Value to get the corresponding Value

Capacity expansion ：

Initial capacity 16, Load factor 0.75, Expansion increment 1 times

The basic method ( notes ： Implementation classes can use these methods ！)

1、containsKey(key)： stay map If there key There is , There is returned true, Instead, return to false

2、putIfAbsent(key, value)： Determine the specified key first (key) Whether there is , If it does not exist, the key / Value pair insertion

3、 Traverse ：forEach((key, value)

4、 Put in ：put(key, value)

5、 adopt Key obtain value：get(key)

6、 Method to get iterator ：

• keySet()
• entrySet()

Traverse ：

So let's set up a Set Assemble and put in Key and value

    private Map<String, String> map = new HashMap<>();
		
	@Before
	public void setup() {
		map.put("1", "zs");
		map.put("2", "ls");
		map.put("3", "ww");
		map.put("4", "zl");
	}
	

Law 1： Get all the keys first Set aggregate , Re traversal （ adopt Key to get the value ） 

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

Law 2： Out Save key value Entry Of Set, Then traverse this Set that will do

    @Test
	public void demo9() {
		Iterator<Entry<String, String>> it = map.entrySet().iterator();
		while(it.hasNext()) {
			Entry<String, String> entry = it.next();
			System.out.println(entry.getKey() + ": " + entry.getValue());
		}

Map Introduction to implementation class

HashMap

Basic introduction

• Threads unsafe , The most commonly used , Fast , disorder (HashMap Unordered means that the insertion order is not recorded , Nor will they be sorted according to specific rules ; however HashMap The value will be saved according to key Of hashCode() To calculate the location of the storage ( The position is hashed , So it's disordered ), When deleting, the element is deleted )
• Internal use Array To store data
• HashMap yes Inquire about The most efficient data structure

Traversal example  

public void demo3() {
		Map<String, String> map = new HashMap<>();
		map.put("4", " Xiao Ming ");
		map.put("2", " Xiaobao ");
		map.put("3", " Wheat ");
		map.put("1", " Little black ");
		map.put("1", "zl");
		map.put("1", " Xiao Ming ");
		
		Iterator<Entry<String, String>> it = map.entrySet().iterator();
		while(it.hasNext()) {
			Entry<String, String> next = it.next();
			System.out.println(next.getKey() + " : " + next.getValue());
		}
	}

Output results  

The basic principle

JDK8 Before Table Array Medium Node() Processing logic ：（ Purple is chain structure ）

The part marked in green is JDK8 New processing logic , Aimed at Table[i] Medium Node The number of nodes is greater than 8 when , Improve search speed through red and black trees

principle ： Use join HashMap Of key And through a series of hash Algorithm, etc. to calculate this key Corresponding bucket number , This bucket number is array The subscript position in the array , If there are elements in this bucket , And more than 8 individual , Just use the number structure , lower than 8 One uses a linked list structure  

Here is a website that can see the dynamic change process of the above figure ： Data Structure Visualization

put(key,val) Method execution process  

HashTable

Thread safety , Less commonly used

ConcurrentHashMap

Thread safety , Than HashTable High performance

About ConcurrentHashMap, There is another point worth noting ：

stay JDK8 Before ,ConcurrentHashMap One barrel, one lock ( Default 6 The lock ) A segmented lock structure to store data to prevent multithreading safety problems , But in this way, the efficiency and performance will be reduced , therefore JDK8 after , Adopt the combination of one barrel and one lock CAS( Compare and replace ) Operation to improve performance , The reason for the performance improvement is CAS Optimistic lock is used in , It avoids the problem of multithreading safety ( Use local variables ) It also improves performance

TreeMap

• 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 )

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 "));
	}

differ HashMap Hash mapping for ,TreeMap The structure of red black tree , Formed a binary tree

LinkedHashMap

• 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) 

Code example  

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);
        }
	}

Output results  

Be careful ： Order and disorder describe the internal state of a system 、 The category of the internal elements of objective things and the relationship between objective things . Order means systematic Constituent elements 、 A regular arrangement of elements within or between things 、 Combine 、 Movement and transformation , Including structural order and motion order ; Disorder is the opposite , Refers to the internal elements of things or between things 、 Between the components within the system Chaos without rules The combination of 、 Movement and transformation , Including structural disorder and motion disorder . Order and disorder are two kinds of situations in the world , The difference between the two is relative , There is no absolute order and disorder in the world , There are factors in ordered things that destroy their regular arrangement or movement process , Disordered things always contain orderly factors