Java HashMap profile records

This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

Summary of Day2

A quick introduction to hashMaps in Java collections

Map

Definition in source (1.8) :

Set keySet(); Set keySet(); So key uses set to store values unique, unordered, and allowed to be NULL

For storing k-V structure data interface, its main implementation class: HashMap(used more in practical work) TreeMap Map set block diagram:

HashMap (overrides all methods of map)

The class definition:

As for maps, hashmap is the most used in practice. First, why is hashmap the most used in practice?

To Hash: The hash algorithm is definitely the most used attribute of this map. For development, we need fast and efficient performance for many contents, so the hash algorithm is actually to hash some very complicated or large data. Match the source data with the hash identifier and index the calculated identifier into the key list array of the word;

The hash method

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

This function is called a ‘perturbation function’ by the industry, but it has limited power. It basically says: use or to reduce map index collisions.

The hash method first retrieves the hashCode of the current key and then xor decrement the index of its own code value by 16 bits (four right moves before Java 1.8), and then performs subsequent judgments based on this number.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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 (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the code

PutTreeVal is also an optimization of the map storage data structure after 1.8 -> tree. Map entry(key-value) data before 1.7 is stored in the database as an array after certain hash, eg:

The above is the normal case, as soon as there is a collision of data will be performed each index to a linked list

The above two are pre-1.8 storage rules:

Why is the data store out of order for map? Map each time for data storage to hash and then will be back when the current data for subsequent judgment, one is to judge whether the capacity of the current data to reach the standard of the expansion, once reached the standard of expansion of the will to hash data so location is uncertain, and once there is data collision conflict (index), New data will be placed at the head of the linked list (source authors feel that the most recently inserted data is more likely to be accessed);

Then there is a more in-depth content about map expansion mechanism: After 1.8, not only did we implement simple capacity expansion, but also introduced the concept of Tree. Once the capacity reaches the default value of TREEIFY_THRESHOLD 8, putTreeVal will be used to Tree the index list.

Other methods

The interview questions

Map expansion mechanism (due to the length of this article, it will be detailed in a follow-up article)

Several common ways to map loops

EntrySet + iterator Set< map.entry <Object, Object>> entries = map.entryset (); entrySet + iterator Set< map.entry <Object, Object>> entries = map.entryset (); Iterator<Map.Entry<Object, Object>> iterator = entries.iterator(); while (iterator.hasNext()){ System.out.println(iterator.next().getKey()+":"+iterator.next().getValue()); }Copy the code

EntrySet + for for (map. Entry<Object, Object> Entry: entries) { System.out.println(entry.getKey()+":"+entry.getValue()); }Copy the code

KeySet +for Set<Object> objects = map.keyset (); for (Object object : objects) { System.out.println(object+":"+map.get(object)); }Copy the code

Collection<Object> values = map.values(); for (Object value : values) { } Set<Object> objects1 = map.keySet(); for (Object o : objects1) { }Copy the code

ForEach ((k,v)-> system.out.println ("key: "+ k +" value:" + v));Copy the code

End

Although more than three years of development experience, suddenly found that their in-depth understanding of the source code is still relatively little, usually for these use is not a lot but after understanding is still of great significance, continue to come on!!