Java总结之映射家族--Map概览

张风捷特烈

发布于 2018-10-08 10:25:50

6150

发布于 2018-10-08 10:25:50

所谓映射便是一一对应，map英语中是[地图]的意思，这也很好的反应了映射的概念。即：地图上的某一点都会对应现实的某一点，说是映射可谓恰到好处。Map可以说是键值对的容器，key和value一一对应，也像是根据索引查找单词。索引当然是不能重复的。如果你发现一个字典的索引有两个[apple],你肯定会认为这个字典有问题。或者一个地图上查询两个[合肥],恐怕你也不会相信这张地图是好的。所以Map可作为Set的超集，Java中的Set集合的底层便是根据Map实现的。

Map家族一览

Map接口.png

一、永恒闪耀的明星：HashMap

作为一个多考点的类，说起HashMap总是有种神圣不可侵犯的感觉。相关话题: 哈希碰撞相关问题：什么是哈希碰撞，如何降低哈希碰撞几率，哈希碰撞后的解决方案 HashMap底层实现问题：链表数组+红黑树数组，为什么要使用这样的数据结构由此可以引出链表与数组的比较：效率问题，空间问题,链表的实现由此也引出红黑树的相关问题：什么是红黑树,红黑树的特点，红黑树的翻转，红黑树与AVL树的比较

HashMap.png

来看一下HashMap的数据结构

这里是Map总结篇，所以只是简单的看一下，在HashMap精析中会详细解释 1---打开源码，可以看出内部有一个Node类，而且是单链表 2---打开源码，可以看出内部有一个TreeNode类，而且是红黑树 3---可以看到内部维护一个链表的数组，当哈希冲突时将数据插入链表尾 4---所以HashMap集数组+单链表+红黑树于一身，对数据结构而言，确实很经典。

链表节点类：可见是一个单链表

 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

红黑树节点类

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;  // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;    // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
}

//可以看到内部维护一个数组链表
transient Node<K,V>[] table;

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                   //tab：记录当前链表的数组
                   //n:当前链表的数组的长度
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//hash:传入键的hash值
            //可以看到添加元素并且没有哈希碰撞时，将元素放入数组的下一位
            tab[i] = newNode(hash, key, value, null);
        else {//否则，即哈希冲突了
            Node<K,V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)//如果是树，按树的插入
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//否则，按链表的插入，
            //关于bin:就像数组里放了一个个垃圾桶(链表),来一个哈希冲突的就往里扔一个，
            //所以binCount就是链表的容量
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                    //链表添加节点
                        p.next = newNode(hash, key, value, null);
                        //数量达到树化阀值
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//树化链表
                        break;
                    }
                    //省略...
    }

总结一下

1.HashMap会创建一个1 << 4(即16)的Node<K,V>(链表)数组，
2.当hash冲突时，该元素会插入到与其冲突的链表尾
3.当链表长度为8并且数组长度大于40时，链表转为红黑树  
4.当树元素小于等于6时会解除树化，分割成链表

为什么链表要化为红黑树

单链表查询、修改、移除、尾部添加元素的时间复杂度为O(n)
红黑树查询、修改、移除、添加元素的时间复杂度为O(logn)
在数据量比较大师O(logn)的效率要比O(n)快很多(可根据数学上两种曲线比较)

红黑树这么好，为什么不直接用红黑树?

1.考虑到哈希冲突的数据不会是巨量的
2.在数据量比较少(树化阀值为8)的时候O(n)和O(logn)并无不同
3.红黑树在插入和移除时会进行额外的旋转操作,而且维护的成员变量较多逻辑较复杂，所以低数据量时反而不如单链表

二、链式哈希映射：LinkedHashMap--我有序，我骄傲

LinkedHashMap<K,V>extends HashMap<K,V>,so LinkedHashMap拥有HashMap功力可见Entry是继承自HashMap.Node(单链表)的， Entry<K,V> before, after，说明Entry是一个双链表由此解决了HashMap不能随时保持遍历顺序和插入顺序一致的问题，详细原理会另开一篇

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

LinkedHashMap.png

三、树形映射：TreeMap--我是红黑树

1----基于红黑树，由于红黑树是一种特殊的二分搜索树，所以可保证键的有序性，也可自定义排序规则 2----containsKey、get、put 和 remove 操作时间复杂度结尾O(logn)

可见节点为红黑树

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

TreeMap.png

四、哈希表：Hashtable--就让我成为历史，躲在JDK的漆黑角落。但面试官总爱挖坟...

Hashtable的老爹Dictionary这样介绍自己："NOTE: This class is obsolete"

底层数组+链表实现,无论key还是value都不能为null，
线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低
初始size为11，扩容：newsize = olesize*2+1
计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

Hashtable.png

五、并发哈希映射：ConcurrentHashMap--我为并发而生

不是一两句话能说清的 ConcurrentHashMap锁的粒度，为对每个数组元素(Node)，Hashtable锁的粒度，为对整个数组

ConcurrentHashMap.png

最后总的比较一下

项目	线程安全?	实现	扩容方式	null键值	父类
HashMap	否	数组+单链表+红黑树	oldCap * 2	允许	AbstractMap
Hashtable	是	数组 + 链表	oldCap * 2 + 1	不允许	Dictionary
ConcurrentHashMap	是	数组+单链表+红黑树	oldCap * 2	允许	AbstractMap
LinkedHashMap	否	数组+单链表+红黑树+双链表	oldCap * 2	允许	HashMap
TreeMap	否	红黑树	----	允许	AbstractMap