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

This article mainly introduces the example analysis of Java data organization and search collection, which is very detailed and has certain reference value. Friends who are interested must finish reading it!

Concept

Parallel lookup set is a tree data structure, which is used to deal with the merge and query of some disjoint sets (so-called union, lookup). For example, we can use and search sets to determine how many trees there are in a forest, whether a node belongs to a tree, and so on.

The main function of the parallel search set is to find the number of connected branches (if all the points in a graph are reachable (directly or indirectly connected), then the number of connected branches of the graph is 1; if the graph has two subgraphs that are all reachable, then the number of connected branches of the graph is 2. )

In real life, there are also some concepts that exist and collect, such as the character relationship in the recent "The Demi-Gods & Semi-Devils". You may not know some small potatoes of the gang, but you must know Qiao Feng, the master of the gang. When you see a beggar, you will think that his boss is the master Qiao Feng. In a scene like this, you will have a certain sense of belonging and automatically think that beggar is merged with the beggar gang.

To put it simply, to look up a set is to classify some data so that the data is in one group and that data is in another group. How to tell whether two of the data are in the same group? We will go to the representatives of each group to see if the representatives of the two data are the same. If so, it is in a group; if not, it is not in a group. So the general framework of the search set is as follows:

/ / and look up the general framework-the data in the code (Node), which can be other, such as binary tree nodes, edges of the graph, nodes, etc. Abstract data public class UnionSet {private HashMap fatherMap; / / key represents the current data, and value indicates who the data represents (father) private HashMap sizeMap / / represents the size of the current group (collection) public UnionSet () {/ / constructor fatherMap = new HashMap (); sizeMap = new HashMap () } public void makeSet (List list) {/ / generate initialization state and look up the set. At the beginning, each data is independent} public boolean isSameSet (Node node1, Node node2) {/ / to determine whether the two data are in the same group. } private Node findFather (Node node) {/ / find this data, who is the representative of that group (father)? } public void union (Node node1, Node node2) {/ / put these two data into a group}}

The above is the general framework, and there are several methods: initializing and checking the set, determining whether it is a group, finding a representative, and merging into a group. There are four ways, that is, to check the collection. Is it simple?

And the search set can achieve O (1) in time complexity when judging whether two data are in the same group, so this data structure is still very useful.

Implement initialization and lookup set

Let's start with the first method: initialize and look up the set.

The parameters passed in may not be List, but can also be Collection, and so on, indicating a set of data! First of all, we have only two member variables, which are the representative of the storage node and the current size of the group. At the time of initialization, we think that each node is a group of its own, that is to say, its own group represents itself; if it is big or small, it is itself, that is, 1.

/ / initialize and look up public void makeSet (List list) {if (list = = null) {return;} fatherMap.clear (); sizeMap.clear (); / / first empty the table / / traverse list, and put each node in the hash table for (Node node: list) {fatherMap.put (node, node) / / the first parameter is the node itself, and the second parameter is the representative of the group sizeMap.put (node, 1); / / the first parameter is the representative of the group, and the second parameter is the size}}

To determine whether it is the same group.

IsSameSet is relatively simple, is to determine the two data on behalf of the group, is not a data can be used! If the representative is the same person, it is in the same group, and vice versa!

/ / determine whether it is the same group public boolean isSameSet (Node node1, Node node2) {if (node1 = = null | | node2 = = null) {return false;} return findFather (node1) = = findFather (node2); / / find their respective representative nodes to see if they are the same. } find the representative node of the current node

FindFather, I think, is the core of the search set, which is also the main factor that the time complexity of the search of the search set can be in O (1).

The idea is the same as the binary tree's idea of finding the root node up, that is, it keeps searching in fatherMap until the representative node (parent node) of a node is itself. Then the most critical step is path compression. In the process of looking up, we need to record all the nodes along the way. After the search is over, we will modify these nodes in fatherMap and directly write the representative nodes of these nodes as the representative nodes of this group. We may be confused. See the following figure:

With this design, the time complexity of the search can be controlled at O (1).

/ / find the representative node, and do path compression private Node findFather (Node node) {if (node = = null) {return null;} / / find the representative node Stack path = new Stack (); / / store the node while along the way (node! = fatherMap.get (node)) {/ / means that the node is not itself, then continue to search for path.push (node) Node = fatherMap.get (node);} / path compression while (! path.isEmpty ()) {Node tmp = path.pop (); fatherMap.put (tmp, node); / / node at this time is the representative node of this group} return node;} merge operation

Finally came the final operation: merging. Merging is also relatively easy, remember one important point: the group hangs under the large group. In other words, this node belongs to a smaller group, and we "hang" it directly under another group. To put it simply: the vaule domain of this group represents the node and points directly to the representative node of another group.

/ / merge operation public void union (Node node1, Node node2) {if (node1 = = null | | node2 = = null) {return;} int node1Size = sizeMap.get (node1); int node2Size = sizeMap.get (node2); / / get the group size of the two nodes Node node1Father = fatherMap.get (node1); Node node2Father = fatherMap.get (node2) / / get the representative node if (node1Father! = node2Father) {/ / two nodes that are not in the same group, merge if (node1Size < node2Size) {/ / node1 and hang in node2 fatherMap.put (node1Father, node2Father); sizeMap.put (node2Father, node1Size + node2Size); / / New group, the size is the sum of the original two groups and sizeMap.remove (node1Father) Delete} else {/ / node2 hanging on node1 / / similar to fatherMap.put (node2Father, node1Father); sizeMap.put (node1Father, node1Size + node2Size); sizeMap.remove (node1Father) The above is all the contents of the article "sample Analysis in Java data institutions and collections". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.