The interview,HashMap, see?
One. What do you knowmap ？
HashMap, TreeMap, ConcurrentHashMap, LinkedHashMap
twoHashMapWhat are the characteristics of?
-
Key and Value are allowed to be null, but only one record can have a null Key
-
Thread insecurity
-
A disorderly
-
Data structure is array + linked list/red-black tree (JDK1.8)
3. JDK1.8HashMap Why red black trees?
Linked list query time complexity O(n), insert time complexity O(1)
Red black tree query and insert time is O(LGN)
You can refer to this article tech.meituan.com/2016/06/24/ Meituan technical team under…
Four.HashMapWhy can the length only be a multiple of 2
- To calculate
HashThe position of elements can be calculated more efficiently by using bit operation instead of taking modulus.
The index of the element is assigned by the following code: index = hash & hashMap table length -1
if ((p = tab[i = (n - 1) & hash]) == null)
Copy the code-
It can be calculated faster in capacity expansion
key的indexTo improve capacity expansion efficiencyFor example, if the map size is 16, the index of key 2 is 2, and the index of key 18 is also 2
However, after the expansion, the index of key 2 is still 2, and the index of key 18 is · 2+16=18.
Here, 4ye directly intercepts the index recalculation part of the linked list in REsize, and there is a similar code in the red-black tree TreeNode
Five.HashMapWhen will the capacity be expanded
If (Hash table size), > (Hash table size x load factor), capacity expansion is performed
Vi. The size of the load factor
The load factor size determines the size of the hash table expansion and hash conflict. Every time a new element is put, it is checked to see if it needs to be expanded. By default, it is doubled.
Increasing the load factor increases the probability of hash conflicts and the time required for capacity expansion.
How to calculate the hash value
Compute the hashCode value of the key, and xor that value with its last 16 digits
This is done to reduce hash collisions
// >>> the unsigned bit moves to the right, that is, regardless of the positive or negative of the number, the high order is added 0
If the number is positive, then 0 is added; if the number is negative, then 1 is added
// << left to add 0, there is no positive or negative
Copy the code
Check ~
int hashCode = "Java4ye".hashCode();
System.out.println((hashCode ^ (hashCode >>> 16)) &15);
// Print out 0
hashMap.put("Java4ye"."1");
Copy the code
Resolution of hash conflicts
-
Open addressing
-
Chain address method (zip method) adopted by HashMap
-
Then the hash method
-
Public overflow area method
Implementation of PUT and GET
When the put
Compute the hash value of the key and the index of the bucket it is in. If there is no collision, put it directly into the array.
If there is a collision, check whether this key is the same key. If so, overwrite it directly.
If the key is the same, onlyIfAbsent or the original value is null. If the key is the same, onlyIfAbsent will be replaced or the original value will be retained.
If the corresponding key is found, the old value is returned and no further execution is carried out
If a new element is added, the system determines the hash table size. If the value is greater than the hash table size x load factor, the system expands the hash table. Return null
You can take a look at the source code given by 4YE, every step has made this important note ~, anyway I understand their own hahahaha 😝
Put the source code:
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// The capacity of the bucket is not initialized when the Hashmap is created. It is expanded when the PUT operation is performed
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Check if there is any data in the corresponding index
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// If the key is the same as the key, then determine which data structure it belongs to, such as red-black tree or linked list
else {
Node<K,V> e; K k;
// Check whether it is the same key
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// Check if it is a red black tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// A list is a list. Search for the key in the list, break if there is one, search until the last element in the list, and add to the end of the list
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// If the threshold is 8, it is converted to a red-black tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Check if it is the same key
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}If the value of onlyIfAbsent is false or the current value is null, the key is overwritten and return the old value.
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
returnoldValue; }}// If put is a new element, it will go to this step, +1, to determine whether to expand
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the codeWhen getting, the hash value of the key should be calculated first, and then the index of the key should be calculated. If there is no hash conflict, it should be returned directly. If there is, it should determine whether the current data structure is a linked list or a red-black tree, and then extract the value from the corresponding structure
This image is from meituan technology team
X. How do you tell if an element is the same
To judge whether their hash values are the same, the same word again to judge the equals method of key | | = = methods are the same, the same word is the same element
11. When are red black trees used?
You can refer to the above put source code, the main code is shown in figure:
You can see that when the size of the array is greater than 64 and the length of the list is greater than 8, the list is converted to a red-black tree.
If the size of a red-black tree is less than or equal to 6, it will be converted to a linked list, refer to resize source code
Twelve. Head insertion and tail insertion
Since HashMap in jdk1.7 uses header interpolation, new elements are always placed at the head of the list.
For example, if the HashMap size is 4, the indexes of key 2, key 6, and key 10 are all 2
So when it expands, the order becomes
Index: 2, key: 10, 2
Index: 6, key: 6
In a multi-threaded environment, this can lead to an infinite loop
For example, thread A is stuck at 2.next 6, 6.Next 10, and thread B has resized to 10.next2.
This is one of the reasons why HashMap threads are unsafe.
The same example: tailgating does not cause an endless loop
For example, thread A is still stuck at 2.next 6, 6.next 10, and thread B has resized to 2.next10.
Using tail interpolation does not mean that a HashMap is thread-safe, because you cannot guarantee that the values put in and get out will be the same as those put in
Because it may have been modified by another thread.
If you think it’s ok, don’t forget to bookmark it before the interview
Welcome attention, make a friend!! (•̀ ω •́)y
Java4ye A little white blogger focused on productivity ~(increasing groping time), sharing learning resources, technological awareness, little things about programmer life let us groping together ~(● world twentyconsciousness) Java4ye here to prepare a series of learning resources for you, as well as a variety of plug-ins, software oh welcome message! Thanks for your support! O (≧ ヾ del ≦ *)