How HashMap works

First, HashMap is based on hashing. We know that there are two common methods for HashMap: put() and get(). When you pass a key-value pair to put(), it calls the hashCode() method of the key object to calculate hashCode. Then find the bucket location to store the value object. When an object is retrieved, the correct key-value pair is found through the equals() method of the key object, and the value object is returned.

In general, you will definitely ask if the key object is different hashcodeWhat happens when the values are equal. They must be stored in a linked list in the same location, using key objectsequals()Method to find a key-value pair.After Java1.8, HashMap added red-black tree data structure on the basis of array and linked list. The data structure is converted to a red-black tree structure when the list length is greater than 8 in an array position.

What’s the difference between HashMap and HashTable?

Both HashMap and HashTable implement the Map interface, and the main differences are in threads, synchronization, and speed.

  • A HashMap is asynchronous, and a HashMap can store objects with null keys, allowing up to one key to be a NULL object and multiple values to be NULL.
  • HashMap is thread-safe, HashTable is thread-safe.
  • Because HashTable is multithreaded, HashMap is faster in the case of a single thread.
  • A HashMap does not guarantee that the storage order is constant.

What’s the difference between a HashMap and a HashSet?

  • HashMap implements the Map interface, while HashSet implements the Set interface.
  • A HashMap stores key-value pairs, and a HashSet stores objects.
  • A HashSet is slower than a HashMap.
  • A hashcode value is computed differently, in that a HashMap uses a key object and a HashSet uses its own object element.

What happens when two objects have the same HashCode?

Because the HashCode is the same, their bucket positions are the same, and a ‘collision’ occurs. Because HashMap uses a linked list to store objects, this Entry(a Map.entry object with key-value pairs) is stored in the linked list.

If two keys have the same HashCode, how do you get the value object?

When we call the get() method, the HashMap uses the hashcode of the key object to find the bucket location and then retrieves the value object. Once the bucket location is found, the keys.equals() method is called to find the correct node in the linked list and eventually the value object.

What is the problem with resizing a HashMap in multi-threaded situations?

Due to thread insecurity, multiple HashMap objects compete to resize a HashMap in multithreaded conditions, and it is not clear which one to resize. As a result, adjusting the size of the HashMap in multithreading can lead to an infinite loop, and since Java1.5 ConcurrentHashMap objects have been added to address multithreading and other issues.

What changes have been made to HashMap in JDK8?

  1. The underlying implementation in JDK7 is array + list, whereas in JDK8 we use array + list + red-black tree.
  2. In JDK7, deadlocks can occur during capacity expansion. In JDK8, deadlocks will not occur through algorithm optimization.
  3. In JDK8, the hash algorithm is simplified to improve the efficiency

Why red black trees in JDK8?

Because JDK7 uses arrays and linked lists as the underlying data structure, if there is a large amount of data, or the hash algorithm is not hash enough, the linked list may be too long, so consider an extreme case: if the hash algorithm is poor, all the elements are on the same list. So the time complexity of data query is almost the same as that of linked list query. As we know, one advantage of linked list is that it is fast to insert, but slow to query, so if a long linked list structure appears in a HashMap, the query efficiency of the whole HashMap will be affected. When we use HashMap, we need to have both insert and query efficiency, while red-black tree insert and query efficiency is between perfectly balanced binary tree and linked list, so using red-black tree is appropriate.

What is the HashMap expansion mechanism and how is JDK7 different from JDK8?

First of all, we need to know why HashMap needs to be expanded. The reason is very simple. The bottom layer of HashMap is realized by using array + linked list, and the array is allocated memory in advance. As a result, the linked list of HashMap is too long and the query efficiency is reduced, so the array needs to be expanded.

In JDK7, the HashMap expansion condition is (size >= threshold) && (null! =table[bucketIndex]), size = current capacity of HashMap, threshold = 12, table[bucketIndex] represents the element of array corresponding to the key put in, So in JDK7 expansion conditions is dangdang Put operating incoming for incoming Key values of the array is not null position and current capacity at the threshold of the greater than or equal to the capacity to make the expansion values of the array is not null position and current capacity when the greater than or equal to the threshold of the capacity to make the expansion, expansion of JDK7 idea is: Creating a new array that is twice the size of the original array and then transferring the list and elements from the array to the new array can cause deadlocks.

Capacity expansion conditions in the JDK8 are less than those in the JDK7. Capacity expansion is performed only when the current capacity is greater than or equal to the capacity expansion threshold. In addition, the roadmap for capacity expansion is complicated.

HashCode = Equals (); HashMap (); Why is that?

Related to HashMap, or because a HashMap with the object’s hashcode methods can have a relationship, because we if two objects are equal in the design of logic, if only to rewrite the Equals method, then a class, there are two objects A1, A2, their A1. Equals (A2) is true, A1. Hashcode is different from A2. Hashcode. When both A1 and A2 are used as keys of a HashMap, the HashMap will consider them to be different because the HashMap will determine whether the key has the same Hashcode when determining whether the key values are different. Hashcode is equal, so in this scenario we’re going to have a situation where we think these two objects are equal, but hashMap doesn’t think so, so there’s a problem.

What should we be aware of when using HashMap?

  1. The capacity expansion mechanism of HashMap is very inefficient. Therefore, if you can determine how many elements need to be stored in advance, it is recommended to initialize the capacity of array when initializing HashMap to prevent capacity expansion.
  2. The hashcode method of an object is used in a HashMap and is critical, so overwriting equals is recommended.
  3. If you are using an object as the key of a HashMap, make the object final to prevent the object from being reassigned, which in effect represents a new object as the key, since the two objects may have different Hashcodes.

Difference between HashMap and Hashtable

  1. HashMap is thread-safe, HashTable is thread-safe; Methods inside a HashTable are basically synchronized modified
  2. HashMap is a little more efficient than HashTable because of thread-safety issues. Also, HashTable is largely obsolete, so don’t use it in your code
  3. In a HashMap, null can be used as a key. There is only one such key, and one or more keys can be null. A NullPointerException is thrown whenever a key value in a HashTable contains a NULL.
  4. Hashmaps since JDK1.8 have made major changes in resolving hash conflicts, converting lists to red-black trees to reduce search time when the list length is greater than the threshold (8 by default). Hashtable has no such mechanism.

Finally, I wish everyone can find their own suitable work in the autumn recruitment, the apprentice!