Java containers HashMap and HashTable in detail

1, HashMap

HashMap inherits the abstract class AbstractMap and implements the interfaces Map, Cloneable and Serializable. HashMap is a container for storing data in key-value pairs,

Consists of an array + linked list, where key和value Both can be null and key has a value of only 1. HashMap Non-thread-safe for key-value pairs < Key,Value > .

Internally, HashMap encapsulates it as a counterpart Entry<Key,Value> Object. The storage size of HashMap can be dynamically changed:

The stored procedure

There is one for each object HashCode According to the HashCode value, call the hash function, calculate 1 hash value, call the indexFor function according to the hash value, calculate the storage location in table, if the location already has a value, then store in the bucket corresponding to that location.

 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);
  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++;
  addEntry(hash, key, value, i);
  return null;
 }
 public final int hash(Object k) {
  int h = hashSeed;
  if (0 != h && k instanceof String) {
   return sun.misc.Hashing.stringHash32((String) k);
  }
  h ^= k.hashCode();
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
 }
 public final int hashCode() {
  return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue()) 
 }
 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);
 }

Get the value

First, the hash value is calculated according to the HashCode code of key, then the indexFor function is called to calculate the storage location of the entry object in table, and the entry object stored in the bucket corresponding to that location is traversed. If the hash value and key of the object are the same as those to be found, the object is returned.

 public 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;
 }

Equal judgment of two map

 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;
  }

Reflexivity: For any non-null reference value x, ES57en.equals (x) should return true.

Symmetry: For any non-null reference values x and y, x.equals (y) should return true if and only if ES66en.equals (x) returns true.

Transitivity: For any non-null reference values x, y, and z, if x.equals (y) returns true and y.equals (z) returns

true, then ES90en.equals (z) should return true.

1 Allergenicity: Multiple calls to x. equals(y) always return true or false for any non-null reference values x and y, as long as on the object

The information used in the equals comparison has not been modified.

For any non-null reference value x, ES109en.equals (null) should return false.

Dynamic allocation of storage space

HashMap The number of buckets, i.e Entry[] table The length of an array, since arrays are contiguous storage units in memory, is spatially expensive, but its random-access speed is Java The fastest in the set. We increase the number of barrels and decrease it Entry<Key,Value> The length of the linked list to increase the speed of reading data from HashMap. This is a classic space for time strategy.

But we can't just start HashMap Allocating too many buckets (i.e Entry[] table Array start should not be too large), because array is a continuous memory space, it is expensive to create, and we are not sure how much HashMap can actually use to allocate such a large space. To solve this problem, HashMap USES the dynamic allocation of buckets according to the actual situation.

To dynamically allocate the number of buckets, a tradeoff is required, and HashMap's tradeoff is as follows:

 if  HashMap The size of the  > HashMap The capacity of the ( namely Entry[] table The size of the )* Load factor ( Experience value 0.75)

  the  HashMap In the Entry[] table  Is expanded to the current capacity 1 Times; Then replace the previous bucket `Entry<Key,Value>` The list is reallocated to the buckets 

The above HashMap capacity (that is, the size of Entry[] table) * loading factor (empirical 0.75) is the so-called threshold (threshold).

2, HashTable

HashTable inherits Dictionary class, implements Map, Cloneable,Serializable interface, does not allow key to be empty, adopts zipper method to implement similar to HashMap.

HashTable is thread-safe (but there is a static method in the Collections class: synchronizedMap(), which creates a thread-safe Map object through which we can synchronously access the potential HashMap and lock the entire map object. CurrentHashMap is thread-safe and locks buckets only, without affecting the operation of other buckets on the map object.

I hope this article will be helpful to you