“This is the fourth day of my participation in the First Challenge 2022. For details: First Challenge 2022”
A paunchy wearing plaid unlined upper garment of bald old, slowly think you come, wish to see this bald, a few root, how also get top architecture division! But I also read the source code, not empty him! So let’s start today’s HashMap tour!
Young man, today I will test you HashMap, see you in the end is a mule 🐎!
Ok, let’s see how I do today! You’re the mule, I’m 🐎!
Bald old: HashMap played, first brief introduction!
Me: HashMap mainly implements the Map interface, which is mainly used to store key-value pairs. It belongs to the commonly used Map set. The underlying data of JDK1.7HashMap is array and linked list. Linked list is mainly used to resolve conflicts. Red black tree is added after JDK1.8.
The bald man: Since you mentioned hash conflicts, why don’t you tell me how 1.7 and 1.8 were resolved respectively? (Catch the details, kid, take you down!)
I :(be to let you ask this, dropped my trap, I be seduce you that!) B: well… Each cell of the array is a linked list. When a key is added, the hash value is computed using the hashcode of the key. The hash value is computed using (n-1) &hash. The same direct coverage, not the same through the zipper method to solve, the zipper method is to add the conflict value to the linked list!
The treeifyBin() method is called if the length of the list is greater than the threshold (default: 8). The treeifyBin() method is used to determine if the length of the list is greater than 64. If the length is less than 64, the treeifyBin() method will be converted to a red-black tree.
The bald man: Since you’ve read the source code, what are the important attributes of HashMap? (Hey, you can only read the source code to know!)
Me :(ouch, unexpectedly did not ask me put process, can can! If the loadFactor is equal to 1, the more compact the array is, the smaller the density is, and the longer the linked list will be, resulting in a slow query. If it is small, the more sparse the array is, the denser it is, resulting in a waste of space, and the default load factor is 0.75. The second attribute is threshold, which is mainly used to determine when to perform resize() expansion. His calculation formula is threshold==loadFactor(0.75) * DEFAULT_INITIAL_CAPACITY(16); There are also some converting red-black trees with a default value of 8 TREEIFY_THRESHOLD, MIN_TREEIFY_CAPACITY64, and so on.
Bald old man: YesputMethods: Introduce 1.7 and 1.8 respectivelyput(You like to mention 1.7 and 1.8 so hard to ask you!)
Me :(ha ha ha ha, fell into my trap again, this time can be said to be my whole lead you by the nose) MMMM… (Pretend to touch the head for a moment) then I will say 1.7, first determine the position of the key by hash method, then insert it directly if there are no elements in this position, if there are elements, determine whether the key is the same, then overwrite it directly, and insert the key into the head of the linked list through the head insert method. That’s true for 1.8. If the array is not initialized, then insert the hash key to the end of the list, similar to 1.7, and call treeifyBin() if the list length is greater than the threshold. If the size of the array is greater than 64, it will be converted to a red-black tree, and then call the red-black tree’s PUT method. If the size is greater than the threshold, it will be expanded.
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Determine whether the array is initialized, or whether the length is 0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// If the current position has no value, a new node is generated and inserted
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// If the key is the same as the inserted value, overwrite it directly
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// If it is a red-black tree, putTreeVal is called directly
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// Insert the end of the list
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// If the length of the list is already 7, the red-black tree needs to be converted
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; }}if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// If the actual size is greater than the threshold, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeBald man: Well, that’s a common way to use HashMap!
I :(NTM, whether have no what to ask of, you whether want to run away!
/ * * *@author: tianjx
* @date: 2021/12/21 choicest *@description: map common method */
public class HashMapFunction {
public static void main(String[] args) {
HashMap<String, String> map = new HashMap<>();
map.put("namekey"."namevalue");
map.put("passwordkey"."passwordvalue");
System.out.println(map);
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");
Set<String> strings = map.keySet();
for (String string : strings) {
System.out.println(string);
System.out.println(map.get(string));
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");
Collection<String> values = map.values();
for (String value : values) {
System.out.println(value);
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");
Set<Map.Entry<String, String>> entrySet = map.entrySet();
for (Map.Entry<String, String> entry : entrySet) {
System.out.println(entry.getKey());
System.out.println(entry.getValue());
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -");
System.out.println(map.size());
System.out.println(map.containsKey("namekey"));
System.out.println(map.containsValue("namevalue"));
System.out.println(map.replace("namekey"."namevaluevalue"));
System.out.println(map.get("namekey")); }}Copy the codeToday’s war bald old here, control the amount, steal a small lazy, ha ha ha ha! Like brothers continue to pay attention to a wave, I amtianjx01Thank you for your attention and praise!
Reference article: Guide brother Java learning
Thank you for reading, I am Alson_Code, a programmer who likes to complicate simple problems and simplify complex problems! ❤