Java里多個(gè)Map的性能比較

1、Java里多個(gè)Map的性能比較（TreeMap、HashMap、ConcurrentSkipListMap）問(wèn)題：比較Java原生的 3種Map的效率。1. TreeMap2. HashMap3. ConcurrentSkipListMap結(jié)果：模擬150W以?xún)?nèi)海量數(shù)據(jù)的插入和查找，通過(guò)增加和查找兩方面的性能測(cè)試，結(jié)果如下：Map類(lèi)型插入查找（在100W數(shù)據(jù)量中）10W50W100W150W0-1W0-25W0-50WConcurrentSkipListMap62 ms227 ms433 ms689ms7 ms80 ms119 msHashMap 18 ms93 ms217 ms303ms2

2、ms13 ms45 msTreeMap 33 ms228 ms429 ms584 ms4ms34 ms61 ms分析說(shuō)明圖1- 1常數(shù)和logn函數(shù)效率對(duì)比示例圖（橫軸-n數(shù)據(jù)量，縱軸-f(n)時(shí)間）TreeMap基于紅黑樹(shù)（一種自平衡二叉查找樹(shù)）實(shí)現(xiàn)的，時(shí)間復(fù)雜度平均能達(dá)到O(log n)。HashMap是基于散列表實(shí)現(xiàn)的，時(shí)間復(fù)雜度平均能達(dá)到O(1)。ConcurrentSkipListMap是基于跳表實(shí)現(xiàn)的，時(shí)間復(fù)雜度平均能達(dá)到O(log n)。如圖所示：當(dāng)數(shù)據(jù)量增加時(shí)，HashMap會(huì)引起散列沖突，解決沖突需要多花費(fèi)一些時(shí)間代價(jià)，故在f(n)=1向上浮動(dòng)。隨著數(shù)據(jù)量的增加，HashMa

3、p的時(shí)間花費(fèi)小且穩(wěn)定，在單線(xiàn)程的環(huán)境下比TreeMap和ConcurrentSkipListMap在插入和查找上有很大的優(yōu)勢(shì)。(1) TreeMap與HashMap相比較 HashMap里面存入的鍵值對(duì)在取出的時(shí)候是隨機(jī)的，它根據(jù)鍵的HashCode值存儲(chǔ)數(shù)據(jù),根據(jù)鍵可以直接獲取它的值，具有很快的訪(fǎng)問(wèn)速度。在Map 中插入、刪除和定位元素，HashMap是最好的選擇。 TreeMap取出來(lái)的是排序后的鍵值對(duì)。插入、刪除需要維護(hù)平衡會(huì)犧牲一些效率。但如果要按自然順序或自定義順序遍歷鍵，那么TreeMap會(huì)更好。本測(cè)試增加和查找功能，HashMap比TreeMap的效率要高。(2) TreeMap

4、與ConcurrentSkipListMap相比較 Skip list(跳表）是一種可以代替平衡樹(shù)的數(shù)據(jù)結(jié)構(gòu)，默認(rèn)是按照Key值升序的。Skip list讓已排序的數(shù)據(jù)分布在多層鏈表中，以0-1隨機(jī)數(shù)決定一個(gè)數(shù)據(jù)的向上攀升與否，通過(guò)“空間來(lái)?yè)Q取時(shí)間”的一個(gè)算法，在每個(gè)節(jié)點(diǎn)中增加了向前的指針，在插入、刪除、查找時(shí)可以忽略一些不可能涉及到的結(jié)點(diǎn)，從而提高了效率。從概率上保持?jǐn)?shù)據(jù)結(jié)構(gòu)的平衡比顯示的保持?jǐn)?shù)據(jù)結(jié)構(gòu)平衡要簡(jiǎn)單的多。對(duì)于大多數(shù)應(yīng)用，用Skip list要比用樹(shù)算法相對(duì)簡(jiǎn)單。由于Skip list比較簡(jiǎn)單，實(shí)現(xiàn)起來(lái)會(huì)比較容易，雖然和平衡樹(shù)有著相同的時(shí)間復(fù)雜度(O(logn),但是skip li

5、st的常數(shù)項(xiàng)會(huì)相對(duì)小很多。Skip list在空間上也比較節(jié)省。一個(gè)節(jié)點(diǎn)平均只需要1.333個(gè)指針（甚至更少）。圖1-2 Skip list結(jié)構(gòu)圖（以7,14,21,32,37,71,85序列為例）Skip list的性質(zhì)(1) 由很多層結(jié)構(gòu)組成，level是通過(guò)一定的概率隨機(jī)產(chǎn)生的。(2) 每一層都是一個(gè)有序的鏈表，默認(rèn)是升序，也可以根據(jù)創(chuàng)建映射時(shí)所提供的Comparator進(jìn)行排序，具體取決于使用的構(gòu)造方法。(3) 最底層(Level 1)的鏈表包含所有元素。(4) 如果一個(gè)元素出現(xiàn)在Level i 的鏈表中，則它在Level i 之下的鏈表也都會(huì)出現(xiàn)。(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指

6、向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。 ConcurrentSkipListMap具有Skip list的性質(zhì) ，并且適用于大規(guī)模數(shù)據(jù)的并發(fā)訪(fǎng)問(wèn)。多個(gè)線(xiàn)程可以安全地并發(fā)執(zhí)行插入、移除、更新和訪(fǎng)問(wèn)操作。與其他有鎖機(jī)制的數(shù)據(jù)結(jié)構(gòu)在巨大的壓力下相比有優(yōu)勢(shì)。 TreeMap插入數(shù)據(jù)時(shí)平衡樹(shù)采用嚴(yán)格的旋轉(zhuǎn)（比如平衡二叉樹(shù)有左旋右旋）來(lái)保證平衡，因此Skip list比較容易實(shí)現(xiàn)，而且相比平衡樹(shù)有著較高的運(yùn)行效率。本測(cè)試的增加功能，ConcurrentSkipListMap和TreeMap效率相差不大。查找功能在50W數(shù)據(jù)量以后，TreeMap更有效率，因?yàn)镃oncurrentSkipListMap自帶鎖機(jī)制，會(huì)占用一些效率，但對(duì)于多線(xiàn)程并發(fā)的環(huán)境下，ConcurrentSkipListMap的效率會(huì)比Treep要好的。本測(cè)試查找方法使用Map的get方法，循環(huán)、離散獲取。對(duì)于ConcurrentSkipListMap，獲得順序片段，可用subMap()方法，提取50w的子序列只需要1ms，具有巨大優(yōu)勢(shì)。 SkipListMap的范圍查詢(xún)效率比HashMap和TreeMap效率都要高。(3) SkipList 參考資料 1 /questions/sk