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

How to carry out in-depth analysis and comparison of HashMap in Java? in view of this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

In the world of Java, no matter the class or all kinds of data, the processing of its structure is the key to the logic and performance of the whole program. Because I came into contact with a problem about the coexistence of performance and logic, I began to study it.

Let's take HashMap to study here.

HashMap can be described as a great utility of JDK, which maps each Object to achieve fast access to "key-value". But what is actually done in it?

Before that, let's introduce the properties of load factor and capacity. As we all know, the actual capacity of a HashMap is the factor * capacity, and its default value is 16 × 0.75 = 12; this is very important and has a certain impact on efficiency! When the number of objects stored in HashMap exceeds this capacity, HashMap reconstructs the access table. This is a big problem, which I'll introduce later. Anyway, if you already know how many objects you want to store, it's best to set it to an acceptable number for that actual capacity.

Two key methods, put and get:

First, there is such a concept, HashMap declares the Map,Cloneable, Serializable interface, and inherits the AbstractMap class. In fact, Iterator is mainly its internal class HashIterator and several other iterator class implementations, and of course, there is a very important Entry internal class that inherits Map.Entry. As we all have the source code, you can take a look at this part if you are interested. What I mainly want to explain is the Entry internal class. It contains four attributes, hash,value,key and next, which are very important. The source code of put is as follows

Public Object put (Object key, Object value) {

Object k = maskNull (key)

This is to determine whether the key value is empty, which is not very esoteric. In fact, if it is empty, it returns a static Object as the key value, which is why HashMap allows null key values.

Int hash = hash (k)

Int I = indexFor (hash, table.length)

These two consecutive steps are the best part of HashMap! I was ashamed after the study, in which hash is to hash through the hashcode of key, the Object, and then get the index value in Object table through indexFor.

Table??? Don't be surprised, in fact, HashMap is not very good, it is put with table. The best thing is to use hash to return the index correctly. As for the hash algorithm, I contacted Doug, the author of JDK, and he suggested that I take a look at "The art of programing vol3". What's hateful is that I've been looking for it before, and I can't find it. I'm even more anxious when he mentions it, but my pockets are empty!

I do not know if you have noticed that put is actually a return method, it will overwrite the put with the same key value and return the old value! The following method thoroughly illustrates the structure of HashMap, which is actually a table plus a linked list of Entry in the corresponding location:

For (Entry e = table [I]; e! = null; e = e.next) {

If (e.hash = = hash & & eq (k, e.key)) {

Object oldvalue = e.value

E.value = value; / / assign the new value to the corresponding key value.

E.recordAccess (this); / / empty method, left to be implemented

Return oldvalue; / / returns the corresponding old value of the same key value.

}

}

Number of modCount++; / / structural changes

AddEntry (hash, k, value, I); / / add new elements, the key!

Return null; / / is returned without the same key value

}

Let's analyze the key methods:

Void addEntry (int hash, Object key, Object value, int bucketIndex) {

Table [bucketIndex] = new Entry (hash, key, value, table [bucketIndex])

Because hash's algorithm may make different key values have the same hash code and the same table index, such as: key= "33" and key=Object g's hash is-8901334, then its index after indexfor must be I, so that in new, the next of this Entry will point to the original table [I], and then the next will be the same, forming a linked list, and put's loop alignment e.next to get the old value. At this point, we all quite understand the structure of HashMap, right?

If (size++ > = threshold) / / this threshold is the amount that can actually be held

Resize (2 * table.length); / / if this capacity is exceeded, the Object table will be reconstructed.

The so-called refactoring is not amazing, which is to build a table that is twice the size (I saw in other forums that someone said it was two times plus one, deceiving me), and then indexfor it one by one! Attention! This is efficiency! If you can make your HashMap do not need to be refactored so many times, the efficiency will be greatly improved!

At this point, get is much simpler than put, and everyone, it's not much better to understand put,get. For collections I think, it is suitable for a wide range, when not completely suitable for unique, if everyone's program needs a special purpose, write it yourself, it is actually very simple. (the author told me so, he also suggested that I use LinkedHashMap, I read the source code, I found that LinkHashMap is actually inherited from HashMap, and then override the corresponding method, interested colleagues, their own looklook) build an Object table, write the corresponding algorithm, ok.

For example, things like Vector,list are actually very simple, at most, there are more synchronous declarations, in fact, if you want to achieve a few inserts and deletions like Vector, you can use an Object table, access by index, add, and so on.

If you insert, delete more, you can build two Object table, and then each element contains a next structure, a table memory, if you want to insert into I, but I already have elements, connect them with next, and then size++, and record its location in another table.

This is the answer to the in-depth analysis and comparison of HashMap in Java. I hope the above content can be of some help to you. If you still have a lot of doubts to be solved, you can follow the industry information channel to learn more about it.

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.