Java Interview Question 14: HashMap

Combined question: What is the internal structure of HashMap? What are the characteristics of red-black trees? What is the time complexity of the red-black tree? What is the time complexity of the ideal HashMap?

Related article: Data Structure: HashMap

Related video: https://www.bilibili.com/video/av75970633

1. What is the internal structure of HashMap? Where is it reflected?

The embodiment of the array:

The embodiment of the single necklace watch:

The embodiment of the red-black tree:

2. Why must the initial capacity of HashMap be a multiple of 2?

    /**     * The default initial capacity - MUST be a power of two.     */    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

The answer is to facilitate the realization of "and" operation (&)

If what you pass in is not a multiple of 2, the code will automatically adjust it for you.

    /**     * Returns a power of two size for the given target capacity.     */    static final int tableSizeFor(int cap) {        int n = cap - 1;        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }

3. There is a hash integer parameter in Node, why should it be saved?

Needless to say, the meaning of key-value pairs, next is the symbol of the linked list, so what is the use of int hash, why do we need to declare a parameter separately?

This is because the acquisition of this value is not easy, and it took four steps to acquire it, so save it:

  1. Ensure that the capacity of HashMap is a multiple of 2,
  2. Get the HashCode of the deposited value
  3. The high 16 bits and the low 16 bits of HashCode are ANDed to get the result
  4. Perform an AND operation on the result and (capacity-1) of the previous step.
    static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }

3. Under what circumstances will it be converted to a red-black tree and the code will be reflected?

The code reflects:

static final int TREEIFY_THRESHOLD = 8; final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {    ...    if ((e = p.next) == null) {        p.next = newNode(hash, key, value, null);        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st            treeifyBin(tab, hash);        break;    }    ...   }

4. What are the characteristics of red-black trees? What is the time complexity of the red-black tree? What is the time complexity of the ideal HashMap?

2.1. What are the characteristics of red-black trees?

2.2. What is the time complexity of the red-black tree?

2.3. What is the time complexity of the ideal HashMap?

O (logN)