Map interface and implementation class

Map system collection

graph TD;Interface.Map-->Class.HashMapInterface.Map-->Interface.SortedMapInterface.SortedMap-->Class.TreeMap

Interface: Interface

Class: Implementation class

Characteristics of the Map interface:

1. Used to store arbitrary key-value pairs (Key-Value)
2. Key: unordered, no subscript, no duplicates allowed (unique)
3. values: unordered, no subscripts, duplicates allowed

Map parent interface

• Features: store a pair of data (Key-Value), unordered, no subscripts, keys cannot be repeated, values ​​can be repeated

• Set(Map.Entry) Set set with matching key value

• Collection values() returns a Collection containing all values

• Method:

  • V put(K key, V value) Store the object in the collection and associate the key value.If the Key is repeated, the original value will be overwritten

  • Object get(Object key) Get the corresponding value according to the key

  • Set keySet(K) returns all Keys and returns a Key(key)

  • Set> entrySet() Returns the Set collection containing the relationship in the collection and returns an Entry (key-value pair)

package com.jhkj.map;import java.util.HashMap;import java.util.Map;/*** Use of Map interface* Features:* 1. Stored as key-value pairs* 2. The key cannot be repeated, the value can be repeated* 3. Disorder*/public class Demo1 {public static void main(String[] args) {// create a Map objectMap map = new HashMap<>();// 1. Add datamap.put("cn","China");map.put("uk","UK");map.put("usa","United States");System.out.println("Number of elements: " + map.size());System.out.println(map.toString());// 2. Delete datamap.remove("usa");System.out.println(map.toString());// 3. Traverse the data// 3.1 Use keySet()System.out.println("----------use keySet()----------");for (String key : map.keySet()) {System.out.println(key + "-----" + map.get(key));}// 3.2 Use entrySet()System.out.println("----------use entrySet()------------");for (Map.Entry entry : map.entrySet()) {System.out.println(entry.getKey() + "------" + entry.getValue());}// 4. Judgment// Determine if the key existsSystem.out.println(map.containsKey("cn"));// Determine if Value existsSystem.out.println(map.containsValue("Russia"));}}

The implementation class of the Map collection

• HashMap (emphasis):
  • Storage structure: hash table (array + linked list + red-black tree)
  • JDK1.2 version, thread-unsafe, fast running efficiency; allow to use null as key or value
• Hashtable (learn about it):
  • jdk1.0 version, thread-safe, allows slow efficiency; does not allow null as key or value
• Properties (subclass of Hashtable):
  • A subclass of Hashtable that requires both key and value to be String.Usually used for reading configuration files
• TreeMap:
  • Storage structure: red-black tree
  • Implements the SortedMap interface (a sub-interface of Map), which can automatically sort keys

HashMap source code analysis summary

1. When the HashMap is just created, the table is null. In order to save space, when the first element is added, the table capacity is adjusted to 16
2. When the number of elements is greater than the threshold (16*0.75=12), the expansion will be performed, and the size will be twice the original size after expansion, and the number of adjusted elements will be reduced for the purpose
3. Jdk1.8 When the length of each linked list is greater than 8 and the number of elements is greater than or equal to 64, it will be adjusted to a red-black tree to improve execution efficiency
4. jdk1.8 When the length of the linked list is less than 6, it is adjusted to a linked list
5. Before jdk1.8, the linked list was inserted at the head, and after jdk1.8, it was inserted at the end

The relationship between HashMap and HashSet

• Actually the HashMap class is called in the HashSet implementation class

public HashSet() {map = new HashMap<>();}

The add method calls the Key in the HashMap

public boolean add(E e) {return map.put(e, PRESENT)==null;}

Relationship between TreeSet and TreeMap

• In fact, the TreeMap class is called in the TreeSet implementation class

public TreeSet() {this(new TreeMap());}