1. Characteristics of Map interface implementation class
1)Map and Collection exist side by side. Used to save data with mapping relationships: Key-Value
2) The key and value in the Map can be any reference type data and will be encapsulated into the HashMap$Node object.
3) Keys in Map are not allowed to be repeated
4) The value in Map can be repeated
5) The key of Map can be null, and the value can also be null. Note that if the key is null, there can only be one value, and there can be multiple values.
6) The String class is commonly used as the key of Map
7) There is a one-way one-to-one relationship between key and value, that is, the corresponding value can always be found through the specified key.
8) Key-value diagram of Map storing data. A pair of k-v is placed in a HashMap$Node. This is because Node implements the Entry interface. Some books also say that a pair of k-v is an Entry (as shown in the figure)
2. Common methods of Map interface
1) put: add
2)remove: delete the mapping relationship according to the key
3) get: Get the value based on the key
4) size: Get the number of elements
5) isEmpty: determine whether the number is 0
6) clear: clear
7)containsKey: Find whether the key exists
3.Map interface traversal method
First group
:
Take out all of them first
Key,
pass
Key
Take out the corresponding
Value
Set keyset = map.keySet();
Traverse:
//(1) Enhance for
System.out.println("-----First way-------");
for (Object key : keyset) {
System.out.println(key + "-" + map.get(key));
}
//(2) iterator
System.out.println("----Second way--------");
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(key + "-" + map.get(key));
}
Second Group
:
put all
values
take out
Collection values = map.values();
Traverse:
//(1) Enhance for
System.out.println("---take out all value enhancements for----");
for (Object value : values) {
System.out.println(value);
}
//(2) iterator
System.out.println("---Get out all value iterators----");
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
Object value = iterator2.next();
System.out.println(value);
}
The third group
:
pass
EntrySet
to get
k-v
Set entrySet = map.entrySet();// EntrySet
Traverse:
//(1) Enhance for
System.out.println("----Use EntrySet's for enhancement (Type 3)----");
for (Object entry : entrySet) {
//Convert entry to Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
//(2) iterator
System.out.println("----Use EntrySet's iterator (type 4)----");
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
Object entry = iterator3.next();
//System.out.println(next.getClass());//HashMap$Node -Implementation->Map.Entry (getKey,getValue)
//Downcast Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
4.Map interface implementation class-HashMap
1) Common implementation classes of Map interface: HashMap, lashtable and Properties implementation classes
2) HashMap is the most frequently used storage data of Map interface (HashMap$Node type)
3)HashMap is stored in the form of key-val pairs
4) The key cannot be repeated, but the value can be repeated, and null keys and null values are allowed.
5) If you add the same key, it will overwrite the original ky-val, which is equivalent to modification. (key will not be replaced, val will be replaced)
6) Like HashSet, the order of mapping is not guaranteed because the bottom layer is stored in a hash table. (idk8’s hashMap underlying array + linked list + red-black tree)
7) HashMap does not implement synchronization, so it is thread-safe. The method does not perform synchronization and mutual exclusion operations, and is not synchronized.
HashMap
Underlying mechanism and source code analysis:
Expansion mechanism:
1) The bottom layer of HashMap maintains an array of Node type
2) When creating the object, initialize the loadfactor to 0.75
3) When adding key-val, the index in the table is obtained through the hash value of the key. Then determine whether there is an element at the index
If there are no elements, add them directly. If there is an element at the index, continue to determine whether the key of the element is equal to the key to be added. If they are equal, replace val directly; if they are not equal, you need to determine whether it is a tree structure or a linked list structure, and handle it accordingly. If the capacity is found to be insufficient when adding, it needs to be expanded.
4) For the first addition, the table capacity needs to be expanded to 16. The threshold is 12 (16*0.75) 5) For subsequent expansions, the table capacity needs to be expanded to 2 times the original (32), and the threshold is the original 2 times of , i.e. 24. And so on
6) In Java8, if the number of elements in a linked list exceeds TREEIFY_THRESHOLD (default is 8), and the size of the table >= MIN TREEIFY_CAPACITY (default 64), tree formation (red-black tree) will be performed.
Source code analysis:
/* HashMap source code
1. Execute constructor new HashMap()
Initialize load factor loadfactor = 0.75
HashMap$Node[] table = null
2. Execute put to call the hash method and calculate the hash value of key (h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) {//K = "java" value = 10
return putVal(hash(key), key, value, false, true);
}
3. Execute putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;//auxiliary variables
//If the underlying table array is null, or length =0, expand to 16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//Get the Node at the index position of the table corresponding to the hash value. If it is null, directly add the k-v
//, create a Node and just add it to the location
if ((p = tab[i = (n - 1) & amp; hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;//auxiliary variables
// If the hash of the key at the index position of the table is the same and the hash value of the new key is the same,
// And satisfy (the key of the existing node of the table and the key to be added are the same object || equals returns true)
// Just think that new k-v cannot be added
if (p.hash == hash & amp; & amp;
((k = p.key) == key || (key != null & amp; & amp; key.equals(k))))
e = p;
else if (p instanceof TreeNode)//If the existing Node of the current table is a red-black tree, process it as a red-black tree
reason
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//If the node found is followed by a linked list, compare it in a loop
for (int binCount = 0; ; + + binCount) {//Infinite loop
if ((e = p.next) == null) {//If the entire linked list is not the same as him, add it to the end of the linked list
p.next = newNode(hash, key, value, null);
//After joining, determine whether the number of current linked lists has reached 8, and then
//Call the treeifyBin method to convert the red-black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash & amp; & amp; //If the same is found during the loop comparison, break and just replace the value
((k = e.key) == key || (key != null & amp; & amp; key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //Replacement, key corresponds to value
afterNodeAccess(e);
return oldValue;
}
}
+ + modCount;//Every time a Node is added, size + +
if ( + + size > threshold[12-24-48])//If size > threshold, expand the capacity
resize();
afterNodeInsertion(evict);
return null;
}
5. About treeing (converting to red-black tree)
//If the table is null, or the size has not reached 64, it will not be treed temporarily, but will be expanded. //Otherwise, it will be truly treed -> pruning
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
}
*/
5.Map interface implementation class-Hashtable
HashTable
Basic introduction to
1) The stored elements are key-value pairs: that is, K-V
2) The keys and values of the hashtable cannot be null, otherwise NullPointerException will be thrown
3) The usage of hashTable is basically the same as HashMap
4) hashTable is thread-safe (synchronized), hashMap is thread-unsafe
Hashtable
and
HashMap
Compared
6.Map interface implementation class-Properties
1. The Properties class inherits from the Hashtable class and implements the Map interface, which also uses a key-value pair to save data.
2. Its usage characteristics are similar to Hashtable
3.Properties can also be used to load data from the xxx.properties file into the Properties class object, and read and modify it.
Basic usage:
//Common methods
//Increase
Properties properties = new Properties();
properties.put("john", 100);
//Neither key nor value can be null
//properties.put(null, 100);
//properties.put("john", null);
properties.put("lucy", 100);
properties.put("lic",100);
properties.put("lic",88);
System.out.println(properties);//Delete
properties.remove("lic");//Change
properties.put("john","Peking University");
System.out.println(properties);//Check
System.out.println(properties.get("john"));
System.out.println(properties.getProperty("john"));
This article is the study notes of Han Shunping Java at Bilibili. If you have more time, you can watch the video to learn.