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

This article mainly introduces "the introduction of Hash table and tree in java". In the daily operation, I believe that many people have doubts about the introduction of Hash table and tree in java. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts of "introduction of Hash table and tree in java". Next, please follow the editor to study!

HashMap in jdk1.7 is composed of Hash table (array plus linked list). After jdk1.8, it is upgraded to Hash table + red-black tree to improve the efficiency of data query. The hash table and the red-black tree are introduced below.

Hash table

In the hash table, we first introduce linear search and binary search:

Linear search

Go through all the data and find the data you need. The corresponding data structure is linear structure such as array and linked list, which is very inefficient for big data, and its time complexity is O (n). For example, the indexOf method in ArrayList:

Public int indexOf (Object o) {if (o = = null) {for (int I = 0; I < size; data +) if (elementdata [I] = = null) return I;} else {for (int I = 0; I < size; idata +) if (o.equals (elementdata [I])) return I;} return-1;}

Binary search

Dichotomy search is an improvement on linear search. For example, for [1magi 2pje 3je 4je 5pr 6pr 7pr 8], I want to search for a number (suppose it is 2). I first compare this number with 4 (this number is generally better than the number of selected digits). If it is less than 4, I find it in the left side of 4 [1m2prime3], and then compare it with 2, which is equal, and I successfully find it. The advantage of this retrieval method is that it can save a lot of unnecessary retrieval, finding only half of the elements in the collection at a time. Its time complexity is O (logn). But it also has its limitations, and his numerical arrangement itself needs to be orderly.

Hash table

All right, the point is, the Hash table shows up, which is a search with a time complexity of O (1), that is, no matter how much data you have, you only need to check it once to find the target data.

The essence of Hash table is that it can locate the element subscript of the search set through the characteristics of value itself, so as to find it quickly. The general Hash function is the length of the mod (remainder) Hash array to be deposited.

After reading the explanation above, you must have found a problem. The address you got by finding the remainder may be the same. This kind of conflict is called Hash collision, and it is very serious if the amount of data is large and the Hash bucket is small. We resolve the conflict in the following ways.

We can see that the positions of 12 and 0 conflict, and then we turn each element of the array into a chain header, and the conflicting elements are placed in the linked list, so that after finding the corresponding link header, we will follow the linked list. As for why the linked list is used to save space, the linked list is not continuously stored in memory, so we can make more full use of memory.

For the HashMap implemented by Hash table, see HashMap (JDK7) for source code analysis.

Tree

In JDK1.7, HashMap uses Hash table to store data, calculates hashcode according to key, and then calculates the position of Hash bucket with the length of Hash array.

If a lot of key have Hash conflicts, then the large amount of data in each bucket results in a very long linked list, so that the advantage of the Hash table no longer exists, but tends to be linear retrieval.

After the jdk1.8 version, java has made improvements to HashMap. When the length of the linked list is greater than 8, the later data will be stored in the red-black tree to speed up retrieval.

Before we talk about the red-black tree, let's talk about some common trees:

Binary tree

A binary tree means that there are zero one or two child nodes under each parent node. When storing data in the binary tree, the number larger than the parent node is placed on the right node, and the number smaller than the parent node is placed on the left node. In this way, we only need to compare a number with the parent node when looking for a certain number, the larger number goes to the right side and is called recursively, and the small number goes into the left recursive node. Cons: if the data itself is ordered, for example, [1, 2, 3, 4, 5, 6, 7], this will lead to an imbalance in the tree, and the binary tree will degenerate into a linked list. So we introduced the avl tree.

Balanced binary tree (AVL tree) second and third tree red and black tree

At this point, the study of "introduction to Hash tables and trees in java" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.