Underlying principles of HashMap1.7

1. Data structure

The underlying data structure of HashMap1.7 is realized by array + linked list, also known as the zipper method.

structure describe
Array (primary) Core bottom layer: Table [], also known as hash array

Array subscript (indexFor) : Evaluates the hash based on the key value and calculates & with array leng-1

Entry: 1 key-value pair =1 linked list (header)

Array size: Capacity
Linked list (pair) Bucket per linked list: The bucket of a hash table

Node value of a linked list: a key-value pair

List length: The size of the bucket
Store the object Entry class, attributes include: key, value, next node

2. Storage process

  1. Receive key value pairs
  2. Computes the hash value based on the key in the key-value pair
  3. Evaluates the array subscript of the storage based on the hash value
  4. Check whether the position has a hash conflict.
  5. If a conflict occurs, the data in the original location is moved to the linked list and the key-value pairs are stored in an array
  6. If no conflicts occur, the key-value pair is stored directly at that location

3. Use the API

V get(Object key); V put(K key,V value); Void putAll(Map<? extends K, ? extends V> m); V remove(Object key); // Copy key pairs from the specified Map to the Map. // Delete the Boolean containsKey(Object key); // Check whether there is a key-value pair for the key; Returns true Boolean containsValue(Object value); // Check whether there is a key-value pair for this value; Set<K> keySet(); Set Collection<V> values(); // Single value sequence, generate a Collection void clear() for all values; // Delete all key pairs int size() from the hash table; // Return the number of key-value pairs in the hash table = key-value pairs in the array + key-value pairs in the linked list Boolean isEmpty(); // Check whether HashMap is empty; Null if size == 0Copy the code

4. Important parameters

Static final int DEFAULT_INITIAL_CAPACITY = 1<<4; static final int MAXIMUM_CAPACITY = 1 << 30; LoadFactor: the loadFactor defaults to 0.75f final float loadFactor; Static final float DEFAULT_LOAD_FACTOR=0.75f threshold: Capacity expansion threshold = capacity x load factor. If the hash table size >= capacity expansion threshold, the hash table will expand. Int threshold; Table: Array transient Entry<K,V>[] TABLE = (Entry<K,V>[]) EMPTY_TABLE; Size: transient int size (array key pairs + all linked list key pairs);Copy the code

5. Source code analysis

1. Structural parameters

There are four constructors in HashMap:

  • Default constructor (no arguments)
  • Specifies the “capacity size” constructor
  • Constructor that specifies “capacity size” and “load factor”
  • Contains the “submap” constructor
