instructions

This chapter is a HashMap summary, is jdK1.8 version.

Inherit the figure

Its inheritance system is relatively simple

Throw out problem

What is the internal data structure like?
When was the expansion mechanism expanded and by how much?
Whether the key or value can be null.
Is it thread safe?

HashMap collection description

Create a HashMap collection object

Map<String,Integer> map = new HashMap<>();
Copy the code

attribute

// Default initial capacity, use the left displacement calculation, 1 = x; 4 = n; DEFAULT_INITIAL_CAPACITY = x * 2 of n squared
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// Maximum capacity --1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;
// Default load factor (load factor), used for capacity expansion
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
// As a judgment, switch to a red-black tree when the node element in a bucket array is larger than 8
static final int TREEIFY_THRESHOLD = 8;
// As a judgment, when a node is less than 6, it is converted to a linked list, provided that it is currently a red-black tree
static final int UNTREEIFY_THRESHOLD = 6;
// If the bucket array capacity is smaller than the value, the bucket array capacity is expanded preferentially rather than treed
static final int MIN_TREEIFY_CAPACITY = 64;
// Array of elements (buckets)
transient Node<K,V>[] table;
// Used as an iteration
transient Set<Map.Entry<K,V>> entrySet;
// Number of elements
transient int size;
// Count the number of map changes
transient int modCount;
// The next size value to resize (capacity x load factor) and the maximum number of key-value pairs that the current HashMap can hold. If the value exceeds this value, you need to expand
int threshold;
// Load factor (load factor)
final float loadFactor;
Copy the code

The constructor

