HashMap stores the structure

It contains an Entry[] table array.transient Entry[] table;*(TRANSIENT: indicates that it cannot be serialized)*Entry stores key-value pairs. It contains four fields, and Entry is a linked list. That is, each position in the array is treated as a bucket, and each bucket holds an Entry list. A HashMap uses the zipper method to resolve conflicts. The same list holds entries with the same hash value and hash bucket modulus.

Normal operation

  • final K getKey();
  • The final V getValue ();
  • final V setValue(V newValue);
  • final boolean equals(Object o);
  • final int hashCode();
  • final String toString();
static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash; Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() {return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (! (o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 ! = null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 ! = null && v1.equals(v2))) return true; } return false; } public final int hashCode() { return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()); } public final String toString() { return getKey() + "=" + getValue(); }}Copy the code

Insert PUT operation

  • To insert an array, the hash value and hash table are used to calculate the number of the bucket.

  • The head insertion method of linked list is used for insertion.

  • HashMap allows you to insert key-value pairs with null keys. However, because of the null hashCode() method, we cannot determine the bucket subscript corresponding to the key value. We can only specify the 0th bucket to hold the key-value pair with the null key.

public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); If (key == null) return putForNullKey(value); int hash = hash(key); Int I = indexFor(hash, table.length); Value for (Entry<K,V> e = table[I]; e ! = null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // Insert a new key-value pair addEntry(hash, key, value, I); return null; }Copy the code
private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e ! = null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }Copy the code
void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null ! = table[bucketIndex])) { resize(2 * table.length); hash = (null ! = key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; Table [bucketIndex] = new Entry<>(hash, key, value, e); size++; }Copy the code

capacity

Let the table length of HashMap be M, and the number of key-value pairs that need to be stored be N. If the hash function meets the requirement of uniformity, then the length of each linked list is about N/M, so the search complexity is O(N/M). To keep the cost of finding down, N/M should be as small as possible, so M should be as large as possible, which means the table should be as large as possible.

  • HashMap uses dynamic expansion to adjust the array length according to the current number of key-value pairs, which ensures both spatial and temporal efficiency. (HashMap expansion does not wait until the array is full, because elements are inserted into the list and will never be full, so there is a threshold, which will be expanded when it is equal to it.)

  • Capacity is normally 2 to the power of n. Even if the input is not 2 to the power of n, it automatically converts the input to 2 to the power of n. The reason is that the bit operation is used to replace the modulus operation, which can greatly reduce the complexity of recalculating the bucket subscript operation. (Bitwise operations only work in base 2, so 2 to the n is required);

  • When capacity expansion is required, use resize() to double capacity. Capacity expansion requires that all key pairs of oldTable be inserted into newTable again, which takes a long time.

  • If a bucket contains a list with a length greater than or equal to 8, the list is converted to a red-black tree.

parameter meaning
capacity Table capacity. The default value is 16. Note that capacity must be 2 to the n.
size Number of key-value pairs.
threshold Size threshold. If the size is greater than or equal to threshold, capacity expansion must be performed.
loadFactor Threshold = (int)(capacity* loadFactor). 
static final int DEFAULT_INITIAL_CAPACITY = 16;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient Entry[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;

Copy the code
void addEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 if (size++ >= threshold)
 resize(2 * table.length);
}

Copy the code
void resize(int newCapacity) {
 Entry[] oldTable = table;
 int oldCapacity = oldTable.length;
 if (oldCapacity == MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
 return;
 }
 Entry[] newTable = new Entry[newCapacity];
 transfer(newTable);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
 Entry[] src = table;
 int newCapacity = newTable.length;
 for (int j = 0; j < src.length; j++) {
 Entry<K,V> e = src[j];
 if (e != null) {
 src[j] = null;
 do {
 Entry<K,V> next = e.next;
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;
 } while (e != null);
 }
 }
}

Copy the code

Comparison to Hashtable **

Hashtable uses synchronized for synchronization. A HashMap can insert entries with null keys. The iterator for a HashMap is the fail-fast iterator. A HashMap does not guarantee that the order of elements in the Map will remain constant over time.

conclusion

Welcome to pay attention to the public number: the future has light, receive a line of large factory Java interview questions summary + the knowledge points learning thinking guide + a 300 page PDF document Java core knowledge points summary!