Map完全解析

一 概覽

image.png

Map的繼承結(jié)構(gòu)如上圖所示列粪,其中最常用的為HashMap榨馁,LinkedHashMap和TreeMap换棚,下圖為其對(duì)比


image.png

在Python里浓领,鍵值對(duì)是用Dictionary來(lái)表示的,事實(shí)上Java舊版本也使用了Dictionary的稱呼奋蔚,只是后來(lái)被廢棄了她混,開(kāi)始使用Map

Dictionary is an abstract class, superclass of Hashtable. You should not use Dictionary as it is obsolete.

二 HashMap篇

  • image.png

    HashMap里有著許多的內(nèi)部類烈钞,其中左下為菱形符號(hào)表示static class,左上一個(gè)大頭針?lè)?hào)的是final class坤按,沒(méi)有標(biāo)記的全色球C就是普通的class毯欣,花色球的就是abstract class ,這個(gè)規(guī)則也適用于圖里的紅色method臭脓。

  • 初始化
  public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;  //無(wú)符號(hào)右移一位
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

注意此時(shí)得到的不是最終的threshold砚作,之后會(huì)通過(guò)resize重新計(jì)算。

  • indexFor
//用于將hash值轉(zhuǎn)化為數(shù)組索引值
static int indexFor(int h, int length) {
    return h & (length-1);
}

等價(jià)于return h % length;采用二進(jìn)制位操作&,相對(duì)于%,能夠提高運(yùn)算效率累提,這就是為什么要用 tableSizeFor 求大于cap的二次冪數(shù)。

  • hash压昼,通過(guò)無(wú)符號(hào)移位符實(shí)現(xiàn)高低位異或從而實(shí)現(xiàn) hash 功能
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

事實(shí)上HashMap、HashTable以及ConcurrentHashMap分別在Jdk 1.7 和 Jdk 1.8中的實(shí)現(xiàn)都有細(xì)微差別瘤运,參考全網(wǎng)把Map中的hash()分析的最透徹的文章窍霞,別無(wú)二家。拯坟,這個(gè)差別也導(dǎo)致了 Java遍歷HashSet為什么輸出是有序的但金? - RednaxelaFX的回答 - 知乎

        Set<Integer> intset = new HashSet<>();
       // Set<Integer> intset = new LinkedHashSet<>();
        for (int i = 0; i < 100; i++) {
           // Integer a = i;
            Integer a = i + (1 << 16);
            intset.add(a);
        }
        Iterator<Integer> iterator = intset.iterator();
        while (iterator.hasNext()) {
            //System.out.print(iterator.next()+ " ");
            System.out.print((iterator.next() - (1 << 16)) + " ");
        }

因?yàn)镾et就是使用了Map來(lái)實(shí)現(xiàn),所以它們的hash功能是一樣的郁季,上述例子通過(guò)增加(1 << 16)可以體會(huì)到HashSet的不保證有序性特點(diǎn)冷溃,如果不加上(1 << 16),則上述例子HashSet和LinkedHashSet都是按照插入順序有序輸出

  • treeifyBin
//當(dāng)沖突的節(jié)點(diǎn)數(shù)超過(guò)閾值梦裂,則執(zhí)行treeifyBin
   if (binCount >= TREEIFY_THRESHOLD - 1)
      treeifyBin(tab, hash);
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //如果map容量小于MIN_TREEIFY_CAPACITY似枕,則resize,否則年柠,將鏈表變成紅黑樹(shù)
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
  • computeIfAbsent
   private static Map<Integer,Long> memo = new HashMap<>();
   static {
      memo.put(0,0L); //fibonacci(0)
      memo.put(1,1L); //fibonacci(1)
   }

  public static long fibonacci(int x) {
     return memo.computeIfAbsent(x, n -> fibonacci(n-2) + fibonacci(n-1));
  }

上面的代碼看似可行凿歼,但是其實(shí)不可取

The docs literally say that the mapping function should not modify this map during computation, so this answer is clearly wrong.

最佳實(shí)踐應(yīng)該是提供一個(gè)helper性質(zhì)的函數(shù),否則一般應(yīng)該使用putIfAbsent函數(shù)

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class Test {
    public static void main(String[] s) {
        Map<String, Boolean> whoLetDogsOut = new ConcurrentHashMap<>();
        whoLetDogsOut.computeIfAbsent("snoop", k -> f(k));
        whoLetDogsOut.computeIfAbsent("snoop", k -> f(k));
    }
    static boolean f(String s) {
        System.out.println("creating a value for \""+s+'"');
        return s.isEmpty();
    }
}