HashMap<String,Integer> map = new HashMap<String,Integer>(); /* * Constructor 1: default constructor (no arguments) */ public HashMap() {// Actually call constructor 3: Constructor this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR) that specifies "capacity size" and "load factor"; } /* * constructor 2: Public HashMap(int initialCapacity) {// Actually call the constructor this(initialCapacity, DEFAULT_LOAD_FACTOR); } /* * constructor 3: Constructor */ public HashMap(int initialCapacity, Float loadFactor) {// The maximum capacity of HashMap can only be MAXIMUM_CAPACITY if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // set loadFactor this.loadFactor = loadFactor; // set capacity expansion threshold = initialCapacity // note: this is not a real threshold, but to expand the table. Threshold = initialCapacity will be recalculated later. init(); // An empty method for future subobject extensions} /* * constructor 4: constructor containing "submap" * that is, the constructed HashMap contains the mapping of the passed Map * loading factor & capacity = default */ public HashMap(Map<? extends K, ? Extends V> m) {this(math.max ((int) (m.size()/DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // This method is used to initialize arrays & thresholds, as described below: inflateTable(threshold); PutAllForCreate (m); }Copy the code

2. Put () method flow

  1. Check whether the table is initialized. If not, initialize it
  2. Check whether the key value is null. If it is null, store the key-value to the first position in the array table
  3. If the value is not null, the hash value is calculated based on the key value
  4. Perform and operations on the hash value of the key and (table.length-1) to obtain the position in the array table corresponding to the key
  5. Check whether the key exists in the array Table. If the key exists, replace the old value with the new value
  6. If the key-value does not exist, add it to the table
Map. Put (" zhang SAN ", 1); public V put(K key, If (table == EMPTY_TABLE){inflateTable(threshold); if(table == EMPTY_TABLE){inflateTable(threshold); // select * from table[0] where key == null Table [0]) */ if (key == Null) return putForNullKey(value); // method 2 /* * if key ≠ null, * Calculates the hash value based on the key and then performs the * and operation with (array.length-1) to obtain the hash position in the array table corresponding to the key */ int hash = hash(key); Int I = indexFor(hash,table.length); For (Entry<K,V> e = table[I]; for (Entry<K,V> e = table[I]; e ! = null; e = e.next) { Object k; // If the key already exists (key-value already exists), With a new value to replace the old value if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {V oldValue = e.v alue. e.value = value; e.recordAccess(this); return oldValue; // return the old value}} modCount++; // If the key does not exist, add "key-value" to the table addEntry(hash, key, value, I); // return null; } method 1: inflateTable(threshold) private void inflateTable(int toSize){int capacity = roundUpToPowerOf2(toSize); // Convert the incoming capacity to the minimum quadratic power greater than the capacity threshold = (int) math. min(capacity*loadFactor,MAXIMUM_CAPACITY + 1); // Recalculate threshold table = new Entry[capacity]; Table} private static int roundUpToPowerOf2(int number){roundUpToPowerOf2(int number){ Return number >= MAXIMUM_CAPACITY? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; } putForNullKey(value) private V putForNullKey(V value){putForNullKey(V value){putForNullKey(value) private V putForNullKey(V value){ Replace the old value with the new value. Return the old 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; } // If not, call addEntry(), encapsulate the value of the empty key & into Entry, and place it in table[0] addEntry(0,null,value,0); Static final int hash(int h){h ^= k.hash (); static final int hash(int h){h ^= k.hash (); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); Static final int hash(Object key){int h; static final int hash(Object key){int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } Method 4: IndexFor (hash,table.length) static int indexFor(int h,int length){ Return h & (length-1); return h & (length-1); } Method 5: addEntry(hash, key, value, i) void addEntry(int hash, K key, V value, int bucketIndex){ if ((size >= threshold) && (null ! = table[bucketIndex])) {// resize(2 * table.length); // Recalculate the hash value of the Key hash = (null! = key) ? hash(key) : 0; // Recalculate the hash array subscript bucketIndex = indexFor(hash, table.length); } // Create a new array element (hash, key, value, bucketIndex) and add it to the array. Method 6: createEntry(hash, key, value, bucketIndex); Void createEntry(int hash, K key, V value, int bucketIndex) {// Save the original Entry in the table. Entry<K,V> e = table[bucketIndex]; // Create an Entry at this position in the table: Insert the key-value pairs of the original header position into the next node (linked list), and insert the key-value pairs into the header position (array) -> to form a linked list. Old entries are added to the linked list (resolving Hash conflicts) table[bucketIndex] = New Entry<>(Hash, key, value, e); // add size++ to the hash table's key-value pair count; }Copy the code

3. Resize () method flow

  1. Insufficient capacity was found while inserting key/value pairs
  2. Save the old array
  3. Create an array based on the new capacity (2x)
  4. Iterate over each data in the old array and calculate where each data is stored in the new array
  5. Move each piece of data from the old array to the new array
  6. Reference the new array table to the Table property of the HashMap
  7. Reset the capacity expansion threshold
Void resize(int capacity){// Save the old array Entry[] oldTable = table; Int oldCapacity = oldtable.length; If (oldCapacity == MAXIMUM_CAPACITY) {threshold = integer.max_value; if (oldCapacity == MAXIMUM_CAPACITY) {threshold = integer.max_value; if (oldCapacity == MAXIMUM_CAPACITY) {threshold = integer.max_value; return; } // Create an array based on the new capacity (2x capacity), that is, new table Entry[] newTable = new Entry[newCapacity]; // transfer(newTable) from the old array to the newTable; Table = newTable; // Table = newTable; // Reset threshold = (int)(newCapacity * loadFactor); } Transfer (newTable) void Transfer (Entry[] newTable){// SRC references the old array Entry[] SRC = table; Int newCapacity = newtable. length; For (int j = 0; for(int j = 0; j < src.length; J ++){// Get each element on the old array Entry<K,V> e = SRC [j]; if (e ! SRC [j] = null; Do {// iterate through the list starting with the array element // Note: When transferring the list, it is a single linked list, so save the next node. Otherwise, the list will be disconnected after the transfer. // recalculate the location of each element int I = indexFor(e.hash, newCapacity); E.next = newTable[I]; newTable[i] = e; // Access the next Entry chain, and so on until all the nodes on the list have been traversed e = next; }while(e ! = null) } } }Copy the code