Java judges whether the two List are identical

Jane Book novice, the first blog, one is to consolidate, deepen the impression, and the two is to leave as a manuscript, easy to view later. There is hope to get great advice here, in order to avoid misleading.
if there is any shortage, please feel understanding and welcome to correct it. Thank you!

I. background

To meet a demand to write the project yesterday when a request for the first time save the server request back to the local List, come in next time, need to determine List and stored in local server request down the List is the same, if the same, the preservation of local use; if not, put down the local List server request coverage previously saved.
so, I outlined the outline briefly:

1, first judge whether there is any preservation in the local area, or if there is no one, then return the request to the local area;
2, there is to judge whether the requested return is equal to the number of List in the local, if not equal, then the request back of the original cover in the local preservation;
3, if equal, traverse the request down, List and List in the local preservation of each element is consistent, if inconsistent, then the request back cover originally saved in the local;
4, if the same, then do not operate, the direct use of the original preservation

However, this traversal, if the amount of data is small, is OK, and if the amount of data is large, consider the performance.

Two, actual combat (compare two Java list whether the same performance optimization)

1, the most brutal method (traverse two List)
Package com.example; import java.util.ArrayList; public class CheckDiffList static void main {public (String[] args) {List< = new; String> LIST1; String> ArrayList< List< String>) (List2 = new; ArrayList< String; > for (int) (I = 0; I 10000; < i++) {list1.add (test + I); list2.add ("test" + I * 2);} System.out.println (getDiffrent (LIST1, List2)); / / the judgment of two elements are the same in List / / getDiffrent total times / / false 2514359} / * * * List in the judgment of two elements are the same * * @param LIST1 * @param List2 private static Boolean getDiffrent * @return * (List< String> list1, List< String> List2) {long = System.nanoTime (st); if (list1.size) = list2.size ((!)) {System.out.println ("getDiffrent total times" (System.nanoTime st) - (+)); return false;} for (String str LIST1) {if (! List2.contains (STR)) {System.out.println ("getDiffrent total times" (System.nanoTime st) - (+)); return false;}} System.out.println ("getDiffrent total times" (System.nanoTime st) - (+)); return true;}}

This method, which I first thought of, is the product of two cycles of size in the total number of cycles, and it takes longer to output from the List.

2. Use the method retainAll for List in Java ()
Package com.example; import java.util.ArrayList; import java.util.List; public class CheckDiffList static void main {public (String[] args) {List< = new; String> LIST1; String> ArrayList< List< String>) (List2 = new; ArrayList< String> for; (int) (I = 0; I 10000; < i++) {list1.add (test + I); list2.add ("test" + I * 2);} System.out.println (getDiffrent2 (LIST1, List2); / / List) determine the two elements within the same is not total times 7563 / / getDiffrent2 / / false} / * * * * to determine whether the same two List elements in < p> bug; * this method is Food.class * * @param LIST1 @param * List2 * @r Eturn / private static Boolean getDiffrent2 (List< String> LIST1, List< String> List2) {long = System.nanoTime (st); System.out.println ("getDiffrent2 total times" (System.nanoTime st) - (+)); return! List1.retainAll (List2);}}

Obviously, method 2 is much less time-consuming than method 1. We can take a look at the retainAll () source code

Only the elements in / * * * Retains this list that are contained in the collection. In other * specified words, removes from this list all its elements that are * of not contained in the specified collection. C collection containing elements * * @param to be retained in this list {@code true} if this * @return list changed as a result of the call * @throws ClassCastException if the class of an element of this list incompatible with the specified * is * collection (< a href= "Collection.html# optional-restrictions" > optional< /a> @throws NullPointerException if this) * list contains a null element and the specified collection does not permit * null * elements (< a href= "Collection.html#optional-restrictions" > optional< /a> or), if the specified collection is * null * @see * Collection#contains (Object) public Boolean retainAll (Collection< C? > Objects.requireNonNull) {(c); / / private method calls the return batchRemove (C, true);} / / if the collection is due to call change, returns true / / set A compared with the intersection of private Boolean batchRemove set B (Collection< > Boolean complement? C, final Object[]) {/ / elementData = this.elementData for all elements of the current object; //w: marking the two elements of the collection of public number int r = 0, w = 0; / / set the flag Boolean modified = false; try A for (set {/ / traversal; R < size; r++) to determine whether B / / set contains a collection of the current element if in A (c.contains (elementData[r]) = complement) / / if contains directly saved. ElementData[w++] = elementData[r];} finally {/ / Preserve Behavioral Compatibility with AbstractCollection if c.contains (throws.) / / even / / c.contains (if) throws exception if (r! = size) {System.arraycopy (elementData, R, elementData, W, size and R); //w A length w as the current set = size - R;} / / if set size A changed if (W! = size) {/ / clear to let GC do its work for (int i / removal of I = w; < size; elementData[i] = null; / / i++) Record set of elements in the change of (add/remove) modCount = size - W; / / set the current array size size = w; modified = true / / return true return modified;}}};

