In-depth understanding of the implementation principle of HashMap in java (picture)

This article mainly introduces relevant information for in-depth understanding of the implementation principles of HashMap in java. Friends in need can refer to

1. The data structure of HashMap

There are arrays and linked lists in the data structure to store data, but these two are basically two extremes.

                                                                                The storage interval of the array is continuous and takes up a lot of memory, so the space is very complex. However, the binary search

of the array has a small time complexity of O(1); the characteristics of the array are:

easy to address, difficult to insert and delete;Linked list

The storage interval of the linked list is discrete and the memory occupied is relatively loose, so the space complexity is very small, but the time complexity is very large, reaching O(N). The characteristics of linked list

are: difficult to address, easy to insert and delete.

Hash table

So can we combine the characteristics of the two and create a data structure that is easy to address and easy to insert and delete? The answer is yes, this is the hash table we are going to mention. Hash table (Hash table) not only meets the convenience of data search, but also does not take up too much content space and is very convenient to use.

There are many different implementation methods of hash table. I will follow What is explained is one of the most commonly used methods - the zipper method, which we can understand as "

array of linked lists

", as shown in the picture:

From the above figure we can find that the hash table is composed of
array + linked list

. In an array with a length of 16, each element stores The head node of a linked list. So according to what rules are these elements stored in the array? Generally, it is obtained by hash(key)%len, which is the hash value of the element's key modulo the array length. For example, in the above hash table, 12%16=12, 28%16=12, 108%16=12, 140%16=12. So 12, 28, 108 and 140 are all stored at the array index 12

#. ## HashMap is actually implemented as a linear array, so it can be understood that the container for storing data is a linear array. This may make us confused, how can a linear array access data by key-value pairs? HashMap does some processing. First, HashMap implements a static internal class Entry, whose important

properties

include

key, value, next

. , we can clearly see from the attributes key and value that Entry is a basic bean for the implementation of HashMap key-value pairs. As we mentioned above, the basis of HashMap is a linear array. This array is Entry[], and the contents in the Map are Saved in Entry[]

 /**

   * The table, resized as necessary. Length MUST Always be a power of two.

   */
    transient Entry[] table;

2. HashMap access implementation Since it is a linear array, why can HashMap use a small number? The algorithm is roughly implemented like this:

// 存储时:
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

1) put

Question: If the index obtained by two keys through hash%Entry[].length is the same, will it not Is there a risk of overwriting?

The concept of chained data structure is used in HashMap here. We mentioned above that there is a next attribute in the Entry class, which points to the next Entry. For example, the first key-value pair A comes in, and the index=0 obtained by calculating the hash of its key is recorded as: Entry[0] = A. After a while, another key-value pair B comes in, and its index is equal to 0 by calculation. What should we do now? HashMap will do this: B.next = A,Entry[0] = B. If C comes in again, the index is also equal to 0, then

C.next = B

,Entry[0] = C; In this way, we find that the place with index=0 actually accesses three key-value pairs A, B, and C. They are linked together through the next attribute. So don’t worry if you have any questions.

That is to say, the last inserted element is stored in the array.

So far, we should have a clear understanding of the general implementation of HashMap.

 public V put(K key, V value) {

    if (key == null)

      return putForNullKey(value); //null总是放在数组的第一个链表中

    int hash = hash(key.hashCode());

    int i = indexFor(hash, table.length);

    //遍历链表

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {

      Object k;

      //如果key在链表中已存在，则替换为新value

      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;

  }

 void addEntry(int hash, K key, V value, int bucketIndex) {

  Entry<K,V> e = table[bucketIndex];

  table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//参数e, 是Entry.next

  //如果size超过threshold，则扩充table大小。再散列

  if (size++ >= threshold)

      resize(2 * table.length);

}

Of course, HashMap also contains some optimization implementations, which will be discussed here. For example: after the length of Entry[] is fixed, as the data in the map becomes longer and longer, the chain of the same index will be very long. Will it affect the performance? A factor is set in HashMap. As the size of the map gets larger and larger, Entry[] will lengthen according to certain rules. 2) get

public V get(Object key) {

    if (key == null)

      return getForNullKey();

    int hash = hash(key.hashCode());

    //先定位到数组元素，再遍历该元素处的链表

    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.equals(k)))

        return e.value;

    }

    return null;

}

3) Null key access

null key is always stored in Entry[] The first element of the array.

 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;

  }

 


  private V getForNullKey() {

    for (Entry<K,V> e = table[0]; e != null; e = e.next) {

      if (e.key == null)

        return e.value;

    }

    return null;

  }

4) Determine the array index: hashcode % table.length modulo

When accessing HashMap, you need to calculate which element of the Entry[] array the current key should correspond to , that is, calculating the array subscript; the algorithm is as follows:

 /**

   * Returns index for hash code h.

   */

  static int indexFor(int h, int length) {

    return h & (length-1);

  }

Bitwise union is equivalent to taking modulo mod or taking remainder %. This means that the array subscripts are the same, but it does not mean that the hashCode is the same.

5）table初始大小

 public HashMap(int initialCapacity, float loadFactor) {

    ..... 


    // Find a power of 2 >= initialCapacity 

    int capacity = 1;

    while (capacity < initialCapacity)

      capacity <<= 1;


    this.loadFactor = loadFactor;

    threshold = (int)(capacity * loadFactor);

    table = new Entry[capacity];

    init();

  }

注意table初始大小并不是构造函数中的initialCapacity！！

而是 >= initialCapacity的2的n次幂！！！！

————为什么这么设计呢？——

3. 解决hash冲突的办法开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列） 再哈希法 链地址法 建立一个公共溢出区

Java中hashmap的解决办法就是采用的链地址法。

4. 再散列rehash过程

当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

  /**

   * Rehashes the contents of this map into a new array with a

   * larger capacity. This method is called automatically when the

   * number of keys in this map reaches its threshold.

   *

   * If current capacity is MAXIMUM_CAPACITY, this method does not

   * resize the map, but sets threshold to Integer.MAX_VALUE.

   * This has the effect of preventing future calls.

   *

   * @param newCapacity the new capacity, MUST be a power of two;

   *    must be greater than current capacity unless current

   *    capacity is MAXIMUM_CAPACITY (in which case value

   *    is irrelevant).

   */

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

  }

 

  /**

   * Transfers all entries from current table to newTable.

   */

  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;

          //重新计算index

          int i = indexFor(e.hash, newCapacity);

          e.next = newTable[i];

          newTable[i] = e;

          e = next;

        } while (e != null);

      }

    }

  }

The above is the detailed content of In-depth understanding of the implementation principle of HashMap in java (picture). For more information, please follow other related articles on the PHP Chinese website!