日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
Java8中HashMap的性能提升

HashMap是一個(gè)高效通用的數(shù)據(jù)結(jié)構(gòu)，它在每一個(gè)Java程序中都隨處可見(jiàn)。先來(lái)介紹些基礎(chǔ)知識(shí)。你可能也知 道，HashMap使用key的hashCode()和equals()方法來(lái)將值劃分到不同的桶里。桶的數(shù)量通常要比map中的記錄的數(shù)量要稍大，這樣 每個(gè)桶包括的值會(huì)比較少（最好是一個(gè)）。當(dāng)通過(guò)key進(jìn)行查找時(shí)，我們可以在常數(shù)時(shí)間內(nèi)迅速定位到某個(gè)桶（使用hashCode()對(duì)桶的數(shù)量進(jìn)行取模） 以及要找的對(duì)象。

這些東西你應(yīng)該都已經(jīng)知道了。你可能還知道哈希碰撞會(huì)對(duì)hashMap的性能帶來(lái)災(zāi)難性的影響。如果多個(gè)hashCode()的值落到同一個(gè)桶內(nèi)的 時(shí)候，這些值是存儲(chǔ)到一個(gè)鏈表中的。最壞的情況下，所有的key都映射到同一個(gè)桶中，這樣hashmap就退化成了一個(gè)鏈表——查找時(shí)間從O(1)到 O(n)。我們先來(lái)測(cè)試下正常情況下hashmap在Java 7和Java 8中的表現(xiàn)。為了能完成控制hashCode()方法的行為，我們定義了如下的一個(gè)Key類：

 
 
    
  
  
  1. class Key implements Comparable { 
    2. 
  
  
  2. private final int value; 
    3. 
  
  
  3. Key(int value) { 
    4. 
  
  
  4. this.value = value; 
    5. 
  
  
  5. } 
    6. 
  
  
  6. @Override
    7. 
  
  
  7. public int compareTo(Key o) { 
    8. 
  
  
  8. return Integer.compare(this.value, o.value); 
    9. 
  
  
  9. } 
    10. 
  
  
  10. @Override
    11. 
  
  
  11. public boolean equals(Object o) { 
    12. 
  
  
  12. if (this == o) return true; 
    13. 
  
  
  13. if (o == null || getClass() != o.getClass()) 
    14. 
  
  
  14. return false; 
    15. 
  
  
  15. Key key = (Key) o; 
    16. 
  
  
  16. return value == key.value; 
    17. 
  
  
  17. } 
    18. 
  
  
  18. @Override
    19. 
  
  
  19. public int hashCode() { 
    20. 
  
  
  20. return value; 
    21. 
  
  
  21. } 
    22. 
  
  
  22. }
    23.

