Hello everyone, I am the third. Last issue released a: face slag reverse attack: HashMap chasing the soul 23 questions, the response is very good!

Onlookers have said 👇

Not to write, is impossible not to write, only the volume can maintain such a life.

Of course, this series I wrote is not a recitation version, is an understanding version, many places are talking about principles, the content is relatively sufficient, rote memorization is difficult, we must understand to memorize.

This article, in addition to the previous HashMap some minor errors to correct, I also relatively “relatively” simple List also invited in, to help you drop the curve, find confidence – use thank, leave a like line. 😀

The introduction

1. What are some common collections?

Collection related classes and interfaces are in java.util and are divided into three main types: List, Map, and Set.

Where Collection is the parent interface of List and Set, it mainly has two sub-interfaces:

• List: The stored elements are ordered and repeatable.
• Set: The stored elements are not out of order and cannot be repeated.

Map is another interface, a collection of key-value pair mapping structures.

List

List, there is no need to ask, but it does not rule out that the interviewer sword is biased, for example, the interviewer also read my article.

2. What is the difference between ArrayList and LinkedList?

(1) Different data structures

• ArrayList is implemented based on arrays
• LinkedList is implemented based on a two-way LinkedList

(2) In most cases, ArrayList is better for finding and LinkedList is better for adding and deleting

• ArrayList is implemented based on arrays. Get (int index) can be obtained directly by array subscript, and the time complexity is O(1). LinkedList is implemented based on the LinkedList, get(int index) needs to traverse the LinkedList, the time complexity is O(n); Of course, get(E Element) searches, both sets are traversal, order n time.

• If the array is inserted at the end of the array, it can be inserted or deleted, but if it is inserted at the middle of the array, it needs to move all the inserted elements forward or backward, and may even trigger expansion. Inserts and deletions of bidirectional lists require only changing the orientation of precursor nodes, successors, and inserts without moving elements.

  

And notice that there’s a trap here, that LinkedList is more likely to be added or deleted in terms of average steps, not in terms of time complexity, which is O(n) for both.

(3) Whether random access is supported

• ArrayList is based on arrays, so it looks up by subscript and supports random access. Of course, it also implements the RandmoAccess interface, which is just used to indicate whether random access is supported or not.
• LinkedList is based on a LinkedList, so it can’t get elements directly by ordinal number, it doesn’t implement the RandmoAccess interface, and tags don’t support random access.

ArrayList is based on array and is a contiguous memory space. LinkedList is based on LinkedList and the memory space is not contiguous. Both of them have some extra consumption in space occupation:

• An ArrayList is a pre-defined array that may have empty memory space, which is a waste of space
• Each node of the LinkedList needs to store its predecessors and successors, so each node takes up more space

3. Do you understand the expansion mechanism of ArrayList?

An ArrayList is a collection of arrays. The size of the array is defined at the time of definition. If the array is full, it will overflow. If the current capacity +1 exceeds the array length, the array will be expanded.

An ArrayList is augmented by creating a new array that is 1.5 times larger and then copying the values of the original array.

4. How to serialize ArrayList? Why modify an array transient?

The serialization of an ArrayList is different in that it uses transient to decorate an array that stores the element’s elementData. The purpose of the transient keyword is not to serialize the decorated member attributes.

Why doesn’t an ArrayList just serialize an array of elements?

For efficiency’s sake, the array might be 100, but only 50 is used, and the remaining 50 doesn’t have to be serialized, which makes serialization and deserialization more efficient, and also saves memory.

So how do you serialize an ArrayList?

ArrayList uses two methods, readObject and writeObject, to customize the serialization and deserialization strategies. In fact, ObjectOutputStream and ObjectInputStream are directly used for serialization and deserialization.

5. Fail-fast and Fail-safe?

Fail — Fast: Fast failure is an error detection mechanism for Java collections

• When traversing A collection object with an iterator, Concurrent Modification Exception is thrown if thread B makes changes (additions, deletions, modifications) to the contents of the collection object while thread A is traversing.
• Principle: Iterators directly access the contents of a collection during traversal, and use one during traversal modCountThe variable. The collection changes if its contents change while it is being traversedmodCountThe value of the. Whenever the iterator iterates over the next element using hashNext()/next(), it checks whether the modCount variable is the expectedmodCount value and returns the traversal if it is; Otherwise, an exception is thrown and the traversal is terminated.
• Note: The exception is thrown if modCount is detected! =expectedmodCount This condition. If the set changes when the modCount value is just set to the expectedmodCount value, the exception will not be thrown. Therefore, concurrent operations cannot be programmed depending on whether or not this exception is thrown; this exception is only recommended for detecting concurrent modification bugs.
• Scenario: Collection classes under the java.util package fail fast and cannot be concurrently modified (modified during iteration) in multiple threads, such as the ArrayList class.

