Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "what are the questions that will be asked in the HashMap interview?" in the operation of the actual case, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Set family

Before we talk about Map, let's take a look at Set.

We have learned the concept of set in junior high school mathematics, that is, there can be no repetitive elements, and it is the same here.

Set is an interface in Java. You can see that it is a collection framework class in the java.util package. There are many specific implementation classes:

Among them, there are three commonly used ones:

HashSet: use Hashmap's key to store elements, the main feature is disorder, the basic operation is O (1) time complexity, very fast.

LinkedHashSet: this is a HashSet + LinkedList structure characterized by the time complexity of O (1) and the ability to retain the order of insertion.

TreeSet: uses the red-black tree structure, the characteristic is can be ordered, can use the natural sort or the custom comparator to sort; the disadvantage is that the query speed is not as fast as HashSet.

Map family

Map is a key-value pair (Key-Value pairs), in which key cannot be repeated. After all, key in set must be stored in it.

Then corresponding to Set, Map also has these three implementation classes:

HashMap: corresponding to HashSet, it is also unordered, O (1).

LinkedHashMap: this is a "HashMap + two-way linked list" structure, the foothold is HashMap, so it has all the features of HashMap and can have order.

TreeMap: is ordered, essentially using a binary search tree to achieve.

Principle of HashMap implementation

For each key in HashMap, first calculate a hash value through hash function, this hash value represents the number in buckets, and buckets is actually implemented in an array, so take the length of the array on this numerical model to get its index in the array, so put it in the array.

So here are a few questions:

If different elements calculate the same hash value, how do you store it?

A: this is a hash collision, where multiple key correspond to the same bucket.

How do you ensure the uniqueness of an element in HashMap? That is, will different hashes be calculated for the same element?

Answer: the uniqueness of the element is guaranteed through the hashCode () and equals () methods.

How to break if there are too many pairs and too little buckets?

Answer: Rehasing. That is, when there are too many collisions, the array will be expanded to twice the size (default). So although the hash value has not changed, but because the length of the array has changed, the calculated index will be changed and will be assigned to different positions, so we don't have to huddle together. I'll see you guys.

So when will it be rehashing? That is, how to measure whether the barrel is crowded enough to expand capacity?

Answer: load factor. That is, divide the number of pair by the number of buckets, that is, the average number of pairs in each barrel. The default value in Java is 0.75f, and if this value is exceeded, it will rehashing.

About hashCode () and equals ()

If the hashCode () value of key is the same, then it is possible that hash collision is going to happen, or that you have actually encountered another self. So how to judge? Continue to compare with equals ().

That is to say,

HashCode () determines the number of key in this bucket, that is, the index in the array.

Equals () is used to compare whether two object are the same.

So how to answer this classic interview question:

Why override the equals () method, but definitely override hashCode ()?

A: first of all, we have an assumption: the hashCode of any two object is different.

Well, under this condition, two object are equal, then if you do not rewrite hashCode (), the calculated hash values are not the same, you will go to different buckets, you will be lost in the vast crowd, and you can no longer recognize each other, which contradicts the equals () condition.

Scatter flowers?

Next, let's take a closer look at these two methods:

In fact, both the hashCode () and equals () methods are defined in the ancestor of Object class. Object is the ancestor of all class in Java.

So since it's for nothing, let's first take a look at what's in the gift bag, Google Object's Oracle document:

So all these methods can be used directly.

Going back to hashCode () and equals (), if the new class does not override these two methods, it inherits the definition in Object class by default.

Let's click in to see how equals () is defined:

Take notes:

The equals () method is to compare whether the two references point to the same object.

Huh? Are you kidding me? Isn't that the same as =?

Add:

The symbol of the size that we often use.

If it is primitive type, then = = is the size of the comparison value.

If it is reference type, then compare whether the two reference point to the same object.

Add:

Java data types can be divided into two types:

There are only 8 species of Primitive type: byte, short, int, long, float, double, char, boolean.

The others are all Reference type.

So although Java claims to be "Everything is object", there are non-object data types.

I don't believe it. I'm going to go to the source code to see how it works.

Ha, really, after going around for such a long time, equals () is realized with = =!

Then why did you come up with such a method?

A: in order for you to override~

For example, generally speaking, when we compare strings, we want to compare the contents of these two strings, so:

Str1 = "tianxiaoqi"; str2 = new String ("tianxiaoqi"); str1 = = str2; / / return falsestr1.equals (str2); / / return true

Because the equals () method is overridden in String:

