簡(jiǎn)書(shū)新手，第一次寫(xiě)博客眉踱，一是為了鞏固一下挤忙，加深印象，二是留作一個(gè)底稿谈喳，方便以后查看册烈。還有呢，就是希望在這里能得到大神得指點(diǎn)婿禽，以免誤人子弟赏僧。
如有不足，敬請(qǐng)諒解扭倾，歡迎指正淀零，謝謝！
一膛壹、背景
昨天寫(xiě)項(xiàng)目時(shí)遇到一個(gè)需求驾中，要求第一次把服務(wù)端請(qǐng)求回來(lái)的List保存到本地，下次進(jìn)來(lái)模聋，需要判斷服務(wù)端請(qǐng)求下來(lái)的List與本地保存的List是否相同肩民，如果相同，則使用本地保存的链方；如果不同持痰，則把服務(wù)端請(qǐng)求下來(lái)的List覆蓋本地原先保存的。
so祟蚀，我簡(jiǎn)單列了一下提綱：
1工窍、先判斷本地中是否有保存的， 沒(méi)有則把請(qǐng)求回來(lái)的保存的到本地中前酿；
2移剪、有則判斷請(qǐng)求回來(lái)的與本地中List個(gè)數(shù)是否相等 若不相等，則把請(qǐng)求回來(lái)的覆蓋原先在本地中保存的薪者；
3、若相等剿涮，遍歷請(qǐng)求下來(lái)List與本地中保存的List各個(gè)元素是否一致 若不一致言津，則把請(qǐng)求回來(lái)的覆蓋原先在本地中保存的；
4取试、若一致悬槽，則不做操作，直接使用原先保存的
然而瞬浓，這樣遍歷如果數(shù)據(jù)量小還好初婆，如果數(shù)據(jù)量大的話(huà)就得考慮一下性能了。
二、實(shí)戰(zhàn)（比較兩個(gè)Java list是否相同的性能優(yōu)化）
1磅叛、最粗暴的方法 (遍歷兩個(gè)List)
package com.example;
import java.util.ArrayList;
public class CheckDiffList {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
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));
// 判斷兩個(gè)List內(nèi)的元素是否相同
// getDiffrent total times 2514359
// false
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent(List<String> list1, List<String> list2) {
long st = System.nanoTime();
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;
}
}
這種方法也就是我最初想到的屑咳，總共要循環(huán)的次數(shù)是兩個(gè)List的size的乘積，從輸出看耗時(shí)也是比較長(zhǎng)的弊琴。
2兆龙、利用Java中為L(zhǎng)ist提供的方法retainAll()
package com.example;
import java.util.ArrayList;
import java.util.List;
public class CheckDiffList {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
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));
// 判斷兩個(gè)List內(nèi)的元素是否相同
// getDiffrent2 total times 7563
// false
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
* <p>
* 此方法有bug 見(jiàn)Food.class
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent2(List<String> list1, List<String> list2) {
long st = System.nanoTime();
System.out.println("getDiffrent2 total times " + (System.nanoTime() - st));
return !list1.retainAll(list2);
}
}
很顯然，方法2比方法1耗時(shí)少很多敲董。我們可以來(lái)看看retainAll()的源碼
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified 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);
//調(diào)用自己的私有方法
return batchRemove(c, true);
}
//如果此 collection 由于調(diào)用而發(fā)生更改紫皇，則返回 true
//集合A比較與集合B的交集
private boolean batchRemove(Collection<?> c, boolean complement) {
//獲得當(dāng)前對(duì)象的所有元素
final Object[] elementData = this.elementData;
//w：標(biāo)記兩個(gè)集合公共元素的個(gè)數(shù)
int r = 0, w = 0;
//設(shè)置標(biāo)志位
boolean modified = false;
try {
//遍歷集合A
for (; r < size; r++)
//判斷集合B中是否包含集合A中的當(dāng)前元素
if (c.contains(elementData[r]) == complement)
//如果包含則直接保存。
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
// 如果 c.contains() 拋出異常
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
//w為當(dāng)前集合A的length
w += size - r;
}
//如果集合A的大小放生改變
if (w != size) {
// clear to let GC do its work
// 清除工作
for (int i = w; i < size; i++)
elementData[i] = null;
//記錄集合中元素的改變(add/remove)
modCount += size - w;
//設(shè)置當(dāng)前數(shù)組的大小
size = w;
//返回為true
modified = true;
}
}
return modified;
}
哈哈哈腋寨，源碼我看得也不是特別懂聪铺，里邊有涉及到關(guān)鍵字transient，還有List的contains()萄窜、System.arraycopy(Object src, int srcPos,Object dest, int destPos, int length)方法铃剔。
不過(guò)結(jié)論是retainAll方法的返回值：如果集合A數(shù)組的大小沒(méi)有改變，則返回false脂倦。如果集合A和集合B是完全相同的集合番宁，也會(huì)返回false。兩個(gè)集合沒(méi)有交集赖阻，才會(huì)返回true蝶押。
簡(jiǎn)單來(lái)說(shuō)，判斷兩個(gè)集合是否有交集火欧，有則返回false棋电，無(wú)則返回true（這句話(huà)不嚴(yán)謹(jǐn)）。
還有為什么苇侵，我的注釋上此方法用來(lái)判斷兩個(gè)List是否相同有bug赶盔，并不是說(shuō)java這個(gè)方法有bug，而是我們直接使用來(lái)去判斷兩個(gè)list元素是否相同有bug榆浓，是由于List的contains()的方法導(dǎo)致的于未，這個(gè)demo中是List<String>，假如是List<Person>就會(huì)看到差別了陡鹃。
List的contains()中調(diào)用的是object的equals方法烘浦，而String復(fù)寫(xiě)了Object的equals。這個(gè)我想另起一文來(lái)單獨(dú)記錄萍鲸。哈哈哈闷叉，前后花了好幾個(gè)小時(shí)才搞明白，只能怪自己技術(shù)太菜脊阴。
3握侧、利用HashMap key唯一蚯瞧，value可以重復(fù)的特點(diǎn)，把list中各元素放到HashMap中
我們的需求是判斷兩個(gè)List中的元素是否相同,那么可以這樣考慮：用一個(gè)map存放list的所有元素品擎，其中的key為list1的各個(gè)元素埋合，value為該元素出現(xiàn)的次數(shù),接著把list2的所有元素也放到map里，如果已經(jīng)存在則value+1孽查，一旦value停止+1饥悴，說(shuō)明有元素不同了，返回false盲再。否則一直遍歷直至list2中所有元素西设，返回true。這樣我們只需循環(huán)m+n次答朋，大大減少了循環(huán)的次數(shù)贷揽。
package com.example;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CheckDiffList {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
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));
// 判斷兩個(gè)List內(nèi)的元素是否相同
// getDiffrent3 total times 26976244
// false
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent3(List<String> list1, List<String> list2) {
long st = System.nanoTime();
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;
}
}
（此方法又復(fù)習(xí)了HashMap使用key-value來(lái)映射和存儲(chǔ)數(shù)據(jù)，Key必須惟一梦碗，value可以重復(fù)禽绪。HashMap是非同步的，所以線程不安全洪规。呵呵印屁，我之前對(duì)HashMap的理解也不夠深。）
觀察方法3我們只是隨機(jī)取了一個(gè)list作為首次添加的標(biāo)準(zhǔn)斩例，這樣一旦我們的list2比list1的size大雄人，則我們第二次put時(shí)的if判斷也會(huì)耗時(shí)，所以有了方法4：
4念赶、方法3的改進(jìn)版（首先去判斷l(xiāng)ist1础钠、list2的size大小）
package com.example;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CheckDiffList {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
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));
// 判斷兩個(gè)List內(nèi)的元素是否相同
// getDiffrent4 total times 37313357
// false
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent4(List<String> list1, List<String> list2) {
long st = System.nanoTime();
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;
}
}
方法4對(duì)兩個(gè)list的大小進(jìn)行了判斷叉谜，小的在最后添加旗吁，這樣會(huì)減少循環(huán)里的判斷，性能又有了一定的提升停局！ 但本例中方法4比方法3耗時(shí)還要長(zhǎng)很钓，我的理解是多做了一次判斷兩個(gè)集合size大小的判斷，但是我覺(jué)得這個(gè)性能可以犧牲董栽。
方法3和方法4都有共同的一個(gè)問(wèn)題：假如某個(gè)list中有重復(fù)元素的話(huà)码倦，由于map不允許有相同的key，所以方法失效裆泳！
三、小結(jié)
比較以上4種方法柠硕，耗時(shí)排行g(shù)etDiffrent2<getDiffrent1<getDiffrent3<getDiffrent4工禾，方法4比方法3多了一次判斷运提，更耗時(shí)我可以理解，為什么3和4比1還耗時(shí)呢闻葵？
寫(xiě)的寫(xiě)的自己都寫(xiě)懵逼了民泵，第一次寫(xiě)博客，原本是想探討一下這4種方法的性能槽畔，結(jié)果成了提供了判斷兩個(gè)list是否相同的4種方法栈妆，歡迎各位大神指正，呵呵噠厢钧。
以下是完整的代碼(注意這個(gè)類(lèi)最好不要整體運(yùn)行鳞尔，因?yàn)榉椒?會(huì)改變list內(nèi)的內(nèi)容，建議分別運(yùn)行1早直、2寥假、3、4方法)
package com.example;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CheckDiffList {
public static void main(String[] args) {
List<String> list1 = new ArrayList<String>();
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));
// 判斷兩個(gè)List內(nèi)的元素是否相同
// getDiffrent total times 2514359
// false
// getDiffrent2 total times 7563
// false
// getDiffrent3 total times 26976244
// false
// getDiffrent4 total times 37313357
// false
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent4(List<String> list1, List<String> list2) {
long st = System.nanoTime();
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;
}
System.out.println("getDiffrent4 total times " + (System.nanoTime() - st));
return false;
}
System.out.println("getDiffrent4 total times " + (System.nanoTime() - st));
return true;
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent3(List<String> list1, List<String> list2) {
long st = System.nanoTime();
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;
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
* <p>
* 此方法有bug 見(jiàn)Food.class
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent2(List<String> list1, List<String> list2) {
long st = System.nanoTime();
System.out.println("getDiffrent2 total times " + (System.nanoTime() - st));
return !list1.retainAll(list2);
}
/**
* 判斷兩個(gè)List內(nèi)的元素是否相同
*
* @param list1
* @param list2
* @return
*/
private static boolean getDiffrent(List<String> list1, List<String> list2) {
long st = System.nanoTime();
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;
}
}
本文參考http://www.cnblogs.com/czpblog/archive/2012/08/06/2625794.html
http://www.cnblogs.com/lyajs/p/5737410.html