Fail-safe

• The collection container using security failure mechanism is not directly accessed on the collection content in traversal, but copies the original collection content first and traverses the copied collection.
• Principle: Since the copy of the original collection is iterated during iteration, the changes made to the original collection during iteration cannot be detected by the iterator, so Concurrent Modification Modification is not triggered.
• Disadvantages: Copy-based has the advantage of avoiding Concurrent Modification Exceptions, but again, the iterator cannot access the modified content, i.e., iterators iterate over the copy of the collection at the beginning of the iteration, and the iterator is not aware of the changes that occurred during the iteration of the original collection.
• Scenario: Containers under the java.util.concurrent package are security failures and can be used and modified concurrently in multiple threads, such as the CopyOnWriteArrayList class.

6. What are some ways to make ArrayList thread safe?

Fail-fast is a mechanism that can trigger the thread safety of an ArrayList. In fact, the thread safety of an ArrayList is still not guaranteed.

• Use Vector instead of ArrayList. (Not recommended; Vector is a legacy class)
• Use Collections. SynchronizedList ArrayList, packaging and packing list after the operation.
• Use CopyOnWriteArrayList instead of ArrayList.
• When using ArrayList, the application uses a synchronization mechanism to control the read and write of the ArrayList.

7. What does CopyOnWriteArrayList know?

CopyOnWriteArrayList is a thread-safe version of ArrayList.

It’s called CopyOnWrite — CopyOnWrite, and that’s what it does.

CopyOnWriteArrayList employs a concurrency strategy of read-write separation. CopyOnWriteArrayList allows concurrent reads. The read operation is lockless and has high performance. For writes, such as adding an element to a container, a copy of the current container is first made, the write is performed on the new copy, and a reference to the original container is then referred to the new container.

Map

In the Map, there is no doubt that the most important is HashMap, the interview is basically dish out the paste, all kinds of questions, must be well prepared.

8. Can you explain the data structure of HashMap?

The data structure of JDK1.7 is array + linked list. Not……

Let’s talk about the JDK1.8 data structure:

JDK1.8’s data structure is array + linked list + red-black tree.

The data structure is shown as follows:

Among them, bucket array is used to store data elements, linked list is used to resolve conflicts, and red-black tree is used to improve the efficiency of query.

• The data elements are mapped to the location of the index of the bucket array through a mapping relationship, known as a hash function
• If a conflict occurs, pull a linked list from the conflicting location and insert the conflicting elements
• If the list length >8& array size >=64, the list becomes a red-black tree
• If the number of red-black tree nodes is less than 6, it is converted to a linked list

9. How much do you know about red-black trees? Why not use binary/equilibrium trees?

A red-black tree is essentially a binary lookup tree, and for balance, it adds some rules to the binary lookup tree:

1. Each node is either red or black;
2. The root node is always black;
3. All leaf nodes are black (note that leaf nodes are actually NULL nodes in the diagram);
4. Both children of each red node must be black;
5. The path from any node to each leaf node in the subtree contains the same number of black nodes;

The reason for not using binary trees:

Red-black tree is a balanced binary tree. The worst time complexity of insert, delete and search is O(logn), which avoids the worst case O(n) time complexity of binary tree.

The reason for not balancing binary trees:

Balanced binary trees are more strictly balanced trees than red-black trees. In order to maintain balance, more rotations are required, which means that balanced binary trees are less efficient at maintaining balance, so the efficiency of balanced binary trees is lower than red-black trees in inserting and deleting.

10. How do red-black trees keep their balance?

Red-black trees maintain balance in two ways: rotation and staining.

• Rotations: There are two kinds of rotations, left and right

• Dye:

11. Do you know the put process of HashMap?

Let’s start with the flow diagram:

1. The hash value is first disturbed to obtain a new hash value. (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

2. Check whether the TAB bit is empty or its length is 0. If yes, expand the capacity.

   if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;
   Copy the code

3. Calculate the subscript according to the hash value. If the corresponding subscript does not store data, insert it directly; otherwise, it needs to be overwritten. tab[i = (n – 1) & hash])