The ancestors left it to you for your own use, and if you don't use it, they also provide a default method, which is good enough.

All right, let's take a look at the introduction of hashCode ():

As for what hashCode () returns, it doesn't have much to do with this article. Interested students can refer to this article. The conclusion is:

What is returned is not necessarily the (virtual) memory address of the object, depending on the specific implementation of the runtime library and JVM.

However, no matter how it is implemented, you need to follow the convention on the document, that is, a unique hash value will be returned for different object.

Detailed explanation of Hash conflict

Generally speaking, there are two kinds of solutions to hash conflicts.

Separate chaining

Open addressing

The first kind of Separate chaining is used in Java, that is, a "chain" is added to the bucket where the collision occurred, and the specific data structure used by this "chain" varies slightly from version to version:

In JDK1.6 and 1.7, it is stored in a linked list, so if there are many collisions, it becomes a search on the linked list, and worst case is O (n).

It is optimized in JDK 1.8. when the length of the linked list is larger (more than 8), the red-black tree will be used to store it, which greatly improves the search efficiency.

(in other words, this really likes the exam, has been asked in many interviews, and the interviewer asked why the red-black tree is used only when it is more than "8".

The second method, open addressing, is also a very important idea, because in real distributed systems, there are many places where the idea of hash is used but not suitable for seprate chaining.

This method is a sequential search, and if the bucket is already occupied, continue to look for the next unoccupied bucket "in some way" until you find the first one.

Empty

As shown in the figure, there is a hash conflict between John Smith and Sandra Dee, which is calculated to 152barrel, so Sandra goes to the next vacancy-153bucket, which will also affect the later key: the Ted Baker calculation result should have been placed on 153rd, but since it has been occupied by Sandra, it can only go to the next vacant seat, so it is 154th.

This method is called Linear probing linear probe, which, as shown in the image above, looks for the next vacancy one by one. Of course, there are other ways, such as to find the square, or Double hashing.

Basic operation of HashMap

The basic operations of each data structure are nothing more than adding, deleting, modifying and querying these four, as far as HashMap is concerned

Added: put (K key, V value)

Delete: remove (Object key)

Change: still use put (K key, V value)

Check: get (Object key) / containsKey (Object key)

Careful students may have found out why some key types are Object and some are K? This is not because of equals ().

This is because you don't necessarily use the same object when you use get/remove.

Remember that str1 and str2 are both examples of Tian Xiaoqi? For example, when I first put (str1, value) and then use get (str2), I also want to get the value corresponding to tianxiaoqi! You can't forget me just because I changed my clothes. Therefore, in get/remove, there is no great restriction on the type of key, which is convenient for another person to recognize.

In fact, the operation process of these API is more or less the same. Let's take the most complex put (K key, V value) as follows:

First of all, you need to get the index of the location in the array.

How do I find index? here we can use getIndex () method to do this alone.

Exactly how to do this is the value calculated by hash function, the length of the array on the module.

So when we get the Node in this position, we start to traverse the LinkedList, which is the operation on the linked list.

Update value if you can find it.

If you can't find it, put it on the linked list, either on the head or at the end. I usually like to put it on the head, because the newly added elements are always more likely to be used, but it does not affect the time complexity.

The code is as follows:

Public V put (K key, V value) {int index = getIndex (key); Node node = array [index]; Node head = node; while (node! = null) {/ / originally this key exists, only the update value if (checkEquals (key, node)) {V preValue = node.value Node.value = value; return preValue;} node = node.next;} / / the difference between node Node newNode = newNode (key, value); newNode.next = head; array [index] = newNode; return null;} and Hashtable is added

This is an age exposure patch, the relationship between HashMap and Hashtable, just like ArrayList and Vector, and StringBuilder and StringBuffer.

Hashtable is the interface provided by the early JDK, and HashMap is the new version; the most significant difference between them is that Hashtable is thread-safe and HashMap is not thread-safe.

This is because the data structure is allowed not to consider the problem of thread safety after Java 5.0. in practice, we find that it is not necessary to lock on the data structure. Locking and locking are expensive in the system, and internal locks sometimes become the bottleneck of the program.

So HashMap, ArrayList, StringBuilder no longer consider the issue of thread safety, the performance has improved a lot, of course, the problem of thread safety has been transferred to us programmers.

Another difference is that HashMap allows null values in key, but Hashtable does not. The advantage is that you can give a default value.

This is the end of the content of "what are the questions to be asked in the HashMap interview". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.