/* initialCapacity: indicates the initialCapacity. LoadFactor: indicates the loadFactor
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)  < 0 throws an exception
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  // If the initial capacity is greater than or equal to the maximum capacity, the maximum capacity is assigned to the initial capacity
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  // Check whether loadFactor is valid
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;  // Assign the default DEFAULT_LOAD_FACTOR to the loadFactor variable
  TableSizeFor (initialCapacity) The method returns a value greater than initialCapacity and the nearest power of 2. For example, if initialCapacity is 29, the value returned is 32**/
  this.threshold = tableSizeFor(initialCapacity);
}
// define the initialCapacity
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR); // Call another constructor
}
// Construct with no arguments
public HashMap(a) {
  // all it does here is assign the default default loadFactor to the loadFactor variable
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

// Add data from another map collection to the current map collection
public HashMap(Map<? extends K, ? extends V> m) {
  this.loadFactor = DEFAULT_LOAD_FACTOR;
  putMapEntries(m, false);
}
Copy the code

TableSizeFor (int cap) returns the second power of the given target capacity.

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code

Said there are two points is a unsigned moves to the right, also called logical moves to the right > > > is a | called or operators, all of them are an operator

Can have a look at www.cnblogs.com/chuijingjin… Description of logical right shift

| : if the corresponding bit is 0, the result is 0, or 1, such as: turn the decimal binary calculation

13 | do 01 "11, 1111, 11: after the conversion of the result, and then put it into decimal is 15Copy the code

Can also refer to the novice tutorial methods: www.runoob.com/java/java-o…

A brief description of the collection CRUD

increase

public V put(K key, V value) {
            // The main addition method, which will be highlighted later
    return putVal(hash(key), key, value, false.true);
}
Copy the code

delete

// Remove the corresponding key value by key
public V remove(Object key) {
    Node<K,V> e;
    // removeNode() the main operation
    return (e = removeNode(hash(key), key, null.false.true)) = =null ?
        null: e.value; Return the value of the deleted key}Copy the code

change

The hash value of the key is used to find the corresponding position and overwrite the corresponding value

check

// Get value by key
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
Copy the code

The core content expansion mechanism of HashMap

The above is just a brief description, but the main thing is its capacity expansion mechanism and internal implementation. Let’s explore this by adding an element

// Add method
public V put(K key, V value) {
            // putVal() add method
    return putVal(hash(key), key, value, false.true);
}

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

// Hash value, key key, value value to put in, onlyIfAbsent If true, do not change the existing value
// If execit is false, the table is in create mode.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
      /* tab; TAB [I = (n-1) &hash] n: length of the hashMap, I: array bucket table */
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // This judgment is used to initialize the table variable when adding data for the first time
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length; // resize() initializes and expands the capacity of the table
  / * this judgment is equivalent to find the key of the node position in the TAB array barrels, the value of the current index will be assigned to p, then use p for judgment, will is null, if the null key | value into the TAB in the [I] * /
  if ((p = tab[i = (n - 1) & hash]) == null)  // The same key is added when the bucket array does not have this
    // Store data
    tab[i] = newNode(hash, key, value, null);
  else {
    // e: the temporary node stores the data of the previous node. If the value is not null, a key exists in the current linked list data
    // K: stores the key of the previous node
    Node<K,V> e; K k;
    // Check whether it is the same as the last key
    if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
      e = p; // If not, send the data of the previous node p to e
    // Check whether the last node is a red-black tree node
    else if (p instanceof TreeNode)
      // If it is a red-black tree node, add data after the red-black tree node, insert method also check whether the same key exists
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // If the hash value of the key is the same, the content of the key is different, and it is not a red-black tree
      for (int binCount = 0; ; ++binCount) {
        // the p variable preserves the previous node, while p.ext finds the next node
        if ((e = p.next) == null) { // This judgment is definitely true, the last node's, the next node has no,
          // This step assigns the new node to the next node of the previous node
          p.next = newNode(hash, key, value, null);
          // If the list length is greater than or equal to the default value of TREEIFY_THRESHOLD, 8
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            // The tree operation, the number of methods must meet the conditions, explained later
            treeifyBin(tab, hash);
          break; // Break the loop
        }
        // If the key of the next node in the list has the same hash value, break the polling loop
        // Then do the following if (e! = null) where the value is replaced
        if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
          break; p = e; }}PutTreeVal (); putTreeVal(); putTreeVal() After the judgment of the above two situations, a result is obtained. If E! If = null, duplicate keys exist, and the old value is replaced by the new value */
    if(e ! =null) { // existing mapping for key
      V oldValue = e.value; // Get value
      if(! onlyIfAbsent || oldValue ==null)
        e.value = value; // Reassign the new value to the value on the node with the same key
      afterNodeAccess(e);
      return oldValue; // Returns the value before it was replaced}}// Number of changes ++
  ++modCount;
  // The actual length ++ needs to be expanded if it is larger than the next size to be adjusted
  if (++size > threshold)
    resize();  / / capacity
  afterNodeInsertion(evict);
  // Added successfully
  return null;
}
Copy the code

The putVal() method roughly does that

When the table is null (the first time), initialize the table bucket array with resize()
Is the hash value of the added data key the same? Or the hash value of keys is the same but the key value is different?
- The hash value of the key is the same: it finds the area of the key with the same hash value, determines whether the hash value is equal to the key value, sets the result to true, and assigns the new value to the old value, thus achieving the effect of unchanged key and value replacement
- If the hash value of the key is the same but the key value is different, the hash value of the key is foundtab[i = (n - 1) & hash]If the hash value of a region is the same as that of a key, the result is false, else is used. If the region is the same as that of a key, and the next node is null, the data is stored in the next node in the region.In simple terms, data with the same hash value but different keys will be placed in the data of the next node in the region created with the same hash valueSo it’s a linked list
If the hash value of the key is the same but the key value is different, it will have a check to see if the length of the list is greater than or equal to the value of the TREEIFY_THRESHOLD(8) property. If so, it will turn the list into a red-black tree
If the length of the hashMap is greater than threshold(the initial value is 12), the hashMap should be expanded

Resize () Expansion method -HashMap expansion mechanism

In add data to add data for the first time and every time add data to the end of a judgment, a judgment is whether the table attribute value is null and at the end of each time add data has a judge whether the number of elements in the collection, super threshold value (the value is as a judge whether need to increase the value of the) initial expansion sets the threshold to 12 for the first time.

final Node<K,V>[] resize() {
  // Assign the table bucket array to oldTab, which is equivalent to an old bucket array
  Node<K,V>[] oldTab = table;
  // Get the bucket array size
  int oldCap = (oldTab == null)?0 : oldTab.length;
  // Get the threshold, which is simply one of the judgment conditions for capacity expansion
  int oldThr = threshold;
  // Define a new bucket array size, and a new threshold of 0
  int newCap, newThr = 0;
  // If the length of the old bucket array is greater than 0
  if (oldCap > 0) {
    // Check whether the length of the old bucket is greater than or equal to MAXIMUM_CAPACITY and the maximum capacity of HashMap
    if (oldCap >= MAXIMUM_CAPACITY) {
      // Assign the major values of integer.max_value to the load factor (threshold) and perform the expansion operation
      threshold = Integer.MAX_VALUE;
      // Return the old bucket array
      return oldTab;
    }
   // Calculate the size of the new capacity and the new threshold by twice of the old capacity and the old threshold
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
      newThr = oldThr << 1; // double threshold
  }
  // If the old threshold is greater than 0
  else if (oldThr > 0) // initial capacity was placed in threshold
    // Assign the old threshold to the new bucket array capacity
    newCap = oldThr;
  else {               // zero initial threshold signifies using defaults
    // DEFAULT_INITIAL_CAPACITY The default value is 16. Assign this value to newCap
    newCap = DEFAULT_INITIAL_CAPACITY;
    // newThr = (capacity * load factor)
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  // If the new threshold is equal to 0, calculate the new threshold according to the threshold calculation formula
  if (newThr == 0) {
    // calculate the new threshold (threshold) (capacity size * loadFactor) loadFactor = loadFactor = loadFactor
    float ft = (float)newCap * loadFactor;
    // Check whether the new capacity is smaller than the maximum default initial capacity and whether the new threshold is smaller than the maximum default initial capacity
    // Assign the new ft threshold to newThr for true
    // If false, assign integer. MAX_VALUE to newThr's new threshold
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  // Assign a new load factor (threshold) to threshold for next expansion
  threshold = newThr;
  // Indicates that the warning is ignored
  @SuppressWarnings({"rawtypes","unchecked"})
  // Create a new bucket array, bucket initialization is done here newCap=16
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  // Assign the new bucket to the attribute table
  table = newTab;
  // Old buckets are not null
  if(oldTab ! =null) {
    for (int j = 0; j < oldCap; ++j) {
      Node<K,V> e; // Temporarily store node variables
      // Check that elements in the bucket array are not null
      if((e = oldTab[j]) ! =null) {
        oldTab[j] = null; // Set to null for garbage collection
        if (e.next == null) // Determine the next node and so on to null
          // Put e in the new capacity [e.hash (newcap-1)]
          newTab[e.hash & (newCap - 1)] = e;
        // Check whether e is a red-black tree
        else if (e instanceof TreeNode)
           // When remapping, the red-black tree needs to be split
          ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
          Node<K,V> loHead = null, loTail = null;
          Node<K,V> hiHead = null, hiTail = null;
          Node<K,V> next;
           // Iterate through the list and group the list nodes in the same order
          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);
            // Map the grouped list to the new bucket
          if(loTail ! =null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if(hiTail ! =null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
 // Return the new bucket
  return newTab;
}
Copy the code

Resize () does a few things

Figure out what the new capacity (newCap) of the bucket array is and what the new threshold (newThr) is
Assign its calculated capacity and threshold value to the HashMap class attribute and make it the initialization capacity of bucket array :16. Expand the capacity in the form of 2 to the NTH power
Remap the key-value pair node to the new bucket array. If the node is of TreeNode type, you need to split the bonus black tree. If it is a common node, the nodes are grouped in the original order, and the details are left to you.

Problem solving

What is the internal data structure like?
- Array + linked list + red-black tree
When was the expansion mechanism expanded and by how much?
- When adding data for the first time, the initial capacity is 16. The subsequent capacity expansion is 2 to the NTH power
Whether the key or value can be null.
- Can be null
Is it thread safe?
- Thread insecurity

conclusion

HashMap is one of the implementation classes of the Map interface class.
Its keys and values can be stored as null values, but HashMap allows a maximum of one record to be null and multiple records to be NULL
It is a thread-unsafe collection
The initial information is that the bucket array is 16 size, threshold(threshold = (capacity size * loadFactor)) is 12, loadFactor(loadFactor) is 0.75f,
When will the capacity be expanded?
- Capacity expansion, default initial bucket array size, and threshold(threshold) size when adding data for the first time
- When size > threshold and length is greater than the threshold, expand the capacity
- Expansion bucket length in the form of 2 to the NTH power
```
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold
    // specify a method in the resize() method.
Copy the code
```
A HashMap stores an array of structures + a linked list + a red-black tree
If the number of elements in the list is greater than 8, the list is converted to a red-black tree structure. If the number of elements in the list is greater than 8, the index between 0 and 7 is 8, so the 8 is the number of elements in the list.
```
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
Copy the code
```
Here’s a caveat:
- In treeifyBin (TAB, hash); There’s another judgment in the method
```
/ / meet this condition will be expansion the if (TAB = = null | | (n = TAB. Length) < MIN_TREEIFY_CAPACITY)Copy the code
```
- If the list length is greater than 8 (default value) and the array length is greater than 64, convert the list to a red-black tree; otherwise, expand the list

How to calculate the location of the bucket array?

 p = tab[i = (n - 1Hash] p = bucket [I = (Bucket length size -1) and the hash value of the operation key]// Hash (bucket length -1) and key to find where the elements are placed in the bucket array
Copy the code

If the hash value of the key is the same, but the key value is different, it puts the data into the next node in the hash value
You can try the same hash value of key but different value, see where the second value is stored, use idea debug to check
```
Map<String, Object> map1 = new HashMap<>();
map1.put("Call"."2");
map1.put("Important"."4");
Copy the code
```

The illustration

Throw in chicken soup

When you hesitate, in fact, the heart has already decided.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Java Collection series – Internal exploration of HashMap

HashMap collection description

attribute

The constructor

A brief description of the collection CRUD

The core content expansion mechanism of HashMap

conclusion

Java Collection series – Internal exploration of HashMap

HashMap collection description

attribute

The constructor

A brief description of the collection CRUD

The core content expansion mechanism of HashMap

conclusion

Related Posts

Java reflection mechanism

JVM garbage collector and garbage collection algorithms

Learning Python: Classes and instances