或者

// Stores regional movie ratings
  Map<String, Map<Integer, Set<String>>> regionalMovieRatings = new TreeMap<>();

  // This will throw NullPointerException!
  regionalMovieRatings.get("New York").get(5).add("Boyhood");

  // This will work
  regionalMovieRatings
    .computeIfAbsent("New York", region -> new TreeMap<>())
    .computeIfAbsent(5, rating -> new TreeSet<>())
    .add("Boyhood");

how-do-i-use-the-new-computeifabsent-function

  • 補(bǔ)充computeIfPresent和compute冗恨,總的來(lái)說(shuō)答憔,ifAbsent或者ifPresent相當(dāng)于compute的filter。
 Map<String, List<Integer>> positionsMap = new HashMap<>();
 positionsMap.computeIfAbsent(i, key -> new ArrayList<>(1)).add(j);
相當(dāng)于
 positionsMap.compute(i, (key, value) -> value == null ? new ArrayList<>(1) : value).add(j);//更通用
而
 positionsMap.computeIfPresent(i, (key, oldValue) -> generateNewValue(key,oldValue));
相當(dāng)于
 positionsMap.compute(i, (key, oldValue) -> oldValue != null ? oldValue : generateNewValue(key,oldValue));//更主要是用于修改舊的value

map中的compute方法

  • merge掀抹, 如果給定的key之前沒(méi)設(shè)置value 或者value為null, 則將給定的value關(guān)聯(lián)到這個(gè)key上.否則虐拓,通過(guò)給定的remaping函數(shù)計(jì)算的結(jié)果來(lái)替換其value。如果remapping函數(shù)的計(jì)算結(jié)果為null傲武,將解除此結(jié)果蓉驹。
  • replace(k,v)和replace(k,v,v)城榛,就是簡(jiǎn)單版的computeIfPresent。
  • 多線程操作
    從上面可看出:在擴(kuò)容resize()過(guò)程中戒幔,在將舊數(shù)組上的數(shù)據(jù) 轉(zhuǎn)移到 新數(shù)組上時(shí)吠谢,轉(zhuǎn)移數(shù)據(jù)操作 = 按舊鏈表的正序遍歷鏈表土童、在新鏈表的頭部依次插入诗茎,即在轉(zhuǎn)移數(shù)據(jù)、擴(kuò)容后献汗,容易出現(xiàn)鏈表逆序的情況敢订,此時(shí)若(多線程)并發(fā)執(zhí)行 put()操作,一旦出現(xiàn)擴(kuò)容情況罢吃,則 容易出現(xiàn) 環(huán)形鏈表楚午,從而在獲取數(shù)據(jù)、遍歷鏈表時(shí) 形成死循環(huán)(Infinite Loop)尿招,即 死鎖的狀態(tài)
  • HashMap幾種初始化方式
public static Map<String, String> articleMapOne;
static {
    articleMapOne = new HashMap<>();
    articleMapOne.put("ar01", "Intro to Map");
    articleMapOne.put("ar02", "Some article");
}
Map<String, String> doubleBraceMap  = new HashMap<String, String>() {{
    put("key1", "value1");
    put("key2", "value2");
}};
Map<String,String> singletonMap = Collections.singletonMap("username1", "password1");
Map<String, String> emptyMap = Collections.emptyMap();
Map<String, String> map = Stream.of(new String[][] {
  { "Hello", "World" }, 
  { "John", "Doe" }, 
}).collect(Collectors.toMap(data -> data[0], data -> data[1]));

Map<String, Integer> map = Stream.of(new Object[][] { 
    { "data1", 1 }, 
    { "data2", 2 }, 
}).collect(Collectors.toMap(data -> (String) data[0], data -> (Integer) data[1]));
Map<String, String> map = Stream.of(new String[][] { 
    { "Hello", "World" }, 
    { "John", "Doe" },
}).collect(Collectors.collectingAndThen(
    Collectors.toMap(data -> data[0], data -> data[1]), 
    Collections::<String, String> unmodifiableMap));
//Java9
Map<String, String> emptyMap = Map.of();
Map<String, String> singletonMap = Map.of("key1", "value");
Map<String, String> map = Map.of("key1","value1", "key2", "value2");
Map<String, String> articles 
  = ImmutableMap.of("Title", "My New Article", "Title2", "Second Article");
