1. What is the underlying data structure of HashMap?

A: The underlying HashMap is an array + linked list + red-black tree data structure

  • The main purpose of the array is to facilitate quick lookups. The time complexity is O(1) and the default size is 16. The subscript index of the array is calculated using the hashcode of the key
  • When multiple keys have the same hashcode but different keys, a single Node is converted to a linked list, which has O(n) query complexity.
  • When the length of the list is greater than or equal to 8 and the size of the array exceeds 64, the list is converted to a red-black tree with a query complexity of O(log(n)). Simply put, the worst number of queries is equal to the maximum depth of the red-black tree.

2. What are the possible methods to resolve hash conflicts?

A:

  1. Good hash algorithm
  2. Automatic expansion: When the array size is nearly full, automatic expansion reduces hash conflicts.
  3. When hash conflicts occur, the linked list is used to resolve them.
  4. When hash conflicts are serious, the linked list is automatically transformed into a red-black tree to speed up traversal.

3. How is HashMapHashMap expanded?

  • Expansion Opportunity:
    1. Initialization: The array is empty during put. The default capacity expansion is 16.
    2. Capacity expansion: If the size of the existing array is larger than the threshold of capacity expansion after the PUT is successful, expand the array to twice the size of the old array.
  • The threshold for capacity expansion is threshold, which will be recalculated each time capacity expansion. The threshold is equal to the size of the array * impact factor (0.75).
  • Once the new array is initialized, you need to copy the values of the old array into the new array. Linked lists and red-black trees have their own copy methods.

4. What to do when hash conflicts occur?

A: Hash collisions refer to situations where different keys are computed to produce the same Hashcode.

  • If the bucket has only one element or is already a linked list, the new element is appended directly to the end of the list.
  • If the bucket is already a linked list and the number of linked lists is greater than or equal to 8, there are two situations:
    1. If the size of the array is less than 64, the array is expanded again and the linked list is not converted to a red-black tree.
    2. If the array size is greater than 64, the linked list is converted to a red-black tree.

Here just list number greater than or equal to 8, also determine the size of the array, the array size is less than 64 did not immediately into the reason, speculation is mainly because red and black tree takes up the space is much larger than the chain, transformation is time consuming, so the array capacity under the condition of small conflict is serious, we can try expansion, can see through the capacity to solve the problem of conflict.

5. Why do lists become red-black trees when the number of lists is greater than or equal to 8?

A: These are actually two questions

  1. Why convert to a red-black tree? When there are too many linked lists, traversal may be time-consuming, which can be converted into red-black trees to reduce the time complexity of traversal. But converting to a red-black tree costs space and time.
  2. Why is the number of nodes greater than or equal to 8? Through the poisson distribution formula, under normal circumstances, the list number in 8, the concept of less than one over ten million, so under normal circumstances, the list will not be converted into a red-black tree, the purpose of this design, is to prevent abnormal situations, such as the hash algorithm has a problem, easily lead to list the number greater than or equal to 8, will still be able to traverse quickly.

6. When do red-black trees become linked lists?

A: When the number of nodes is less than or equal to 6, the red-black tree will automatically transform into a linked list, mainly considering the space cost of the red-black tree. When the number of nodes is less than or equal to 6, it is also quick to traverse the linked list, so the red-black tree will become a linked list again.

7. What if I don’t want to overwrite the value of a HashMap that is already in the array when I put it? What if the value is null and you want to return the default value?

A:

  • If the array has a key, but you don’t want to override the value, you can select putIfAbsent, which has a built-in variable onlyIfAbsent, which is true, so it won’t override the put method that we normally use, Built-in onlyIfAbsent is false to allow overwriting.

  • If the value is null and you want to return the default value, you can use the getOrDefault method. The first parameter of the method is key and the second parameter is the default value you want to return, such as map.getOrDefault(” 2 “, “0”). Returns 0 by default instead of null.

8. Is it feasible to delete it by following codes?

HashMap<String,String > map = Maps.newHashMap();
map.put("1"."1");
map.put("2"."2");
map.forEach((s, s2) -> map.remove("1"));
Copy the code

A: no, will quote error ConcurrentModificationException, forEach source code is as follows:

public void forEach(BiConsumer<? super K, ? super V> action) {
        Node<K,V>[] tab;
        if (action == null)
            throw new NullPointerException();
        if (size > 0&& (tab = table) ! =null) {
            int mc = modCount; ModCount is assigned to the MC before the loop starts
            for (int i = 0; i < tab.length; ++i) {
                for(Node<K,V> e = tab[i]; e ! =null; e = e.next)
                    action.accept(e.key, e.value);
            }
            if(modCount ! = mc)// The remove method modifies modCount, but the MC remains the same
                throw newConcurrentModificationException(); }}Copy the code

It is recommended to use iterators for deletion, in the same way as ArrayList iterators,

9. Describe the process of HashMap get and Put

A: For details please refer to [Java container source code] HashMap most detailed ten thousand word source analysis (JDK8), do not know if you can draw a picture.