Ha ha ha, I see the source code is not particularly understand, it is related to the keyword transient, and List (contains), System.arraycopy (Object SRC, int srcPos, Object DeST, int destPos, int length) method.

However, the conclusion is that the return value of the retainAll method: Returns FALSE if the size of the collection A array is not changed. If the collection A and the collection B are exactly the same set, they will return false. The two collection does not intersect until true is returned.
in simple terms, determine whether the two sets have an intersection, return false, and return true (this is not exact).

And why, I comment on this method is used to determine whether two is the same as List bug, Java is not to say that this method has bug, but we directly use the two list elements are the same bug judge come and go, is due to List (contains) method to the demo, List&lt, String>; if it is List< Person> you will see the difference.

In List’s contains (), the object’s equals method is called, and String copies the Object’s equals. I want to write a separate note of this. Ha ha ha, it took several hours before I realized that I could only blame myself for being too technical.

3, the use of HashMap key unique, value can repeat the characteristics of the list elements into the HashMap

We need is to determine the two List elements are the same, so it can be considered: all elements with a map list storage, the key for each element of the LIST1, the number of value for the element, then all elements of the List2 in the map, if the value+1 already exists, once value stop +1, shows the different elements, return false. Otherwise, go through all the elements in List2 until true is returned. In this way, we only need to cycle m+n times, greatly reducing the number of cycles.

