Preface:

HashMap should be a mandatory question for the Java backend engineer interview, because it contains so many knowledge points that it is a good way to test the candidate’s Java background. HashMap, HashTable and ConcurrentHashMap. This is the essence of a HashMap interview.

The opening

Interviewer: Why don’t you introduce yourself first?

I: I am **, graduated from ****, currently in the company do — system development. The development projects are: Brabra……

Interviewer: Are you familiar with Java collections and HashMap?

Me: Yes. (Familiar smell)

Interviewer: Can you tell me about the internal data structure of HashMap?

I: currently I use JDK1.8 version, internal use array + linked list red black tree;

Me: Let me draw a data structure diagram for you:

In addition, I have compiled 20 years of interview questions, including Spring, concurrency, database, Redis, distributed, Dubbo, JVM, microservices and other aspects of the summary, the following is part of the screenshot, if necessaryClick here, click here”, code word nuggets.

Interviewer: Do you understand how HashMap inserts data?

Me: er… I think it’s better to draw a picture, as follows:

  1. Check whether the array is empty, if empty to initialize;
  2. Not null, computes the hash value of k, using (n-1) & the index that should be stored in the array;
  3. If there is no data in table[index], construct a Node and store it in table[index].
  4. If data exists, a hash conflict has occurred (the hash value of keys on two nodes is the same). Check whether the keys are equal and replace the original data with a new value (onlyIfAbsent is false).
  5. If not, determine whether the current node type is a tree node. If it is a tree node, create a tree node and insert it into the red-black tree.
  6. If not, create a common Node and add it to the linked list. Determine whether the length of the linked list is greater than 8, if so, the linked list is converted to a red-black tree;
  7. After the insertion, check whether the number of nodes is greater than the threshold. If the number is greater than the threshold, expand the number to twice that of the original array.

Interviewer: You mentioned the initialization of a HashMap. How does a HashMap set its initial capacity?

Generally, if new HashMap() does not pass a value, the default size is 16 and the load factor is 0.75. If you pass an initial size k, the initial size is greater than k to the power of 2. For example, if you pass 10, the size is 16. (Additional note: The implementation code is as follows)

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

Supplementary notes: The following figure shows the detailed process. The algorithm is to move the initial binary 1, 2, 4, 8, and 16 bits to the right, respectively, with itself. The first digit with the highest digit 1 is moved to the right continuously, and all the digits after the highest digit 1 are changed to 1. 111111 + 1 = 1000000 = 2 to the sixth power

Interviewer: You mentioned hash functions. Do you know how the hash function of HashMap is designed?

Me: the hash function takes the hashcode that passes the key, which is a 32-bit int, and then xor the high and low 16 bits of the Hashcode.

Here we go!

Interviewer: What’s the difference between a HashMap and a HashTable?

Me: HashMap is not thread-safe

A HashMap, a subclass of the Map interface, is an object that maps keys to values, where both keys and values are objects and cannot contain duplicate keys, but can contain duplicate values. A HashMap allows null keys and null values, whereas a HashTable does not.

HashTable is thread-safe.

HashMap is a lightweight implementation of Hashtable (non-thread-safe implementation). They both implement the Map interface. The main difference is that HashMap allows null keys, which can be more efficient than Hashtable because it is not thread-safe.

A HashMap allows NULL as an entry key or value, whereas a Hashtable does not. HashMap contains containsValue and containsKey. Because the CONTAINS method is misleading. Hashtable inherits from the Dictionary class, and HashMap is an implementation of the Map interface introduced in Java1.2. The main difference is that Hashtable’s method is Synchronize, whereas HashMap does not. Instead of synchronizing its method for multiple threads accessing Hashtable, HashMap must provide external synchronization for it. A Hashtable and a HashMap both use roughly the same hash/ Rehash algorithm, so there is no significant difference in performance.

What about ConcurrentHashMap? What does it do?

The JDK provides HashMap and HashTable, but how do you achieve thread-safety and efficiency at the same time? Obviously, neither of these can be satisfied, so the ConcurrentHashMap artifact is created for high-concurrency scenarios.

This artifact uses a segmented locking strategy, which provides the same thread-safety by dividing the entire Map into N segments (similar to a HashTable), with an n-fold increase in efficiency and a 16-fold increase by default.

The advantages of ConcurrentHashMap are the disadvantages of HashMap and HashTable, which also do not support null keys

The emergence of ConcurrentHashMap also means the end of HashTable, so use HashTable sparingly in future projects.

Interviewer: (Inner OS: The young man can do it. He has a deep understanding of the bottom layer. He has a good foundation.

I have basically understood your level and I am quite satisfied with you. The basis and principle are very good. I will give feedback to the above side and evaluate and screen your resume.

Me: ok ok, thank the interviewer, I first go back. Inner OS: How close it was! A hashmap was almost knocked down. Fortunately, I had a good look before the interview, otherwise I would have been embarrassed today.

Finally:

In view of the recent many people in the interview, I have also sorted out quite a lot of interview materials, there are also other big factories. I hope I can help you.

The answers to the following interview questions are documented in notes. Also sorted out some interview materials & the latest 2020 collection of some big factory interview real questions (all sorted into documents, a small part of screenshots), there is a need to click into the group to find management, nuggets.