Map集合源码解析与对比

HashMap数据结构

  • HashMap是基于hashing的原理； value>插到table[i]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table[i]上形成一个链表
  • 扩容原理：HashMap的扩容因子或负载因子为0.75，初容量1<<4=16，最大容量1<<30= 2^30 ；当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中，也就是作rehashing，因为它调用hash方法找到新的bucket位置；
  • 存储原理：put(key, value)方法存储时，会先对key调用hashCode()方法，返回的hashCode，然后根据table的长度进行取模，用于找到bucket位置来储存Entry对；

  • 查找原理：拿key的hashCode来找到bucket位置，然后将会遍历链表,调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象;


    JDK1.7的HashMap数据结构图

HashMap指针碰撞问题

  • 因为有equals()和hashCode()两个方法，所以两个对象就算hashcode相同，但是它们可能并不相等；
  • 出现Hash碰撞后，两个值对象会存在同一个bucket中，并使用链表存储Map.Entry对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中；

HashMap线程安全问题

  • 当多线程的情况下，可能产生条件竞争(race condition)；
  • 当重新调整HashMap大小的时候，存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了；

Key不可变对象的好处

  • hashCode()方法在存取时都会用到，但是equals()方法仅仅在获取值对象的时候才出现，所以使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率
  • 因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了，不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，例如Interger其他的wrapper类也有这个特点。
  • 不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。
  • 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话，那么碰撞的几率就会小些，这样就能提高HashMap的性能。
  • 使用自定义对象作为key，要注意重写equals()和hashCode()方法，要保证插入到map中后就不会在改变，否则会出现get时找不到值；

Collections对HashMap实现同步

  • Collections.synchronizedMap可以实现对HashMap线程同步，返回的是一个Collections.SynchronizedMap类，直接将读写操作加了synchronized

HashMap 和 Hashtable

  • HashMap初始容量16，Hashtable 11；
  • HashMap扩容是oldCap << 1，扩容一倍，Hashtable(oldCapacity << 1) + 1，扩容大小不一致是因为index计算方式不同，并且一定是要对奇数取膜；
  • HashMap的index计算是e.hash & (newCap - 1)，Hashtable(e.hash & 0x7FFFFFFF) % newCapacity，实际e.hash & (newCap - 1) == e.hash % newCap
  • HashMap可以接受null键值和值，而Hashtable则不能；
  • HashMap是非synchronized，Hashtable是线程安全的，所以在单线程情况下，HashMap效率更高；
  • HashMap的iterator在多线程下操作可能会抛出ConcurrentModificationException异常，因为Collection的Iterator使用了fail-fast机制；
    http://www.importnew.com/24822.html

HashMap 和 LinkedHashMap

  • LinkedHashMap 继承自HashMap，内部又维护了一条双向链表，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序；
  • LinkedHashMap 遍历时遍历的记录顺序的双向链表，所以先得到的记录肯定是先插入的；
  • LinkedHashMap 也可以在构造时带参数，按照应用次数排序；
  • LinkedHashMap 数据量大时在查找的时候会比HashMap慢，因为HashMap会先找到bucket位，然后遍历链表，hash均匀时时间复杂度可能是O(1)

HashMap 和 TreeMap

  • TreeMap 基于NavigableMap实现的红黑树
  • TreeMap 实现SortMap接口，能够把它保存的记录根据键排序；
  • TreeMap 默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的

HashMap 和 HashSet

  • HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key

HashMap 和 SparseArray

  • SparseArray相比ArrayList查找时采用binary search查找key；
  • 数据量特别大时性能不如HashMap,数据量超过几百时，性能差距不到50%；
  • SparseArray在remove时，只是做了逻辑删除，key还是可以重用的；
SparseArray.java
private void gc() {
        // Log.e("SparseArray", "gc start with " + mSize);
        int n = mSize;
        int o = 0;
        int[] keys = mKeys;
        Object[] values = mValues;

        for (int i = 0; i < n; i++) {
            Object val = values[i];

            if (val != DELETED) {
                if (i != o) {
                    keys[o] = keys[i];
                    values[o] = val;
                    values[i] = null;
                }
                o++;
            }
        }
        mGarbage = false;
        mSize = o;
        // Log.e("SparseArray", "gc end with " + mSize);
}

HashMap和ArrayMap

  • 主要是节省空间，因为内部用了4个数组维护，并且空间进行了复用，扩容时是通过index+index>>1，并不会扩容一倍
  • mHashes的存在，主要是用来找到mArray中的key的hash值的index，因为mArray中是将key和value一起存入的，所以将index<<1+1就找到了value在mArray中的位置；
  • 查找时使用二分查找，尽可能提高效率，在数据量大的情况下，如不HashMap
  • ArrayMap原理具体可参考：https://www.cnblogs.com/huanyou/p/5985303.html

ConcurrentHashMap

  • JDK1.7 的整个 ConcurrentHashMap 由一个个 Segment 组成，Segment 代表”部分“或”一段“的意思，所以很多地方都会将其描述为分段锁。
    简单理解就是，ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全
  • JDK1.8 的ConcurrentHashMap 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率
  • ConcurrentHashMap基于ReentrantLock实现分段锁，所以ConcurrentHashMap在并发条件下性能相比Hashtable更好；