4. Check whether TAB [I] is a tree node. If TAB [I] is a tree node, insert data into the list. If TAB [I] is a tree node, insert data into the tree.

5. If the length of the linked list is greater than or equal to 8 when nodes are inserted, the list needs to be converted to a red-black tree. treeifyBin(tab, hash);

6. Finally, after all elements are processed, judge whether the threshold value is exceeded; Threshold: If the threshold is exceeded, the system will expand the capacity.

12. How does HashMap find elements?

First look at the flow chart:

Finding a HashMap is much easier:

1. Using the perturbation function, get the new hash value
2. Calculates the array subscript to get the node
3. If the current node matches the key, this field is returned
4. Otherwise, if the current node is a tree node, look for red black tree
5. Otherwise, traverse the list for lookup

13. How is the hash/disturbance function of HashMap designed?

The hash function of a HashMap takes the hashcode of the key, which is a 32-bit value of type int, and xor the high and low 16 bits of the HashCode.

    static final int hash(Object key) {
        int h;
        // The hashCode of the key and the hashCode of the key are shifted 16 bits to the right for xor
        return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
    }
Copy the code

This is designed to reduce the probability of hash collisions.

14. Why can hash/perturbation functions lower hash collisions?

The key.hashcode () function calls the hash function of the key value type and returns an int hash value. Int values range from -2147483648 to 2147483647, which adds up to about 4 billion mappings.

As long as hash functions are mapped evenly and loosely, collisions are hard to occur in general applications. But the problem is that with a 4 billion array, you can’t fit it in memory.

If the initial size of the HashMap array is only 16, then we need to modulo the length of the array before the remainder can be used to access the array subscript.

Source modulo operation is the hash value and array length -1 to do an “and” operation, bit operation than mod % operation is faster.

bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
     return h & (length-1);
}
Copy the code

This, by the way, explains why the array length of a HashMap is an integer power of 2. Because this (array length -1) is exactly equivalent to a “low order mask”. The result of the and operation is that the hash values are all zeroed out, and only the low values are reserved for array subscript access. For example, if the initial length is 16, 16-1=15. The base 2 representation is 0000 0000 0000 0000 1111. And a hash value as follows, the result is a truncation of the lowest four-digit value.

This is faster, but the new problem is that even if the hash values are distributed loosely, if only the last few bits are taken, the collision will be very serious. If the hash itself is not well done, the distribution of an arithmetic sequence of holes, if just the last few low points repeat regularly, that’s even harder to do.

At this point, the value of the disturbance function is reflected. Take a look at the schematic diagram of the disturbance function:

Moving 16 bits to the right, exactly half the size of 32bit, and doing xor for the high and low parts of the original hash code is to mix the high and low parts of the original hash code to increase the randomness of the low parts. In addition, the mixed low level is mixed with some features of the high level, so that the information of the high level is also preserved in a disguised way.

15. Why is the capacity of HashMap a multiple of 2?

• The first reason is to facilitate hashing mod:

A HashMap uses the hash value &(array size -1). This is because the size of a HashMap is a multiple of 2. Multiples of 2 mean that the number has only one 1 bit. And the number -1 can get the binary 1 becomes 0, the following 0 becomes 1, and then through the ampersand operation, can get the same effect as %, and the bit operation is much more efficient than %

When the capacity of a HashMap is 2 to the NTH power, the binary base of (n-1) is 1111111***111. In this way, the bitwise operation with the hash value of the added element can be fully hashed so that the added elements are evenly distributed in every position of the HashMap, reducing hash collisions.

• The second aspect is to perfectly transfer elements that have generated hash collisions to the new table when expanding the table, using the expanded size to be a multiple of 2

A quick look at the HashMap scaling mechanism shows that elements in a HashMap scale up when they exceed the load factor *HashMap size.

16. If you initialize the HashMap, pass a value of 17new HashMap<>What does it do?

In simple terms, when initialized, the HashMap will look up for the nearest multiple of 2, so 17 is passed in, but the actual capacity of the HashMap is 32.

Let’s look at the details. In the initialization of a HashMap, there is a method like this;

public HashMap(int initialCapacity, float loadFactor) {...this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}
Copy the code