Key類的實(shí)現(xiàn)中規(guī)中矩：它重寫(xiě)了equals()方法并且提供了一個(gè)還算過(guò)得去的hashCode()方法。為了避免過(guò)度的GC，我將不可變的Key對(duì)象緩存了起來(lái)，而不是每次都重新開(kāi)始創(chuàng)建一遍：

 
 
    
  
  
  1. class Key implements Comparable { 
    2. 
  
  
  2. public class Keys { 
    3. 
  
  
  3. public static final int MAX_KEY = 10_000_000; 
    4. 
  
  
  4. private static final Key[] KEYS_CACHE = new Key[MAX_KEY]; 
    5. 
  
  
  5. static { 
    6. 
  
  
  6. for (int i = 0; i < MAX_KEY; ++i) { 
    7. 
  
  
  7. KEYS_CACHE[i] = new Key(i); 
    8. 
  
  
  8. } 
    9. 
  
  
  9. } 
    10. 
  
  
  10. public static Key of(int value) { 
    11. 
  
  
  11. return KEYS_CACHE[value]; 
    12. 
  
  
  12. } 
    13. 
  
  
  13. }
    14.

現(xiàn)在我們可以開(kāi)始進(jìn)行測(cè)試了。我們的基準(zhǔn)測(cè)試使用連續(xù)的Key值來(lái)創(chuàng)建了不同的大小的HashMap（10的乘方，從1到1百萬(wàn)）。在測(cè)試中我們還會(huì)使用key來(lái)進(jìn)行查找，并測(cè)量不同大小的HashMap所花費(fèi)的時(shí)間：

 
 
    
  
  
  1. import com.google.caliper.Param; 
    2. 
  
  
  2. import com.google.caliper.Runner; 
    3. 
  
  
  3. import com.google.caliper.SimpleBenchmark; 
    4. 
  
  
  4. public class MapBenchmark extends SimpleBenchmark { 
    5. 
  
  
  5. private HashMap map; 
    6. 
  
  
  6. @Param
    7. 
  
  
  7. private int mapSize; 
    8. 
  
  
  8. @Override
    9. 
  
  
  9. protected void setUp() throws Exception { 
    10. 
  
  
  10. map = new HashMap<>(mapSize); 
    11. 
  
  
  11. for (int i = 0; i < mapSize; ++i) { 
    12. 
  
  
  12. map.put(Keys.of(i), i); 
    13. 
  
  
  13. } 
    14. 
  
  
  14. } 
    15. 
  
  
  15. public void timeMapGet(int reps) { 
    16. 
  
  
  16. for (int i = 0; i < reps; i++) { 
    17. 
  
  
  17. map.get(Keys.of(i % mapSize)); 
    18. 
  
  
  18. } 
    19. 
  
  
  19. } 
    20. 
  
  
  20. }
    21.

有意思的是這個(gè)簡(jiǎn)單的HashMap.get()里面，Java 8比Java 7要快20%。整體的性能也相當(dāng)不錯(cuò)：盡管HashMap里有一百萬(wàn)條記錄，單個(gè)查詢也只花了不到10納秒，也就是大概我機(jī)器上的大概20個(gè)CPU周期。 相當(dāng)令人震撼！不過(guò)這并不是我們想要測(cè)量的目標(biāo)。

假設(shè)有一個(gè)很差勁的key，他總是返回同一個(gè)值。這是最糟糕的場(chǎng)景了，這種情況完全就不應(yīng)該使用HashMap:

 
 
    
  
  
  1. class Key implements Comparable { 
    2. 
  
  
  2. //... 
    3. 
  
  
  3. @Override
    4. 
  
  
  4. public int hashCode() { 
    5. 
  
  
  5. return 0; 
    6. 
  
  
  6. } 
    7. 
  
  
  7. }
    8.

Java 7的結(jié)果是預(yù)料中的。隨著HashMap的大小的增長(zhǎng)，get()方法的開(kāi)銷(xiāo)也越來(lái)越大。由于所有的記錄都在同一個(gè)桶里的超長(zhǎng)鏈表內(nèi)，平均查詢一條記錄就需要遍歷一半的列表。因此從圖上可以看到，它的時(shí)間復(fù)雜度是O(n)。

不過(guò)Java 8的表現(xiàn)要好許多！它是一個(gè)log的曲線，因此它的性能要好上好幾個(gè)數(shù)量級(jí)。盡管有嚴(yán)重的哈希碰撞，已是最壞的情況了，但這個(gè)同樣的基準(zhǔn)測(cè)試在JDK8中的時(shí)間復(fù)雜度是O(logn)。單獨(dú)來(lái)看JDK 8的曲線的話會(huì)更清楚，這是一個(gè)對(duì)數(shù)線性分布：

為什么會(huì)有這么大的性能提升，盡管這里用的是大O符號(hào)（大O描述的是漸近上界）？其實(shí)這個(gè)優(yōu)化在JEP-180中已經(jīng)提到了。如果某個(gè)桶中的記錄過(guò) 大的話（當(dāng)前是TREEIFY_THRESHOLD = 8），HashMap會(huì)動(dòng)態(tài)的使用一個(gè)專門(mén)的treemap實(shí)現(xiàn)來(lái)替換掉它。這樣做的結(jié)果會(huì)更好，是O(logn)，而不是糟糕的O(n)。它是如何工作 的？前面產(chǎn)生沖突的那些KEY對(duì)應(yīng)的記錄只是簡(jiǎn)單的追加到一個(gè)鏈表后面，這些記錄只能通過(guò)遍歷來(lái)進(jìn)行查找。但是超過(guò)這個(gè)閾值后HashMap開(kāi)始將列表升 級(jí)成一個(gè)二叉樹(shù)，使用哈希值作為樹(shù)的分支變量，如果兩個(gè)哈希值不等，但指向同一個(gè)桶的話，較大的那個(gè)會(huì)插入到右子樹(shù)里。如果哈希值相等，HashMap希 望key值最好是實(shí)現(xiàn)了Comparable接口的，這樣它可以按照順序來(lái)進(jìn)行插入。這對(duì)HashMap的key來(lái)說(shuō)并不是必須的，不過(guò)如果實(shí)現(xiàn)了當(dāng)然最 好。如果沒(méi)有實(shí)現(xiàn)這個(gè)接口，在出現(xiàn)嚴(yán)重的哈希碰撞的時(shí)候，你就并別指望能獲得性能提升了。

這個(gè)性能提升有什么用處？比方說(shuō)惡意的程序，如果它知道我們用的是哈希算法，它可能會(huì)發(fā)送大量的請(qǐng)求，導(dǎo)致產(chǎn)生嚴(yán)重的哈希碰撞。然后不停的訪問(wèn)這些 key就能顯著的影響服務(wù)器的性能，這樣就形成了一次拒絕服務(wù)攻擊（DoS）。JDK 8中從O(n)到O(logn)的飛躍，可以有效地防止類似的攻擊，同時(shí)也讓HashMap性能的可預(yù)測(cè)性稍微增強(qiáng)了一些。我希望這個(gè)提升能最終說(shuō)服你的 老大同意升級(jí)到JDK 8來(lái)。

測(cè)試使用的環(huán)境是：Intel Core i7-3635QM @ 2.4 GHz，8GB內(nèi)存，SSD硬盤(pán)，使用默認(rèn)的JVM參數(shù)，運(yùn)行在64位的Windows 8.1系統(tǒng) 上。

原文出處： Tomasz Nurkiewicz   譯文出處： deepinmind


文章名稱：Java8中HashMap的性能提升
瀏覽路徑：http://www.5511xx.com/article/dhhgcdh.html