一 概覽
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);
}
- tableSizeFor酗钞，其實(shí)就是為了快速找到最近的大于等于cap的2的倍數(shù)，具體原理參考HashMap源碼注解 之 靜態(tài)工具方法hash()来累、tableSizeFor()
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
- 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"));