• Threshold, through the method tableSizeForThe calculation is based on the initialization parameters.
• It also looks for the smallest binary value that is greater than the initial value. Like 17, I should have found 32.

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; }
Copy the code

• MAXIMUM_CAPACITY = 1 << 30, this is the critical range, that is, the largest set of maps.
• The calculation is done by shifting to the right 1, 2, 4, 8, 16, and the original number|Operation, this is mainly to fill in the binary position of each 1, when the binary position is 1, is a standard multiple of 2 minus 1, and finally add 1 to return the result.

Take 17 as an example and look at the process of initializing the size of a table:

17. What else do you know about the construction of hash functions?

The hash constructor in HashMap is called:

• In addition to the remainder method: H (key)=key%p (p<=N), the key is divided by a positive integer p not greater than the length of the hash table, the remainder is the address, of course, the HashMap has been optimized, the efficiency is higher, the hash is more balanced.

In addition, there are several common hash function constructors:

• Direct addressing

  Map directly to the corresponding array location based on the key, for example, 1232 to the subscript 1232.

• Numerical analysis method

  Take some number of the key (such as tens and hundreds) as the location of the mapping

• Square the middle

  Take the middle bits of key squared as the location of the mapping

• Folding method

  Divide the key into segments with the same number of digits, and then use their summation as the location of the mapping

18. What are the methods for resolving hash conflicts?

As we’ve seen by now, the reason HashMap uses linked lists is to handle hash collisions, which is called:

• Linked address method: pull a linked list at conflicting locations and put the conflicting elements in it.

In addition, there are some common ways to resolve conflicts:

• Open addressing: Open addressing starts at the conflicting location and goes down to find a space for the conflicting elements.

  There are many ways to find a free spot:

  • Line detection method: starting from the conflicting positions, judge whether the next position is free until the free position is found
  • Square probe: starting at the conflicting position X, the first increment1 ^ 2I’m going to increase it a second time2 ^ 2… Until a free position is found
  • …

• Rehash method: change a hash function, recalculate the address of the conflicting elements.
• Create a public overflow area: Create another array and put the conflicting elements in it.

19. Why is the HashMap linked list turned red-black tree threshold 8?

Treification occurs when the length of the table array is greater than 64 and the length of the linked list is greater than 8.

Why 8? The source code comments also provide an answer.

The node size of a red-black tree is about twice that of a normal node, so switching to a red-black tree sacrifices space for time and is more of a bottom-of-the-line strategy to ensure search efficiency in extreme cases.

Why is the threshold 8? It’s about statistics. Ideally, using random hash codes, the nodes in the list conform to poisson distribution, and the probability of the number of nodes is decreasing. If the number of nodes is 8, the probability of occurrence is only 0.00000006.

Why is the threshold for a red-black tree to return to a linked list 6 instead of 8? If the threshold value is also set to 8, if a collision occurs and the increase and decrease of nodes are just around 8, the continuous conversion between linked list and red-black tree will occur, resulting in resource waste.

20. When will the expansion be? Why is the expansion factor 0.75?

In order to reduce the probability of hash conflicts, when the number of elements in the current HashMap reaches a critical value, expansion will be triggered and all elements will be rehashed into the expanded container, which is a time-consuming operation.

The threshold is determined by the loading factor and the capacity of the current container. If the default constructor is used:

Threshold = Default capacity (DEFAULT_INITIAL_CAPACITY) * Default capacity expansion factor (DEFAULT_LOAD_FACTOR)

When greater than 16×0.75=12, the expansion operation will be triggered.

So why was 0.75 chosen as the default load factor for HashMap?

Simply put, this is a consideration of the balance between the cost of space and the cost of time.

In the HashMap there is a comment like this:

As we all know, HashMap hashes are constructed by Hash residuals, and the load factor determines how many elements to expand.

If we set it to be larger, with more elements and fewer vacancies, then the probability of hashing conflicts will increase, and the time cost of searching will increase.

If we set it as small, the space will be expanded when there are fewer elements and more vacancies, the probability of hash collision will be reduced, and the search time cost will be reduced, but more space will be needed to store elements, and the space cost will be increased.

21. Is the expansion mechanism understood?

A HashMap is implemented based on an array + linked list and a red-black tree, but the length of the bucket array used to hold keys is fixed, determined by the initialization parameter.

Then, as the number of data inserts increases and the load factor takes effect, the capacity needs to be expanded to accommodate more data. One important aspect of scaling is that optimization in JDK1.8 eliminates the need to recalculate the hash value of every element.