Package com.example; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class CheckDiffList static void main {public (String[] args) {List< = new; String> LIST1; String> ArrayList< List< String>) (List2 = new; ArrayList< String> (for); int (I = 0; I < 10000; i++) {list1.add (test + I); list2.add ("test" + I * 2);} System.out.println (getDiffrent3 (LIST1, List2)); / / the judgment of two elements are the same in List / / getDiffrent3 total times / / false 26976244} / * * * two List in judgment elements are the same * * @param LIST1 @param * List2 * @ret Urn / private static Boolean getDiffrent3 (List< String> LIST1, List< String> List2) {long = System.nanoTime (st); Map< String, Integer> map = new HashMap< String, Integer> (list1.size) (list2.size) (+); for (String string: LIST1 {map.put (string). 1);} for (String string List2) {Integer CC = map.get (string); if (CC! = null) {map.put (string, ++cc); continue;} System.out.println ("getDiffrent3 total times" (System.nanoTime st) - (+)); return false;} System.out.println ("getDiffrent3 total times + (System.nanoTime) - (st)); return true; }}

This method also reviews HashMap, which uses key-value to map and store data. Key must be unique, and value can be repeated. HashMap is asynchronous, so threads are unsafe. Oh, I didn’t understand HashMap too deeply before

Observation method 3. We just randomly picked up a list as the first addition standard, so once our List2 is larger than LIST1’s size, then our second put if judgment will be time-consuming, so there’s method 4:

4. Improved version of method 3 (first to determine the size size of LIST1 and List2)
Package com.example; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class CheckDiffList static void main {public (String[] args) {List< = new; String> LIST1; String> ArrayList< List< String>) (List2 = new; ArrayList< String> (for); int (I = 0; I < 10000; i++) {list1.add (test + I); list2.add ("test" + I * 2);} System.out.println (getDiffrent4 (LIST1, List2)); / / the judgment of two elements are the same in List / / getDiffrent4 total times / / false 37313357} / * * * two List in judgment elements are the same * * @param LIST1 @param * List2 * @ret Urn / private static Boolean getDiffrent4 (List< String> LIST1, List< String> List2) {long = System.nanoTime (st); Map< String, Integer> map = new HashMap< String, Integer> (list1.size) (list2.size) (+); List< String> maxList = LIST1; List< String> minList = List2; if (list2.size) (>); (list1.size) {maxList = List2; minList = LIST1;} for (String string maxList) {map.put (string, 1);} for (String string minList) {Integer CC = map.get (string); if (CC! = null) {map.put (string, ++cc); continue return false;}; } System.out.println ("getDiffrent4, total, times" + (System.nanoTime () - st)); return true;}

Method 4 to determine the size of the two list, small in the last add, this will reduce the cycle of judgment, and performance has been improved! But in this case, the method 4 takes longer than the method 3, and my understanding is that you’ve done more than once to judge the size of the two sets of size, but I think this performance can be sacrificed.

Method 3 and method 4 all have the same problem: if there is a repeating element in a list, the method fails because map does not allow the same key!

Three summary

Comparing the above 4 methods, time-consuming getDiffrent2< getDiffrent1< getDiffrent3< getDiffrent4;, method 4 than method more than 3 a judgment, more time-consuming, I can understand, why 3 and 4 than time consuming?

Write write write Meng force, the first time to write a blog, originally want to discuss the performance of the 4 methods, the results of the two list provides the judgment whether the same 4 methods, welcome you. God, oh.

The following is the complete code (note that this class is best not to run as a whole, because method 2 will change the contents of list, and suggest running 1, 2, 3, 4 methods respectively)

Package com.example; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class CheckDiffList static void main {public (String[] args) {List< = new; String> LIST1; String> ArrayList< List< String>) (List2 = new; ArrayList< String> (for); int (I = 0; I < 10000; i++) {list1.add (test + I); list2.add ("test" + I * 2);} System.out.println (getDiffrent (LIST1, List2); System.out.println (getDiffrent2) (LIST1, List2); System.out.println (getDiffrent3) (LIST1, List2); System.out.println (getDiffrent4 (LIST1). List2)); / / the judgment of two elements are the same in List / getDi Ffrent total times 2514359 getDiffrent2 total times / / false / / 7563 / / false / / getDiffrent3 total times 26976244 getDiffrent4 total times / / false / / 37313357 / / false} / * * * List in the judgment of two elements are the same * * @param LIST1 @param * List2 * return * private static Boolean @ getDiffrent4 (List< String> LIST1, List< String> List2; long) {st = System.nanoTime (String, Integer>); Map< new; map = HashMap< String, Integer> (list1.size) (list2.size) (+); List< String> maxList = LIST1; List< String> minList = List2; if (list2.size (>); Li (st1.size)) {maxList = List2; minList = LIST1;} for (String string maxList) {map.put (string, 1);} for (String string minList) {Integer CC = map.get (string); if (CC! = null) {map.put (string, ++cc); continue;} System.out.println ("getDiffrent4 total times" (System.nanoTime st) - (+)); return false;} System.out.println ("getDiffrent4 total times" (System.nanoTime st) - (+)); return true;} / * * * to determine the two elements are the same in List * * @param LIST1 @param * List2 * @return * private static Boolean getDi Ffrent3 (List< String> LIST1, List< String> List2) {long = System.nanoTime (st); Map< String, Integer> map = new HashMap< String, Integer> (list1.size) (list2.size) (+); for (String string LIST1) {map.put (string, 1);} for (String string List2) {Integer CC = map.get (string); if (CC! = null) {map.put (string, ++cc); continue;} System.out.println ("getDiffrent3 total times" (System.nanoTime st) - (+)); return false;} System.out.println ("getDiffrent3 total times" (+ System.nanoTime (-) st)); return true;} / * * * two List in judgment Whether the same * * < p> this method is bug Food.class * * @param LIST1 @param * List2 * @return * private static Boolean getDiffrent2 (List< String> LIST1, List< String> List2) {long = System.nanoTime (st); System.out.println ("getDiffrent2 total times" (System.nanoTime st) - (+)); return! List1.retainAll (List2);} / * * * List in the judgment of two elements are the same * * @param LIST1 @param * List2 * @return * private static Boolean getDiffrent (List< String> LIST1, List< String> List2) {long = System.nanoTime (st); if (list1.size) = (! (list2.size)) {System.out.println ("getDiffrent "Times + Total (System.nanoTime) - (st)); return false;} for (String str LIST1) {if (! List2.contains (STR)) {System.out.println (" getDiffrent total times "(System.nanoTime st) - (+)); return false;}} System.out.println (" getDiffrent total times "+ (System.nanoTime) - (st)); return true;}}

This article refers to http://www.cnblogs.com/czpblog/archive/2012/08/06/2625794.html
http://www.cnblogs.com/lyajs/p/5737410.html