這陣子工作上的時候又遇到一個要從兩個List中找出相同Id，然後 Assign 給對方的那種，正當我準備再寫個Double-ForEach來解決這個問題時，腦中突然被這種很醜的寫法給噁心到了，頓時間在想
「肯定有更好的方式吧」
於是就想到了HashMap，我知道取出Map的時間複雜度為O(1)，但這是保證都是O(1)嗎？還是說只有用index查找，例如get(1)這種才快呢？老實說我不是很清楚，另外我如果要用HashMap，我勢必要先把List的內容put到Map中，那這樣跟我直接用Double-ForEach查找來講，是不是會更慢呢？於是今天打算來研究一下，我的想法很簡單，創造10,000,000個UID，並分別放到List跟Map，最後取出最後新增的UID，來比較兩者之間的速度
程式碼如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| public static void main(String[] args) {
System.out.println("開始執行");
HashMap<String, String> stringStringHashMap = new HashMap<>();
List<String> uuidList = new ArrayList<>();
String theLastUid="";
long inputStartTime = System.currentTimeMillis();
for(int i =0;i<10_000_000;i++){
String uid = new UID().toString();
stringStringHashMap.put(uid,uid);
uuidList.add(uid);
theLastUid=uid;
}
long inputEndTime = System.currentTimeMillis();
System.out.println("資料塞完耗時" +(inputEndTime - inputStartTime));
System.out.println("=======");
long mapStartTime = System.currentTimeMillis();
String mapString = stringStringHashMap.get(theLastUid);
long mapEndTime = System.currentTimeMillis();
System.out.println("Map耗時 :"+(mapEndTime - mapStartTime));
System.out.println("Map撈出來的" + mapString);
System.out.println("=======");
long listStartTime = System.currentTimeMillis();
String finalTheLastUid = theLastUid;
String listString = uuidList.stream().filter(s -> s.equals(finalTheLastUid)).findFirst().orElse(null);
long listEndTime = System.currentTimeMillis();
System.out.println("List耗時 :"+(listEndTime - listStartTime));
System.out.println("List撈出來的 = " + listString);
}
|
最後輸出的結果
1
2
3
4
5
6
7
8
| 開始執行
資料塞完耗時2228
=======
Map耗時 :0
Map撈出來的-122815f4:190363175b6:1717
=======
List耗時 :103
List撈出來的 = -122815f4:190363175b6:1717
|
沒想到Map查詢的速度居然是List的無限倍！那接下來我要驗證看看，Map雖然比較快，但是在塞資料這件事情上面，會不會Map消耗的時間比List還多，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static void main(String[] args) {
System.out.println("開始執行");
HashMap<String, String> stringStringHashMap = new HashMap<>();
List<String> uuidList = new ArrayList<>();
String theLastUid="";
long inputStartTime = System.currentTimeMillis();
for(int i =0;i<10_000_000;i++){
String uid = new UID().toString();
stringStringHashMap.put(uid,uid);
}
long inputEndTime = System.currentTimeMillis();
System.out.println("Map資料塞完耗時" +(inputEndTime - inputStartTime));
System.out.println("=======");
long inputStartTime2 = System.currentTimeMillis();
for(int i =0;i<10_000_000;i++){
String uid = new UID().toString();
uuidList.add(uid);
theLastUid=uid;
}
long inputEndTime2 = System.currentTimeMillis();
System.out.println("List資料塞完耗時" +(inputEndTime2 - inputStartTime2));
}
|
1
2
3
4
| 開始執行
Map資料塞完耗時2288
=======
List資料塞完耗時1656
|
可以看到我的想法確實沒錯，塞到hashMap確實比單純塞到List耗時還要長，因為還要處理哈希碰撞的問題，但相對來說，Map跟List塞進去的性能差異並沒有到搜尋的差異那麼大，而且這只是在只需要搜尋一次的場景，如果單一方法有需要搜尋兩次的話，那麼設定成Map確實是個不錯的解法。