Since the original capacity of a HashMap is a power of 2, the size is doubled, and the new capacity is also a power of 2, the elements are either in their original position, or moved by a power of 2.

Take a look at this figure. N is the length of the table. Figure A shows the index position determined by key1 and KEY2 before expansion, and Figure B shows the index position determined by key1 and key2 after expansion.

After the element recalculates the hash, the mask range of n-1 is 1bit more (red) at the high end, so the new index will look like this:

If the value is 0, the index remains the same. If the value is 1, the index +oldCap is changed to the original index.

The main logic for node migration is as follows:

22. What are the main optimizations for HashMap in JDk1.8? Why is that?

There are five major optimizations for jdK1.8 HashMap:

1. Data structure: Array + list changed to array + list or red-black tree

   Cause: Hash conflict occurs, elements will be stored in linked list, linked list too long to red black tree, time complexity from O(n) to O(logn)

2. Linked list insertion method: The linked list insertion method has been changed to tail insertion method

   If there are already elements in the array, 1.7 places the new element in the array, and the original node is the successor node of the new node. 1.8 traverses the list and places the element at the end of the list.

   Cause: In the expansion process of 1.7 headplug method, the headplug method will cause the linked list to be reversed, and loops will be generated in multi-threaded environment.

3. Rehash: During expansion, 1.7 needs to rehash the elements in the original array to the new location. 1.8 uses simpler judgment logic, which does not need to rehash the location through the hash function. The new location remains unchanged or the index + the new capacity is added.

   Cause: Improve capacity expansion efficiency and expand capacity faster.

4. Expansion time: 1.7 Determine whether expansion is required and then insert; 1.8 Determine whether expansion is required and then insert.

5. Hash function: 1.7 does four shifts and four xor, jdk1.8 only does one.

   Reason: If you do it 4 times, the marginal utility is not big, so change it to once to improve efficiency.

23. Can you design and implement a HashMap yourself?

This problem is often tested quickly.

Don’t panic, red and black tree version we are probably not able to write, but array + linked list version is not a big problem, detailed visible: handwritten HashMap, quick hand interview direct call expert! .

Overall design:

• Hash function: hashCode()+ divisor remainder method
• Conflict resolution: chain address method
• Expansion: Nodes are rehash to obtain positions

Complete code:

24. Is HashMap thread safe? What’s the problem with multithreading?

HashMap is not thread-safe, and these problems can occur:

• Infinite loop under multithreading. The HashMap in JDK1.7 uses header insertion to insert elements. In a multi-threaded environment, expansion can lead to an infinite loop of circular lists. For this reason, JDK1.8 uses tail inserts to keep the list elements in their original order during expansion without the problem of circular lists.

• Multithreaded PUT can cause elements to be lost. If multiple threads perform the put operation at the same time, if the computed index positions are the same, the previous key will be overwritten by the next key, resulting in element loss. This problem exists in BOTH JDK 1.7 and JDK 1.8.

• If PUT and GET are concurrent, GET may be null. Thread 1 performs put, rehash because the number of elements exceeds threshold, and thread 2 performs GET, which may cause this problem. This problem exists in JDK 1.7 and JDK 1.8.

25. Is there any solution to the HashMap thread insecurity problem?

In Java HashTable, Collections. SynchronizedMap and ConcurrentHashMap can achieve thread-safety Map.

• HashTable is a direct method to add synchronized keyword, lock the entire table array, granularity is relatively large;
• Collections.synchronizedmap set of tools is the use of the Collections within class, by passing in the Map to encapsulate a synchronizedMap object, internal object defines a lock, by object lock inside method;
• ConcurrentHashMap uses segwise locking in JDK1.7 and CAS+synchronized in JDK1.8.

26. Can you elaborate on the implementation of ConcurrentHashmap?

ConcurrentHashmap thread security is implemented in jdk1.7 based on piecewise locking and in jdk1.8 based on CAS+synchronized.

Section 1.7 the lock

ConcurrentHashMap 1.7 contains an array of segments that inherit from ReentrantLock. The Segment contains an array of hashentries. A HashEntry is itself a linked list structure with the ability to hold keys, values and Pointers to the next node.

Each Segment is a HashMap. The default length of the Segment is 16.

Put the process

