“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”
The birth of HashMap
1.1 an array
Array: a physically contiguous piece of storage of a certain size.
Benefits: Quickly find and modify contents according to subscripts.
Disadvantages: Size determination, cannot be modified. Adding new elements or deleting elements can be tricky.
Static initialization of an array
// Array implementation 1:
// Data type array name [] = {value, value... }
String str[] = {"Mobile end"."Android"."iOS"};
System.out.println(str.length);// Three elements
for (int i = 0; i <str.length ; i++) {
System.out.println(str[i]);
}
// Array:
// Data type array name [] = new data type [] {value, value... }
String str2[] = new String[3];
str2[0] = "Mobile end";
str2[1] = "Android";
str2[2] = "iOS";
System.out.println(str2.length);// Three elements
for (int i = 0; i <str2.length ; i++) {
System.out.println(str2[i]);
}
Copy the codeThe result is the same.
"E:\Android\Android StudioO\jre\bin\java.exe".3Mobile Android iOSCopy the codeIf I want to add two more elements (Java, Kotlin), then the array is not appropriate, and the order table appears.
Table 1.2 order
Sequential table: A linear table stored as an array that is physically contiguous, logically contiguous, and dynamically incremented. (such as: ArrayList)
Sequential tables are used much more frequently than data. Use certainly can use, let’s look at the source code.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
transient Object[] elementData;// An array buffer that stores the elements of ArrayList.
private int size;/ / the size of the ArrayList
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public void clear(a) {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0; }}Copy the codeAnd then you’ll notice that we’re still using arrays, but we’re just handling the array instead of doing it ourselves.
Original data:
New data:
Adding and deleting elements in a sequential list requires a large number of operations such as moving elements, so the linked list is generated.
1.3 list
Linked list: A linked list is a discontinuous, non-sequential storage structure on a physical storage cell. The logical order of data elements is achieved by connecting the Pointers in the list.
new
Change the pointer to element 1 from element 2 to element 4, and then to element 4 to element 2.
Remove elements
The pointer to element 1 points directly to element 3.
1.4 ArrayList vs. LinkedList
ArrayList(sequential list) :
- Advantages: Quick search
- Disadvantages: add and delete slowly
LinkedList (list)
- Advantages: fast addition and deletion
- Disadvantages: Slow search
So the question is when do you use an ArrayList? When is LinkedList used? Why is that?
So can you combine the advantages of sequential and linked lists? – the Hash table
1.5 the Hash table
A Hash table (also called a Hash table) is a data structure that is directly accessed based on Key values. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping function is called a hash function, and the array of records is called a hash table.
A hash table is essentially an array. You can access data directly according to a key value, fast search.
Second, the HashMap
A HashMap uses Node(implements map.Entry) arrays to store key-value pairs. Each key-value pair forms a Node entity. The Node class is actually a one-way linked list structure with a Next pointer that can be connected to the Next Node entity.
Note: The Entry in jdk1.8 HashMap is gone, replaced by Node, but Node also implements the Map.Entry interface, similar to the previous Entry.
The Node class
static class Node<K.V> implements Map.Entry<K.V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey(a) { return key; }
public final V getValue(a) { return value; }
public final String toString(a) { return key + "=" + value; }
public final int hashCode(a) {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {... }}Copy the codeHash, key, and value represent the data of this node, and next represents the data pointing to the next node.
-
Before JDK1.8, the underlying hash table is implemented by array + linked list, that is, the linked list is used to handle conflicts, and the linked list with the same hash value is stored in a linked list. However, when there are many elements in a bucket, that is, there are many elements with the same hash value, searching by key value is inefficient.
-
In JDK1.8, hash table storage is realized by array + linked list + red-black tree. When the length of the linked list exceeds the threshold (8), the linked list is converted to red-black tree, which greatly reduces the search time.
2.0
class HashMapTest {
public static void main(String[] args) {
/ / create a HashMap
HashMap<String,String> hashMap = new HashMap<>();
// Add data (key-value)
hashMap.put("name"."Handsome");
hashMap.put("age"."20");
hashMap.put("subject"."Android");
hashMap.put(null."Empty Key");
System.out.println("HashMap1:"+hashMap.toString());//{null= null, subject=Android, name= 0, age=20}
// Add data (overwrite existing keys)
hashMap.put("age"."26");
System.out.println("HashMap2:"+hashMap.toString());//{null= null, subject=Android, name= id, age=26}
// Get value based on key
System.out.println("Key-null:"+hashMap.get(null));/ / short Key
System.out.println("Key-subject:"+hashMap.get("subject"));//Android
// Delete elements based on key
System.out.println("Delete subject corresponding to :"+hashMap.remove("subject"));// Delete subject corresponding to Android
// Delete elements according to key-value
System.out.println("Remove the age."+hashMap.remove("age"."20"));// Delete age corresponding to 20:false
System.out.println(hashMap.toString());//{null= null Key, name= new, age=26}
System.out.println("Remove the age."+hashMap.remove("age"."26"));// Delete age corresponding to 20:true
System.out.println("HashMap3:"+hashMap.toString());//{null= null, name= null}
// Select * from key-value Set ();
Set<Map.Entry<String,String>> entrySet= hashMap.entrySet();
for (Map.Entry<String, String> strEntry : entrySet) {
System.out.println("Traversal the Set:"+strEntry.getKey()+"-"+strEntry.getValue());
}
// Get the Set of keys
Set<String> strKeySet= hashMap.keySet();
for (String s : strKeySet) {
// Get the value from key
System.out.println("Traversal the KeySet set:"+s+"-"+hashMap.get(s));
}
// Get a Set of key-values. // Get an iterator
Set<Map.Entry<String,String>> itEntrySet= hashMap.entrySet();
Iterator iterator = itEntrySet.iterator();
while (iterator.hasNext()){
Map.Entry map= (Map.Entry)iterator.next();
System.out.println("Iterator:"+map.getKey()+"-"+map.getValue());
}
// There are other ways to iterate over data}}Copy the codeThe results
"E:\Android...."
HashMap1:{null= empty Key, subject=Android, name= time, age=20}
HashMap2:{null= empty Key, subject=Android, name= time, age=26}
Key-nullKey-subject:Android delete subject Corresponding to Android delete age:false
{null= Empty Key, name= time, age=26} to delete the age:true
HashMap3:{null= null Key, name= 0}nullSelect * from KeySet; select * from KeySet;null- Empty Key iterates through the KeySet: name- Iterator:null- Empty Key Iterator: name- Process finished with exit code0
Copy the code2.1 Construction method
/** * Default load factor value */
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
/** * The load factor of the hash table. * /
final float loadFactor;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/** * Construct an empty HashMap with a default load factor (0.75). * /
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the codeHashMap has four constructors that initialize three parameters:
- InitialCapacity: indicates the initialCapacity (16 by default).
- LoadFactor Loads the factor (0.75 by default).
- Threshold Threshold: indicates the maximum number of value pairs that a hashMap can contain. If the number exceeds the threshold, the value pairs need to be expanded.
threshold=initialCapacity*loadFactor.
Load factor: By default, the array size is 16, so when the number of elements in the HashMap exceeds 16*0.75=12, the array size is doubled to 16*2=32, and the position of each element in the array is recalculated. Of course, this value is optional, but changing it is not recommended.
We usually use the parameterless constructor. With the HashMap created, let’s start storing the data.
2.2 the put ()
Add data:
-
Key can be null
-
Key is unique. If key exists, value content is overwritten
public V put(K key, V value) {
return putVal(hash(key), key, value, false.true);
}
Copy the codeHere we hash the key before calling the putVal() method.
2.2.1 hash (key)
/** * Computes key.hashcode () and hashes the high hash (XOR) to the low hash. Since the table uses a quadratic power mask, the set of hashes that change bits only above the current mask will always conflict. * Using trees to handle a lot of conflicts in bin, we simply xor some of the shifted bits in the cheapest way to reduce system losses, as well as merge the impact of the highest bits that would otherwise never be used for index calculations due to table boundaries (source). * /
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
public int hashCode(a) {
return identityHashCode(this);
}
static int identityHashCode(Object obj) {
int lockWord = obj.shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
return identityHashCodeNative(obj);
}
Copy the code- Returns 0 when key == null, which means that key can be set to NULL.
- You can see from the identityHashCode() method that the key can be of any type and can become a hashCode of type int.
What is H >>> 16?
H is hashCode. H >>> 16 is used to extract the height of H 16, (>>> is unsigned right shift)
0000 0100 1011 0011 1101 1111 1110 0001
>>> 4
0000 0000 0100 1011 0011 1101 1111 1110
>>> 16
0000 0000 0000 0000 0000 0100 1011 0011
Copy the codeThe above two examples – one >>>4 and one >>>16 – can be used for comparison.
This returns a Hash value based on the Key. So let’s go ahead and look at putVal().
2.2.2 putVal ()
/** * table initializes the array of Node types that store data when first used, and resizes as needed. * Length is equal to a power of 2. (0 in special cases), each element of the array = 1 singly linked list */
transient Node<K,V>[] table;
/ * * *@paramThe hash value of the hash key *@paramThe key key *@paramValue Specifies the value * to be placed@paramOnlyIfAbsent If true, do not change the existing value *@paramIf evict is false, the table is in create mode. *@returnThe previous value, if not, returns null */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// Check whether the table is initialized
if ((tab = table) == null || (n = tab.length) == 0)
// Call the resize() method to initialize and assign
n = (tab = resize()).length;
// Get the subscript using hash, if the data is null
if ((p = tab[i = (n - 1) & hash]) == null)
// TAB [I] subscript has no value, create a new Node and assign it.
tab[i] = newNode(hash, key, value, null);
else {
// TAB [I] index has data, collision occurred
Node<K,V> e; K k;
// Check that the hash value of TAB [I] is the same as the hash value of TAB [I], and the key value of TAB [I] is the same as the key value
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// Replace the original data directly
e = p;
else if (p instanceof TreeNode)// Determine the data structure is a red-black tree
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {// Data structures are linked lists
for (int binCount = 0; ; ++binCount) {
// the next node of p is null, indicating that p is the last node
if ((e = p.next) == null) {
// Create a Node and insert it at the end of the list
p.next = newNode(hash, key, value, null);
// When the element >=8-1, the list becomes a tree (red-black tree)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// Exit the loop if the key already exists in the list
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break;
// Update p to point to the next node and continue traversalp = e; }}// If a key already exists in the list, change the value of the original key and return the old value
if(e ! =null) {
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);// Method to call when replacing old values (null by default)
return oldValue;
}
}
++modCount;// Number of changes
// Determine whether to expand the map size based on the map value
if (++size > threshold)
resize();
afterNodeInsertion(evict);// Method to be called on successful insertion (null by default)
return null;
}
Copy the code2.2.3 the resize ()
/** * Default initial capacity - must be a power of 2. * /
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/** * Initialize or double the table size. If empty, the allocation is based on the initial capacity target saved in the field threshold. * Otherwise, because we use the quadratic extension */
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null)?0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// The table has been initialized and its capacity is greater than 0
if (oldCap > 0) {
//MAXIMUM_CAPACITY=1<<30=2 to the 30th power =1073741824
if (oldCap >= MAXIMUM_CAPACITY) {
// If the old capacity reaches the maximum value, the capacity is not expanded and the threshold is set to the maximum value
// integer. MAX_VALUE=(1 << 31)-1=2 to the 31st power -1=2147483648-1
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // Double the size
}
else if (oldThr > 0) // Initialize the container =threshold
newCap = oldThr;
else {
// If threshold and table are not initialized, it is the first initialization
// The first time I entered there was nothing so I initialized the container (16)
newCap = DEFAULT_INITIAL_CAPACITY;
/ / 12 = 0.75 * 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// If newThr is 0, calculate the threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// Update the threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// Update table data
table = newTab;
// If there is already data in the previous bucket, the hash value will change as the table capacity changes, and the subscript needs to be recalculated
if(oldTab ! =null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// will specify that subscript data is not null
if((e = oldTab[j]) ! =null) {
// Empty the specified subscript data
oldTab[j] = null;
// Specify only one subscript data
if (e.next == null)
// Store the data directly to the newly calculated hash index
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)/ / the red-black tree
// Split the nodes in the tree box into lower tree box and upper tree box. If it is now too small (<=6), the data structure is removed from the red-black tree and replaced with a linked list.
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { / / list
// Recalculate the hash value and regroup according to the new subscript
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
if(loTail ! =null) {
loTail.next = null;
newTab[j] = loHead;
}
if(hiTail ! =null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
Copy the codeTherefore, the resize() method initializes the container and assigns a value to table, returning Node<K,V>[].
2.2.4 putTreeVal ()
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) { Class<? > kc =null;
boolean searched = false;
// Get the root nodeTreeNode<K,V> root = (parent ! =null)? root() :this;
If there is no key conflict, store the object directly and return null object
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//dir: determines the location of the node
if ((ph = p.hash) > h)// The hash value of the current node is greater than the hash value of the stored object
dir = -1;
else if (ph < h)// The hash value of the current node is smaller than the hash value of the stored object
dir = 1;
else if((pk = p.key) == k || (k ! =null && k.equals(pk)))// If the current node is equal to the hash value of the object and the key is the same, the current node is returned
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
// If you sort by the comparator instead of the hash value, then the comparator returns the value to decide to enter the left and right nodes
if(! searched) { TreeNode<K,V> q, ch; searched =true;
if(((ch = p.left) ! =null&& (q = ch.find(h, k, kc)) ! =null) || ((ch = p.right) ! =null&& (q = ch.find(h, k, kc)) ! =null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
// If the left or right node of p is empty, the storage location has been found
if ((p = (dir <= 0)? p.left : p.right) ==null) {
Node<K,V> xpn = xp.next;
// Create a node
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
// Set the location according to dir
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if(xpn ! =null)
((TreeNode<K,V>)xpn).prev = x;
// Insertion tree, set red and black nodes, whether to rotate
MoveRootToFront resets the root node
moveRootToFront(tab, balanceInsertion(root, x));
return null; }}}Copy the code2.3 the get ()
To get the data
This method returns the result:
- Node (the Node);
- null
- The data corresponding to this key is NULL.
- The key does not exist in the HashMap
public V get(Object key) {
Node<K,V> e;
// Hash (key) : Computes the hash value based on the hashCode of the key, as in put.
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the codeGetNode () returns null if the node is null, or the value of the key if the node exists.
2.3.1 getNode ()
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @returnNode, if not null */ is returned
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// Get the first element of the table based on the hash value.
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
// If the first node is the Key we are looking for, we return it directly
if (first.hash == hash && // ((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
// Get information about the next node
if((e = first.next) ! =null) {
// If the data structure is a red-black tree, get the node by getTreeNode() and return it
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// Otherwise loop through the list to find the node and return
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the code2.3.2 getTreeNode ()
static final class TreeNode<K.V> extends LinkedHashMap.LinkedHashMapEntry<K.V> {
TreeNode<K,V> parent; // Red black tree node
// Call the tree's find() function
final TreeNode<K,V> getTreeNode(int h, Object k) {
return((parent ! =null)? root() :this).find(h, k, null);
}
Copy the code2.3.3 the find ()
final TreeNode<K,V> find(inth, Object k, Class<? > kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)// The current node hash value is greater than the given hash value, enter the left node
p = pl;
else if (ph < h)// The current node is less than the given hash value, enter the right node
p = pr;
else if((pk = p.key) == k || (k ! =null && k.equals(pk)))// If the current node is equal to the given hash value and the key is the same, the current node is returned
return p;
else if (pl == null)// If the left node is null, the right node is entered
p = pr;
else if (pr == null)// If the right node is null, the left node is entered
p = pl;
else if((kc ! =null|| (kc = comparableClassFor(k)) ! =null) && (dir = compareComparables(kc, k, pk)) ! =0)// If you sort by the comparator instead of the hash value, then the comparator returns the value to decide to enter the left and right nodes
p = (dir < 0)? pl : pr;else if((q = pr.find(h, k, kc)) ! =null)// If the keyword is found in the right node, return the current node directly
return q;
else// Enter the left node
p = pl;
} while(p ! =null);
return null;
}
Copy the code2.4 the remove ()
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null.false.true)) = =null ?
null : e.value;
}
Copy the code final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// Check whether table exists, data element >0, index element exists
if((tab = table) ! =null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) ! =null) {
Node<K,V> node = null, e; K k; V v;
// check that p is consistent with the data passed in
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
// get p data
node = p;
else if((e = p.next) ! =null) {// The data of the next node of p is inconsistent with that of P
// Check whether the data structure of p is a red-black tree
if (p instanceof TreeNode)
// Red-black tree, call find to find node
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
/ / list
do {
// loop to find the same data as e
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while((e = e.next) ! =null); }}// Determine the obtained data
if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
// Delete data according to red-black tree
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//node=p, then pointer to the next node after p, to delete node
tab[index] = node.next;
else// node= p.ext, so node is killed
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
returnnode; }}return null;
}
Copy the codeThis method is similar to the put/get method above, which is to obtain the hash value, and then find the node according to the hash value and Key, delete, explore a lot of fun.
2.5 the clear ()
public void clear(a) {
Node<K,V>[] tab;
modCount++;
if((tab = table) ! =null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null; }}Copy the codeThis is a straightforward way to iterate over the table and set the value of the table to NULL.
In fact, there are only a few common methods of HashMap, you know?
Three, question and answer small knowledge
3.1 Why Do I Always Use String and Integer for keys
In the syntax of a HashMap, any object can be a Key. For example, Integer, Long, String, and Object. But in practice, String is most commonly used as the Key.
- They are all final modified classes that are immutable, ensuring that keys cannot be modified and that hash values cannot be obtained differently.
- Internally, they override equals(), hashCode(), etc., to follow the internal specification of HashMap.
- They have their own separate properties, and they are placed in the constant area (to quickly determine whether they are equal or not).
3.2 When can HashMap be expanded?
There is a paragraph in the put method above
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {...if(++size > threshold) resize(); . }Copy the codeIf the map elements are greater than threshold = Capacity (current map size) x Load factor(default: 0.75).
Call resize() to expand capacity
static final int MAXIMUM_CAPACITY = 1 << 30;
final Node<K,V>[] resize() {
...
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold}...Copy the code>>: in binary form, all digits are moved to the left by the corresponding digit, the higher digit is moved out (discarded), and the lower digit is filled with zero. Move oldCap 1 bit to the left.
Limitation: cannot exceed a maximum of 2 to the 30th power
3.3 Why is expansion 2 to the NTH power?
For efficient access, a HashMap should have as few collisions as possible. The idea is to distribute the data as evenly as possible, with each list roughly the same length.
For example, hashmap.get (“name”).hashcode ()=773564.
773564 to binary: 10111100110110111100
Modulus operation
Modulo operation: Obviously, when the hashmap size is not 2 to the NTH power, there are more hash collisions.
tab[(n - 1) & hash])
Copy the codeIn hash algorithms, in order to distribute elements more evenly, modulus calculation is often used. In hashMap, (n-1) & hash is used instead of hash%n for modulus calculation. The reason is that in computers, ampersand is much more efficient than %; Note that (n-1) & hash is equivalent to hash%n only if the capacity is 2 to the NTH power, which is why the initial capacity of hashMap initialization must be 2 to the NTH power.
3.4 Why do 16 bits higher or 16 bits lower before modular operation?
Due to hashCode and (length-1) operations, length is mostly less than 2 to the 16th power. So the lower 16 bits of HashCode (or even lower) are always involved. If the higher 16 bits were involved, it would make the resulting index more hashed.
3.5 What methods should be implemented if the key in a HashMap is the defined entity class type?
// The equals(), hashCode() methods are not overridden
System.out.println("Unoverride equals(), hashCode(), etc.");
HashMap<User,String> userMap = new HashMap<>();
User userQin = new User(Ying zheng "".20);
userMap.put(userQin,The First Emperor of Qin);
// When you define MapUser and put the data does not change, map.get can get the data
System.out.println(userMap.get(userQin));/ / the qin shi huang
System.out.println("Age20:"+userQin.hashCode());//Age20:1531333864
// When mapUser. age changes, map. get cannot get data
userQin.age=25;
System.out.println("Age25:"+userQin.hashCode());//Age25:1531333864
System.out.println(userMap.get(userQin));/ / the qin shi huang
userMap.put(new User("Liu".20),Emperor Gaozu of the Han Dynasty);
System.out.println(userMap.get(new User("Liu".20)));//null
// Override equals(), hashCode() methods
System.out.println("Override equals(), hashCode()");
HashMap<HMUser,String> hmUserMap = new HashMap<>();
HMUser hmUserLi = new HMUser("Li Shimin".20);
hmUserMap.put(hmUserLi,"Tang Taizong");
// When you define MapUser and put the data does not change, map.get can get the data
System.out.println(hmUserMap.get(hmUserLi));/ / emperor taizong
System.out.println("Age20:"+hmUserLi.hashCode());//Age20:807921772
// When mapUser. age changes, map. get cannot get data
hmUserLi.age=25;
System.out.println("Age25:"+hmUserLi.hashCode());//Age25:807921777
System.out.println(hmUserMap.get(hmUserLi));//null
hmUserMap.put(new HMUser("Zhu Yuanzhang".20),"Ming Tai Zu");
System.out.println(hmUserMap.get(new HMUser("Zhu Yuanzhang".20)));/ / Ming emperor
Copy the code-
Without overriding equals(), hashCode() :
- The hashCode value remains the same after the same object property is changed, which can be obtained from map.get.
- Different objects have the same attributes and cannot get values from map. get.
-
When overriding equals(), hashCode() :
-
If the same object property changes, the hashCode will also change, and the value cannot be obtained from map. get.
-
Different objects have the same properties and can get values from map. get.
-
3.6 Why is HashMap not thread-safe
-
If thread A and thread B insert at the same time and calculate the same hash value corresponding to the same array position, A writes to A node first and B writes to the same node, then B’s write operation will overwrite A’s write operation and cause A’s write data to be lost.
-
When HashMap is expanded: a new array of new capacity is generated, and all the key pairs of the original array are re-evaluated and written to the new array, and then the new array is pointed to. When multiple threads enter at the same time and detect that the total number exceeds the threshold, the resize operation will be called at the same time to generate new arrays respectively. Finally, only the new array generated by the last thread will be assigned to the bottom layer of the map, and all the other threads will be lost.
ConcrrentHashMap, ConcrrentHashMap, ConcrrentHashMap,
ConcrrentHashMap:
-
The bottom layer of the segmented array + linked list implementation, thread safety.
-
By dividing the entire Map into N segments, this provides the same thread-safety, but an n-fold increase in efficiency and a 16-fold increase by default (read operations are not locked, and the latest values are guaranteed because the Node value variable is volatile).
-
ConcurrentHashMap allows multiple modification operations to occur concurrently, and the key is the use of lock separation.
-
Some methods that span segments, such as size() and containsValue(), may need to lock the entire table instead of just one segment, which requires locking all segments sequentially and releasing all segments sequentially when done.
-
Capacity expansion: Capacity expansion within a segment (If the number of elements in a segment exceeds 75% of the length of the corresponding Entry array, capacity expansion will not be performed on the entire Map). Check whether the Map needs to be expanded before insertion to avoid invalid capacity expansion.
Lock segmentation technology: firstly, the data is divided into sections for storage, and then each section of data is equipped with a lock. When a thread uses the lock to access one section of data, the data of other sections can also be accessed by other threads.
ConcurrentHashMap Divides the hash table into 16 buckets by default. Common operations such as GET, PUT, and remove lock only the buckets that are currently used. As a result, a single thread can now be entered by 16 writers at the same time, and the concurrency improvement is noticeable.