The content of this article is a record of the study, which may be insufficient.
HashMap in JDK1.7
JDK1.7’s hashMap consists of arrays and linked lists
/** 1 << 4, represents 1, moves 4 bits to the left, becomes 10000, i.e. 16, in binary form, The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. * Static final int MAXIMUM_CAPACITY = 1<<30; //1 073 741 824 /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75 f; /** * An empty table instance to share when the table is not inflated. */ static final Entry<? ,? >[] EMPTY_TABLE = {}; /** * The table, resized as require. Length MUST Always be a power of two. The length must be a power of two. */ transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; /** * The number of key-value mappings contained in this map. /** * The next size value at which to resize (capacity * load factor). * @serial */ // If table == EMPTY_TABLE then this is the initial capacity at which the // table will be created when inflated. int threshold; /** * The load factor for the hash table. * * @serial */ final float loadFactor; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). * record hashMap element is modified the number of * / transient int modCount;Copy the code1: DEFAULT_INITIAL_CAPACITY, which is the default initial capacity of the hashMap and must be a power of 2.
2: MAXIMUM_CAPACITY: indicates the maximum capacity supported by hashMap.
3: DEFAULT_LOAD_FACTOR, the default load factor for hashMap, has a value of 0.75, which determines the density of the hashMap data.
4: Entry<K,V>[] table, hashMap array, you can adjust the size according to your needs, the length must be a power of 2.
5: size, which records the number of elements in the hashMap.
6: threshold: adjusts the value of hashMap, that is, capacity x load factor.
7: loadFactor: loadFactor that can be adjusted.
8: modCount, which counts the number of times the hashMap structure has been modified.
The hashMap source code has four constructors that are initialized to know the size of the capacity and load factor.
/** does two things: Init () * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); If (initialCapacity > MAXIMUM_CAPACITY) // Limit the maximum capacity initialCapacity = MAXIMUM_CAPACITY; If (loadFactor < = 0 | | Float. The isNaN (loadFactor)) / / check loadFactor throw new IllegalArgumentException (" Illegal load factor: " + loadFactor); LoadFactor = loadFactor; loadFactor = initialCpacity; loadFactor = loadFactor; // Record loadFactor threshold = initialCapacity; // Initial threshold=initialCapacity=16 init(); } /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default Load factor (0.75). */ public HashMap() {//16 0.75 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * Constructs a new <tt>HashMap</tt> with the same mappings as the * specified <tt>Map</tt>. The <tt>HashMap</tt> Is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified <tt>Map</tt>. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }Copy the codeLet’s look at the put method:
public V put(K key, V value) { if (Entry<K,V>[] table == EMPTY_TABLE) { inflateTable(threshold); } putForNullKey(value); putForNullKey(value); putForNullKey(value); int hash = hash(key); Int I = indexFor(hash, table.length); For (Entry<K,V> e = table[I]; e ! = null; E = e.next) {// Iterate over the list Object k at subscript I; If (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {/ / if the key values are the same, to cover the old value, return the new value V oldValue = e.v alue. e.value = value; // New value overrides old value e.reordaccess (this); //do nothing return oldValue; // return the old value}} modCount++; // Number of changes +1, similar to a version number addEntry(hash, key, value, I); return null; }Copy the codeYou can see that when the table is empty, a method is called:
private void inflateTable(int toSize) { // Find a power of 2 >= toSize int capacity = roundUpToPowerOf2(toSize); // threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; // Initialize the table initHashSeedAsNeeded(capacity); }Copy the codeRoundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2
When a hashMap puts an element, it calculates the hash value based on the hash operation, then modulates the hash value and the length of the table to calculate the subscript of the element in the table. If the keys are identical, the original values are overwritten, and if they are different, the elements are added to the linked list.
/** static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }Copy the code/** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null ! = table[bucketIndex])) {// If size is greater than threshold && table has an entry in index resize(2 * table.length); Hash = (null! = key) ? hash(key) : 0; // Recalculate the hash value bucketIndex = indexFor(hash, table.length); // recalculate subscript} createEntry(hash, key, value, bucketIndex); /** * Like addEntry except that this version is used when creating entries * as part of Map construction or "pseudo-construction" (cloning, * deserialization). This version needn't worry about resizing the table. * * Subclass overrides this to alter the behavior of HashMap(Map), * clone, and readObject. */ void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; Table [bucketIndex] = new Entry<>(hash, key, value, e); // put the new entry into the array. Next points to the old table[I] size++; // Change the number of elements in map}Copy the codeWhen the number of put elements is greater than 12, that is, the capacity of the hashMap * the calculated value of the load factor, then the capacity will be expanded. Otherwise, expand the capacity to twice the original capacity. After the expansion, you need to recalculate the hash and subscripts. The table length has changed, so you need to recalculate.
Let’s look at the get method:
public V get(Object key) { if (key == null) return getForNullKey(); Entry<K,V> entry = getEntry(key); return null == entry ? null : entry.getValue(); } /** * Returns the entry associated with the specified key in the * HashMap. Returns null if the HashMap contains no mapping * for the key. */ final Entry<K,V> getEntry(Object key) { if (size == 0) { return null; } int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e ! = null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) return e; } return null; }Copy the codeThe get method also computes the hash, then the subscript, and then finds the element.
HashMap in JDK1.8
The biggest difference between hashMap and 1.7 in JDK1.8 is the introduction of red-black trees
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
Copy the code/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.6f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. * */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64; /** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ 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() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { 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) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }}Copy the codeLet’s look at the put method:
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } /** * Implements Map.put and related methods. Add element * * @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; If ((TAB = table) = = null | | (n = TAB. Length) = = 0) / / if the table is null n = (TAB = the resize ()). The length; //resize if ((p = TAB [I = (n-1) & hash]) == null) // Resize if ((p = TAB [I = (n-1) & hash]) == null) // Resize if ((p = TAB [I]) == null) // Resize if (p = TAB [I]) == null) // Resize if (p = TAB [I] = newNode(hash, key, value, null); // Create a new node and place it in an array else {// If p! =null Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key ! = null &&key. equals(k)))) // e = p; Else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).puttreeval (this, TAB, hash, key); TreeNode for (int binCount = 0; ; ++binCount) {if ((e = p.ext) == null) {if (e = p.ext) == newNode(hash, key, value); // Add a node to the end if (binCount >= treeify_threshold-1) // -1 for 1st // If the list length >= 8 treeifyBin(TAB, hash); // Convert the list into a common black tree break; } if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) // If keys are the same, exit loop break; p = e; } } if (e ! = null) { // existing mapping for key V oldValue = e.value; if (! onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }Copy the codeIf the length of the list is greater than 8, that is, the value of TREEIFY_THRESHOLD in the source code, then the list will be converted to a red-black tree structure. If the number of elements in a red-black tree is less than 6, it will be converted back to a linked list.
3: ConcurrentHashMap in JDK1.7
The difference between the ConcurrentHashMap in JDK1.7 and the HashMap in JDK1.7 is the elements stored in the array. ConcurrentHashMap is thread-safe.
public V put(K key, V value) { Segment<K,V> s; if (value == null) throw new NullPointerException(); int hash = hash(key); // Compute Hash value int j = (Hash >>> segmentShift) & segmentMask; // unsafe. getObject (Segment<K,V>) unsafe. getObject; recheck (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment s = ensureSegment(j); Return s.hash (key, hash, value, false); } final V put(K key, int hash, V value, Boolean onlyIfAbsent) {HashEntry<K,V> node = tryLock()? null : scanAndLockForPut(key, hash, value); // If tryLock succeeds, null is returned, otherwise... V oldValue; try { HashEntry<K,V>[] tab = table; int index = (tab.length - 1) & hash; HashEntry<K,V> first = entryAt(TAB, index); For (HashEntry<K,V> e = first;;) {// Start with first if (e! = null) {// If e! =null K k; If (k = e.k ey) = = key | | (e.h ash = = hash && key. Equals (k))) {/ / if the same key oldValue = e.v alue. // Get the old value if (! OnlyIfAbsent) {// Absent =false e.value = value; // override the old value ++modCount; // } break; } e = e.next; } else {// until e is null if (node! = null) // Place the element in the head of the list node.setNext(first); else node = new HashEntry<K,V>(hash, key, value, first); // create a new Entry int c = count + 1; If (c > threshold && tab.length < MAXIMUM_CAPACITY) // If the number of hashMap elements exceeds threshold, The length of the table is smaller than the maximum rehash(node) capacity. // Rehash is similar to resize, doubling the size of the table, repackaging entries, and adding the given node to the new table else // If there is still space setEntryAt(TAB, index, node); // Add the list node to index ++modCount; // change the operand count = c; // set count+1 oldValue = null; // break; } } } finally { unlock(); } return oldValue; // oldValue} private Segment<K,V> ensureSegment(int K) {final Segment<K,V>[] ss = this.segments; long u = (k << SSHIFT) + SBASE; Segment< k,V> seg; GetObjectVolatile (ss, u)) == null) {// if (seg = (Segment<K,V>) unsafe. getObjectVolatile(ss, u)) == null) {// if (seg = (Segment<K,V>) unsafe. getObjectVolatile(ss, u)) == null); // use segment 0 as prototype int cap = proto.table.length; Float lf = proto.loadfactor; float lf = proto.loadfactor; / /... int threshold = (int)(cap * lf); // Calculate threshold HashEntry<K,V>[] TAB = (HashEntry<K,V>[])new HashEntry[cap]; if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, // Segment< k,V> s = new Segment< k,V>(lf, threshold, TAB); // create segment while ((seg = (segment <K,V>) unsafe. getObjectVolatile(ss, u)) == null) { Spin the if (UNSAFE.com pareAndSwapObject (ss, u, null, seg = s)) / / if by CAS updated, retreat to break; } } } return seg; }Copy the code/** segments each element is a dedicated hashtable * The segments, each of which is a specialized hash table. */ final Segment<K,V>[] segments;Copy the codeAs you can see in 1.7, the ConcurrentHashMap array stores segments, each of which has a hashTable. When you put an element, it locks it, then evaluates the hash and subscript, which are evaluated twice, once at segments in the array and once at hashTable.
4. ConcurrentHashMap in JDK1.8
ConcurrentHashMap in JDK1.8 has the same structure as HashMap in JDK1.8, except that it is handled differently
public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); // Compute hash value int binCount = 0; for (Node<K,V>[] tab = table;;) {// spin Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) //table==null || table.length==0 tab = initTable(); InitTable else if ((f = tabAt(TAB, I = (n-1) & hash)) == null) {if (casTabAt(TAB, I, null) New Node<K,V>(hash, key, value, null)) break; } else if ((fh = f.hash) == MOVED) // If the element at subscript I is not null, And f. Hash ==MOVED MOVED = constant value -1 TAB = helpTransfer(TAB, f); // else {V oldVal = null; Synchronized (f) {// When the header element is not null and does not need to be converted to a tree, If (tabAt(TAB, I) == f) {if (fh >=0) {// If the hash value of the linked list header >=0 binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek ! = null &&key. equals(ek)))) {oldVal = e.val; if (! OnlyIfAbsent) // and not absent e.vi = value; // The old value overwrites the new value break; } Node<K,V> pred = e; Next = new Node<K,V>(hash, key, value, null); next = new Node<K,V>(hash, key, value); break; }}} else if (f instanceof TreeBin) {Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) ! = null) { oldVal = p.val; if (! onlyIfAbsent) p.val = value; } } } } if (binCount ! = 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal ! = null) return oldVal; break; } } } addCount(1L, binCount); return null; }Copy the codeWhen put elements, will use the CAS operation, to judge whether to be put to the position of the element in the array is empty, empty is changed to the current element, put if the CAS fails, then will spin, this time found that has a element in the array, then will lock list or red-black tree head, put elements in the list, or red and black under the tree.
Five: Hash conflict
When put is used to compute the hash and the subscript, the value may be the same, and the same place in the array will cause hash collisions.
The probability of the calculated subscript values being the same is very high. Therefore, the hash conflict is mainly caused by the same subscript positions. The solution of hashMap is to use the chained address method, that is, to use the linked list method to solve the problem. Otherwise, put the element in the next place on the list.