The entire process is very similar to a HashMap, except that it locates the Segment and then ReentrantLock the Segment. The rest of the process is basically the same as a HashMap.

1. Hash, locate the segment, initialize the segment if it is empty
2. ReentrantLock is used to lock. If the lock fails to be obtained, spin will be tried. If the spin exceeds the number of times, the lock will be blocked to ensure that the lock is successfully obtained
3. Iterate over a HashEntry, just like a HashMap, replacing an array key with a hash, and inserting a list if it doesn’t exist

Get the process

The key hashes to the segment and iterates through the list to locate the specific element. Note that the value is volatile, so get does not need to be locked.

1.8 the CAS + synchronized

Instead of using the same data structure as HashMap, jdK1.8 implements thread-safety using an array + a linked list + a red-black tree. The key to its thread-safe implementation is the PUT process.

Put the process

1. First compute the hash, traverse the node array, and initialize it with CAS+ spin if the node is empty

 tab = initTable();
Copy the code

Node array initialization:

    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            // If initializing or expanding capacity
            if ((sc = sizeCtl) < 0)
                / / wait for
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {   / / CAS operation
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0)? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])newNode<? ,? >[n]; table = tab = nt; sc = n - (n >>>2); }}finally {
                    sizeCtl = sc;
                }
                break; }}return tab;
    }
Copy the code

2. If the current array position is empty, write data directly through CAS spin

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }
Copy the code

3. If hash==MOVED, the system needs to expand the capacity

else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
Copy the code

    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        if(tab ! =null && (f instanceofForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) ! =null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                if((sc >>> RESIZE_STAMP_SHIFT) ! = rs || sc == rs +1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break; }}return nextTab;
        }
        return table;
    }
Copy the code

4. If not, synchronized is used to write data, and the written data is also judged as linked list and red-black tree. Linked list writing is overwritten in the same way as HashMap and key hash; otherwise, tail insertion is used. If the length of the linked list exceeds 8, it is converted to red-black tree

 synchronized(f) {... }Copy the code

Get the query

Get is very simple. It is basically the same as a HashMap. It calculates the location by key.

27. Are the internal nodes of the HashMap ordered?

A HashMap is unordered and randomly inserted based on the hash value. To use an ordered Map, use LinkedHashMap or TreeMap.

28. Tell me how LinkedHashMap is organized.

The LinkedHashMap maintains a bidirectional linked list, with the first and last nodes. In addition, the Entry of the LinkedHashMap Node inherits the Node attributes of HashMap, as well as before and after, which are used to identify the front and back nodes.

You can sort by insertion order or access order.

29. Tell me how TreeMap is ordered.

TreeMap sorts by the natural order of keys or Comprator order, internally through a red-black tree. So either the class to which the key belongs implements the Comparable interface, or a custom Comparator that implements the Comparator interface is passed to TreeMap for key comparisons.

Set

A “Set” interview is not a good question.

30. What is the underlying implementation of HashSet?

The underlying implementation of HashSet is based on HashMap. The source code for HashSet is very, very sparse, because with the exception of Clone (), writeObject(), and readObject(), which HashSet itself has to implement, all methods call methods directly from the HashMap.

The add method of a HashSet directly calls the Put method of a HashMap. The added element is the key and an Object is the value. The put method of a HashMap directly calls the put method of a HashMap.

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
Copy the code

In the putVal method of the HashMap, a series of judgments are made and the result is that the inserted value is returned only if the key does not exist in the table array.

            if(e ! =null) { // existing mapping for key
                V oldValue = e.value;
                if(! onlyIfAbsent || oldValue ==null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
Copy the code

---

Reference:

[1]. A HashMap waffled with the interviewer for half an hour

[2]. “Big Factory Interview” — Java set 30 questions

[3] chapter 4 “Insert, Find, Delete, Traverse HashMap Data, Source Code Analysis”

[4]. “I Want to Enter the Factory” Java foundation take life serial 16 questions

[5]. Data structure LinkedHashMap

[6]. Chapter 3 “Core knowledge of HashMap, Disturbance Function, Load factor, Expansion linked list resolution, Deep Learning”.

[7] Interviewer: Why is the load factor of HashMap 0.75?

[8]. Interview old Enemy red black tree

[9]. Java TreeMap working principle and implementation

[10]. Write HashMap by hand.

[11].Java 8 Series relearning HashMap

---

Article first individual public number: three points evil, welcome attention!