一 概览
image.png
Map的继承结构如上图所示，其中最常用的为HashMap，LinkedHashMap和TreeMap，下图为其对比
image.png
在Python里，键值对是用Dictionary来表示的，事实上Java旧版本也使用了Dictionary的称呼，只是后来被废弃了，开始使用Map
Dictionary is an abstract class, superclass of Hashtable. You should not use Dictionary as it is obsolete.
二 HashMap篇
-
image.png
HashMap里有着许多的内部类，其中左下为菱形符号表示static class，左上一个大头针符号的是final class，没有标记的全色球C就是普通的class，花色球的就是abstract class ，这个规则也适用于图里的红色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，其实就是为了快速找到最近的大于等于cap的2的倍数，具体原理参考HashMap源码注解 之 静态工具方法hash()、tableSizeFor()
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1; //无符号右移一位
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
注意此时得到的不是最终的threshold，之后会通过resize重新计算。
- indexFor
//用于将hash值转化为数组索引值
static int indexFor(int h, int length) {
return h & (length-1);
}
等价于return h % length;采用二进制位操作&，相对于%，能够提高运算效率，这就是为什么要用 tableSizeFor 求大于cap的二次幂数。
- hash，通过无符号移位符实现高低位异或从而实现 hash 功能
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
事实上HashMap、HashTable以及ConcurrentHashMap分别在Jdk 1.7 和 Jdk 1.8中的实现都有细微差别，参考全网把Map中的hash()分析的最透彻的文章，别无二家。，这个差别也导致了 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)) + " ");
}
因为Set就是使用了Map来实现，所以它们的hash功能是一样的，上述例子通过增加(1 << 16)可以体会到HashSet的不保证有序性特点，如果不加上(1 << 16)，则上述例子HashSet和LinkedHashSet都是按照插入顺序有序输出
- treeifyBin
//当冲突的节点数超过阈值，则执行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，否则，将链表变成红黑树
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));
}
上面的代码看似可行，但是其实不可取
The docs literally say that the mapping function should not modify this map during computation, so this answer is clearly wrong.
最佳实践应该是提供一个helper性质的函数，否则一般应该使用putIfAbsent函数
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
- 补充computeIfPresent和compute，总的来说，ifAbsent或者ifPresent相当于compute的filter。
Map<String, List<Integer>> positionsMap = new HashMap<>();
positionsMap.computeIfAbsent(i, key -> new ArrayList<>(1)).add(j);
相当于
positionsMap.compute(i, (key, value) -> value == null ? new ArrayList<>(1) : value).add(j);//更通用
而
positionsMap.computeIfPresent(i, (key, oldValue) -> generateNewValue(key,oldValue));
相当于
positionsMap.compute(i, (key, oldValue) -> oldValue != null ? oldValue : generateNewValue(key,oldValue));//更主要是用于修改旧的value
- merge， 如果给定的key之前没设置value 或者value为null, 则将给定的value关联到这个key上.否则，通过给定的remaping函数计算的结果来替换其value。如果remapping函数的计算结果为null，将解除此结果。
- replace(k,v)和replace(k,v,v)，就是简单版的computeIfPresent。
- 多线程操作
从上面可看出：在扩容resize（）过程中，在将旧数组上的数据 转移到 新数组上时，转移数据操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况，此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态 - 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"));
网友评论