Map<String, String> articles 
  = Maps.newHashMap(ImmutableMap.of("Title", "My New Article", "Title2", "Second Article"));

HashTable

附錄

  1. Java8 HashMap詳解
  2. Java8 集合源碼解析 - HashMap
  3. HashMap在不同JDK版本中的區(qū)別
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末矾柜,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子就谜,更是在濱河造成了極大的恐慌怪蔑,老刑警劉巖,帶你破解...
    沈念sama閱讀 210,914評(píng)論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件丧荐,死亡現(xiàn)場(chǎng)離奇詭異缆瓣,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)虹统,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,935評(píng)論 2 383
  • 文/潘曉璐 我一進(jìn)店門(mén)弓坞,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人车荔,你說(shuō)我怎么就攤上這事渡冻。” “怎么了忧便?”我有些...
    開(kāi)封第一講書(shū)人閱讀 156,531評(píng)論 0 345
  • 文/不壞的土叔 我叫張陵族吻,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我茬腿,道長(zhǎng)呼奢,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,309評(píng)論 1 282
  • 正文 為了忘掉前任切平,我火速辦了婚禮握础,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘悴品。我一直安慰自己禀综,他們只是感情好简烘,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,381評(píng)論 5 384
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著定枷,像睡著了一般孤澎。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上欠窒,一...
    開(kāi)封第一講書(shū)人閱讀 49,730評(píng)論 1 289
  • 那天覆旭,我揣著相機(jī)與錄音,去河邊找鬼岖妄。 笑死型将,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的荐虐。 我是一名探鬼主播七兜,決...
    沈念sama閱讀 38,882評(píng)論 3 404
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼福扬!你這毒婦竟也來(lái)了腕铸?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 37,643評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤铛碑,失蹤者是張志新(化名)和其女友劉穎狠裹,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體亚茬,經(jīng)...
    沈念sama閱讀 44,095評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡酪耳,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,448評(píng)論 2 325
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了刹缝。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片碗暗。...
    茶點(diǎn)故事閱讀 38,566評(píng)論 1 339
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖梢夯,靈堂內(nèi)的尸體忽然破棺而出言疗,到底是詐尸還是另有隱情,我是刑警寧澤颂砸,帶...
    沈念sama閱讀 34,253評(píng)論 4 328
  • 正文 年R本政府宣布噪奄,位于F島的核電站,受9級(jí)特大地震影響人乓,放射性物質(zhì)發(fā)生泄漏勤篮。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,829評(píng)論 3 312
  • 文/蒙蒙 一色罚、第九天 我趴在偏房一處隱蔽的房頂上張望碰缔。 院中可真熱鬧,春花似錦戳护、人聲如沸金抡。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,715評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)梗肝。三九已至榛瓮,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間巫击,已是汗流浹背禀晓。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,945評(píng)論 1 264
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留喘鸟,地道東北人匆绣。 一個(gè)月前我還...
    沈念sama閱讀 46,248評(píng)論 2 360
  • 正文 我出身青樓驻右,卻偏偏與公主長(zhǎng)得像什黑,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子堪夭,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,440評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容

  • 1.HashMap是一個(gè)數(shù)組+鏈表/紅黑樹(shù)的結(jié)構(gòu)愕把,數(shù)組的下標(biāo)在HashMap中稱為Bucket值,每個(gè)數(shù)組項(xiàng)對(duì)應(yīng)的...
    誰(shuí)在烽煙彼岸閱讀 1,018評(píng)論 2 2
  • 一、基本數(shù)據(jù)類型 注釋 單行注釋:// 區(qū)域注釋:/* */ 文檔注釋:/** */ 數(shù)值 對(duì)于byte類型而言...
    龍貓小爺閱讀 4,257評(píng)論 0 16
  • 實(shí)際上爬迟,HashSet 和 HashMap 之間有很多相似之處橘蜜,對(duì)于 HashSet 而言,系統(tǒng)采用 Hash 算...
    曹振華閱讀 2,510評(píng)論 1 37
  • Java8張圖 11付呕、字符串不變性 12计福、equals()方法、hashCode()方法的區(qū)別 13徽职、...
    Miley_MOJIE閱讀 3,696評(píng)論 0 11
  • 以前象颖,只是聽(tīng)說(shuō):25歲是人生一道坎,25歲前后人會(huì)發(fā)生很多變化姆钉。說(shuō)實(shí)話说订,這樣的話我大部分還是不信的,我一直堅(jiān)持認(rèn)為...
    TELEDESIGN閱讀 408評(píng)論 0 0