JDK1.7 的ConcurrentHashMap数据结构图

为什么Hashtable、ConcurrentHashmap不支持key或者value为null

ConcurrentHashmap、Hashtable不支持key或者value为null，而HashMap是支持的。为什么会有这个区别？在设计上的目的是什么？

在网上找到了这样的解答:
ConcurrentHashmap和Hashtable都是支持并发的，这样会有一个问题，当你通过get(k)获取对应的value时，如果获取到的是null时，你无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射。HashMap是非并发的，可以通过contains(key)来做这个判断。而支持并发的Map在调用m.contains（key）和m.get(key),m可能已经不同了。
另外HashTable在计算hash值时没有进行非空校验，为Null会报异常

JDK1.8新特性

  • hash算法优化，通过hashCode()的高16位异或低16位实现的，1.7 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
  • resize优化，数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8(默认值)的列表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。
  • 通过增加tail指针，既避免了死循环问题（让数据直接插入到队尾），又避免了尾部遍历，但仍是非线程安全的，多线程时可能会造成数据丢失问题
  • ConcurrentHashmap 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据

计算index一定是对奇数取膜

length为2的整数次幂的话，则一定为偶数，那么 length-1 一定为奇数，奇数的二进制的最后一位是1，这样便保证了 h&(length-1) 的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀，而如果length为奇数的话，很明显 length-1 为偶数，它的最后一位是0，这样 h&(length-1) 的最后一位肯定为0，即只能为偶数，这样导致了任何hash值都只会被散列到数组的偶数下标位置上，浪费了一半的空间，因此length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列

JDK1.8 HashMap 部分关键源码

//计算Hash
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//put操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K, V>[] tab; //table数组
    Node<K, V> p;//数组中链表的尾指针
    int n, i;
    //如果table为空，初始化table
    if ((tab = table) == null || (n = tab.length) == 0) {
        n = (tab = resize()).length;
    }
    //如果table中计算的hash没有冲突，直接放入数组最后一个
    if ((p = tab[i = (n - 1) & hash]) == null) {
        tab[i] = newNode(hash, key, value, null);
    }
    //出现hash冲突；一种情况是key相同替换，还可能是hash冲突，但是key不同
    else {
        Node<K, V> e;//待插入node的临时变量
        K k;
        //如果Hash值相同，比较key是否相同，如果相同，直接将尾指针赋给临时变量，用于后面的替换value
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
            e = p;
        }
        //否则是放入新的key、value
        //如果node是TreeNode，则是红黑树实现
        else if (p instanceof TreeNode) {
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        } else {
            //遍历链表
            for (int binCount = 0; ; ++binCount) {
                //找到根结点
                if ((e = p.next) == null) {
                    //添加到链表中
                    p.next = newNode(hash, key, value, null);
                    //TREEIFY_THRESHOLD默认为8，节点超过8，转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) {// -1 for 1st
                        treeifyBin(tab, hash);
                    }
                    break;
                }
                //如果是key相同，直接跳出，替换尾指针
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                    break;
                }
                p = e;
            }
        }
        //临时变量赋值value，并调插入，如果key相同返回旧的值，key不同oldValue就为null
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) {
                e.value = value;
            }
            //LinkedHashMap使用的
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //modCount是用来操作计数的，在foreach或者其他操作中出现modCount不一致时用来抛出ConcurrentModificationException，fail-fast机制
    ++modCount;
    if (++size > threshold) {
        resize();
    }
    //LinkedHashMap使用的
    afterNodeInsertion(evict);
    return null;
}

//查找
final HashMap.Node<K, V> getNode(int hash, Object key) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> first, e;
    int n;
    K k;
    //table不为空
    //计算index，index = (n - 1) & hash，找到bucket位
    //first 链表的第一个节点
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        //先检查第一个节点
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k)))) {
            return first;
        }
        //遍历链表
        if ((e = first.next) != null) {
            if (first instanceof HashMap.TreeNode) {
                return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
            }
            do {
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                    return e;
                }
            } while ((e = e.next) != null);
        }
    }
    return null;
}

JDK1.8 SynchronizedMap部分源码

private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
        private final Map<K,V> m;     // Backing Map
        final Object  mutex;        // Object on which to synchronize
        SynchronizedMap(Map<K,V> m) {
            this.m = Objects.requireNonNull(m);
            mutex = this;
        }
        SynchronizedMap(Map<K,V> m, Object mutex) {
            this.m = m;
            this.mutex = mutex;
        }
        public V get(Object key) {
            synchronized (mutex) {return m.get(key);}
        }
        public V put(K key, V value) {
            synchronized (mutex) {return m.put(key, value);}
        }
        public V remove(Object key) {
            synchronized (mutex) {return m.remove(key);}
        }
        ... ...
}

参考

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,711评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,079评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,194评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,089评论 1赞 286
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,197评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,306评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,338评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,119评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,541评论 1赞 306
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,846评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,014评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,694评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,322评论 3赞 318
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,026评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,257评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,863评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,895评论 2赞 351