Map完全解析

2019-02-20 本文已影响0人 ayagg

一概览

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

map中的compute方法

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"));

Map完全解析

一概览

二 HashMap篇

HashTable

附录

猜你喜欢

热点阅读

Map完全解析

一 概览

二 HashMap篇

HashTable

附录

猜你喜欢

热点阅读

一概览