preface

Wechat search [Java3y] to pay attention to this man with a dream, like attention is the biggest support for me!

The text has been uploaded to my GitHub: github.com/ZhongFuChen… , has more than 300 original articles, most recently in the serialized Interview series!

I, Three Crooked, recently started writing an interview series. I have a name for this interview series, “Please Give me an Offer.”

You can search “Java3y” on wechat and reply “Interview”.

So this article is called “Please Give me an Offer: Map Interview Questions.”

So let’s get started.

The interview scene

Sancrooked: “My name is Sancrooked, and I currently maintain a public account called Java3y. In recent years, I have written 300+ original technical articles, nearly 1,000 pages of original e-books and many knowledge points of mind mapping. My vision is: as long as the students who pay attention to me can get offer from Dachang. I…”

Map is an interface in Java. Common implementation classes include HashMap, LinkedHashMap, TreeMap, and ConcurrentHashMap.

First of all, let’s be clear: in Java, hash tables are structured as arrays and linked lists. The underlying data structure of HashMap is array + linked list/red-black tree, LinkedHashMap is array + linked list + two-way linked list, TreeMap is red-black tree, ConcurrentHashMap is array + linked list/red-black tree.

Interviewer: “Let’s start with HashMap. Can you talk about what happens when you create a HashMap?”

There are several constructors for a HashMap, but the main ones are to specify the size of the initial value and the size of the load factor. If we do not specify it, the default HashMap size is 16 and the load factor size is 0.75.”

If you pass a 10, you actually end up with a HashMap of 16. If you pass a 7, you end up with a HashMap of 8. When we put an element into a HashMap, we need to figure out the hash position of the element. In a HashMap, bitwise operations are used instead of modulo operations to calculate the location of the element more efficiently. Why a HashMap can only be a power of two, because it is only a power of two that it makes sense to replace modulo with bitwise operations.”

The load factor determines the size of the hash table expansion and hash conflict. For example, my default HashMap size is now 16, with a load factor of 0.75, which means that the array can only hold 12 elements at most, and the hash table needs to be expanded once it has more than 12 elements. How do you figure out 12? Very simple, 16 times 0.75. Every time a put element is added, the HashMap size is checked to see if it has exceeded this threshold. If so, it needs to be expanded.”

“Given the above statement (HashMap size can only be a power of 2), the default is to double the original size.”

Can I increase the load factor to 1 so that my HashMap can expand until it reaches 16 elements? Obviously, yes, but not recommended. The load factor is higher, which means the probability of hashing is higher, the probability of hashing is higher, which also takes time (because lookups are slower).”

“The implementation is on the hash method. What you can find is that it evaluates the normal hash and then does xOR with the higher 16 bits to produce the final hash. This has the advantage of increasing randomness and reducing the likelihood of collisions.”

Three crooked: “When put is put, the key is first hash to calculate the index of the key. If there is no collision, put it directly into the array. If there is a collision, you need to determine whether the current data structure is a linked list or a red-black tree, and insert it according to the different situation. Assuming the key is the same, replace it with the original value. Finally, determine whether the hash table is full (the current size of the hash table * load factor). If the hash table is full, expand the capacity.

If there is no direct return, it will determine whether the current data structure is a linked list or a red-black tree, and then extract the data from different data structures. “

The hash value is first compared, followed by the == operator and equals() to determine if the elements are the same. Namely: if only the same hash value, it shows that the elements of the hash conflict, if the hash value and the equals () | | = = are the same, it shows that the element is the same. “

Three skew: “The list is changed to a red-black tree only when the size of the array is greater than 64 and the size of the list is greater than 8. The red-black tree is degraded to a linked list when the size is 6. In this case, the operation of turning red-black tree into linked list is mainly due to performance considerations during query and insertion. Linked list query time O(N), insert time O(1), red-black tree query and insert time O(logN)”

“Actually LinkedHashMap is not used very much in daily development. As mentioned above, LinkedHashMap’s underlying structure is array + list + bidirectional list. In fact, it inherits HashMap and maintains a bidirectional list on the basis of HashMap. With this bidirectional linked list, our inserts can be “ordered”, not ordered by size, but ordered by insertion.

Three skew: “LinkedHashMap traversals are actually two-way linked lists, so the size of LinkedHashMap does not affect traversal performance.”

Three bad: TreeMap’s underlying data structure is a red-black tree. TreeMap keys cannot be null. TreeMap orders are compared using comparators. If the comparator is null, the natural order is used.”

“HashMap is not thread-safe. In a multi-threaded environment, it is possible to lose data and not get the latest data. For example, the thread Aput goes in and the thread Bget doesn’t come out. We want to be thread-safe and use ConcurrentHashMap.”

ConcurrentHashMap is a thread-safe Map implementation class under the JUC package. The thread-safe Map implementation class in addition to ConcurrentHashMap has a class called Hashtable. Of course, Collections can also be used to wrap up a thread-safe Map. However, both Hashtable and Collections packages tend to be inefficient (they synchronize directly from the outer layer), so ConcurrentHashMap is used for thread-safety purposes.”

ConcurrentHashMap’s underlying data structure is array + linked list/red-black tree, which supports high concurrency access and updates and is thread-safe. ConcurrentHashMap synchronizes by partially locking and using the CAS algorithm. The get is not locked, and the Node is volatile. During capacity expansion, each thread will be assigned a corresponding interval, and in order to prevent data inconsistency caused by putVal, the interval will be locked.”

Three crooked: “No, I won’t”

Three bad: In JDK7, HashMap is a header interpolation method. In JDK8, HashMap is a tail interpolation method. In JDK7, HashMap does not have a red-black tree…. ConcurrentHashMap is implemented in JDK7 using segwise locking, which is different in JDK 8. But I forgot most of the JDK 7 details.”

“I have never used JDK 7 API, I think now should also use JDK8? So I didn’t look at it. How about I tell you something about multithreading?”

Three crooked: “Oh”

digression

May for this interview you want to learn more details of the Map, such as basic knowledge Map/HashMap/LinkedHashMap/TreeMap/ConcurrentHashMap source code, can be in WeChat search “Java3y” reply “Map” of the before I write original articles.

** Open source project covering all knowledge points of Java backend, has 10K+ star! ** contains 1000+ pages of original ebook!!

  • GitHub
  • Gitee access is faster

The content of PDF document is typed by hand, you can ask me directly if you don’t understand