Map集合源码解析与对比

2019-04-22  本文已影响0人  魏树鑫

HashMap数据结构

HashMap指针碰撞问题

HashMap线程安全问题

Key不可变对象的好处

Collections对HashMap实现同步

HashMap 和 Hashtable

HashMap 和 LinkedHashMap

HashMap 和 TreeMap

HashMap 和 HashSet

HashMap 和 SparseArray

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

ConcurrentHashMap

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新特性

计算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);}
        }
        ... ...
}

参考

上一篇下一篇

猜你喜欢

热点阅读