HashMap和ConcurrentHashMap
标签:Java基础

HashMap和ConcurrentHashMap

看了那么多的HashMap和ConcurrentHashMap的文章,是时候自己总结一下的了:

先看类的声明:

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable 

可见HashMap是实现的AbstractMap,而AbstractMap又实现的是Map,来看一下类图结构:

可见还是Java常用的模板方法,在Map提供接口,AbstractMap提供基础的实现,而下面的子类在对上面的进行相应的扩展。

Java8的中的HashMap的结构如图:

可见Java8的HashMap采用的是 数组+链表+红黑树的方式。

HashMap源码分析

容量分析

    /**
     * 默认容量为16,且必须是2的n次方
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * 最大容量,如果使用比它还大的参数的去构造HashMap,将默认使用它,必须是2的n次方
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 在构造函数中未指定时使用的加载因子。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     *
     * 将链表转换为红黑树的阈值,必须比2大,至少为8
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     *
     * 红黑树转换为链表的阈值
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     *
     * 桶中bin最小hash容量,如果大于这个值会进行resize扩容操作,此值至少是TREEIFY_THRESHOLD的4倍
     */
    static final int MIN_TREEIFY_CAPACITY = 64;


HashMap的扩容机制是:当HashMap中的元素个数(size)超过临界值(threshold)时就会自动扩容。在HashMap中,threshold = loadFactor * capacity

如果我们在使用HashMap的时候,没有指定容量,那么在使用过程中将会不断的扩容,非常影响性能。

当然我们设置的值也会影响HashMap的性能。当我们知道HashMap中要存放多少个值的时候,我们应当设置多大的值合适呢?

    /**
     * Returns a power of two size for the given target capacity.
     * 返回给定目标容量的大于输入参数且最近的2的整数次幂的数
     */
    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;
    }

上面这个函数是HashMap确定容量的函数,但注意jdk1.8中,在调用HashMap的构造函数定义HashMap的时候,就会进行容量的设定。而在Jdk 1.7中,要等到第一次put操作时才进行这一操作。

上面这个是简单的计算过程,竖着看,5->7->8,19->31->32 .... 最后再做一下极限值的判断,至于里面的 |=>>> 其实是对一个二进制数依次向右移位,然后与原值取或。 即:

1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111

通过几次无符号右移按位或运算,我们把1100 1100 1100转换成了1111 1111 1111 ,再把1111 1111 1111加1,就得到了1 0000 0000 0000,这就是大于1100 1100 1100的第一个2的幂。

但是还有一种特殊情况套用以上公式不行,这些数字就是2的幂自身。如果数字4 套用公式的话。得到的会是 8 :

Step 1: 
0100 >>>1 = 0010
0100 | 0010 = 0110
0110 >>>1 = 0011
0110 | 0011 = 0111
Step 2:
0111 + 0001 = 1000

为了解决这个问题,JDK的工程师把所有用户传进来的数在进行计算之前先-1,就是源码中的第一行:

int n = cap - 1;

那容量应该设置多大呢?float ft = ((float)s / loadFactor) + 1.0F;

在Java8 的Has和Map的源码的这两个函数都是采用上面的这个计算公式来确定容量的

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) 
    private void readObject(java.io.ObjectInputStream s)

put分析

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    //    onlyIfAbsent为true的时候,表示只有当key不存在的时候,才会进行put操作
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
//        第一次put操作的的时候才会进行resize()操作
//        第一次 resize 和后续的扩容有些不一样,因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
//        找到具体的数组下标,如果此位置没有值,那么直接初始化一下 Node 并放置在这个位置就可以了
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {// 数组该位置有数据
            Node<K,V> e; K k;
//            首先,判断该位置的第一个数据和我们要插入的数据,key 是不是"相等",如果是,取出这个节点
            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 {
                // 到这里,说明数组该位置上是一个链表
                for (int binCount = 0; ; ++binCount) {
                    // 插入到链表的最后面(Java7 是插入到链表的最前面)
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // TREEIFY_THRESHOLD 为 8,所以,如果新插入的值是链表中的第 8 个
                        // 会触发下面的 treeifyBin,也就是将链表转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果在该链表中找到了"相等"的 key(== 或 equals)
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        // 此时 break,那么 e 为链表中[与要插入的新值的 key "相等"]的 node
                        break;
                    p = e;
                }
            }
            // e!=null 说明存在旧值的key与要插入的key"相等"
            // 对于我们分析的put操作,下面这个 if 其实就是进行 "值覆盖",然后返回旧值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值,需要进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

和 Java7 稍微有点不一样的地方就是,Java7 是先扩容后插入新值的,Java8 先插值再扩容。

简要说明就是:

  1. 先初始化容量
  2. 找到对应位置,看是否右值,没有,直接插入
  3. 判断第一个的key是否和它相等,是的话就取出key
  4. 判断是否是红黑树的节点,是的话,调用红黑树的插入方法
  5. 将新的元素插入到链表末尾,并检查是否要转树
  6. 或者找到了相同的节点,break
  7. 对相同的节点替换值
  8. 检查是否要进行扩容

扩容分析

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            // 对应数组扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 将数组大小扩大一倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 将阈值扩大一倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // 对应使用 new HashMap(int initialCapacity) 初始化后,第一次 put 的时候
            newCap = oldThr;
        else {               // 对应使用 new HashMap() 初始化后,第一次 put 的时候
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 用新的数组大小初始化新的数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;// 如果是初始化数组,到这里就结束了,返回 newTab 即可
        if (oldTab != null) {
            // 开始遍历原数组,进行数据迁移。
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 如果该数组位置上只有单个元素,那就简单了,简单迁移这个元素就可以了
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
//                    红黑树情况
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 这块是处理链表的情况,
                        // 需要将此链表拆成两个链表,放到新的数组中,并且保留原来的先后顺序
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

get分析

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }   
	final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        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 TreeNode)
                    return ((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;
    }

hash分析

    static final int hash(Object key) {
        int h;
//        >>> 无符号右移,忽略符号位,空位都以0补齐
//        返回的是key的hashcode()与key的无符号右移16位
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

在JDK1.8的实现中,优化了高位运算的算法,通过hashCode()的高16位异或低16位实现 。然后再通过h & (table.length -1)来得到该对象在数据中保存的位置。

位运算(&)效率要比代替取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

X % 2^n = X & (2^n – 1)

2^n 表示2的n次方,也就是说,一个数对2^n取模 == 一个数和(2^n – 1)做按位与运算 。

假设n为3,则2^3 = 8,表示成2进制就是1000。2^3 = 7 ,即0111。

此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。

ConcurrentHashMap源码分析

初始化

    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
//        这个初始化方法有点意思,通过提供初始容量,计算了 sizeCtl,sizeCtl = 【 (1.5 * initialCapacity + 1),
// 然后向上取最近的 2 的 n 次方】。如 initialCapacity 为 10,那么得到 sizeCtl 为 16,如果 initialCapacity 为 11,得到 sizeCtl 为 32。
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

get分析

先进行一次再散列,然后使用这个散列值通过散列运算定位到segment,再通过散列算法定位到元素

public V get(Object key){
    int hash = hash(key.hashcode());
    return segmenFor(hash).get(key,hash);
}

get的高效在于整个get过程不需要加锁,除非读到的值是空才会加锁重读。原因是它的get方法里将要使用的共享变量都定义成了volatile类型的,见下面:

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

    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
    }

    public final K getKey()       { return key; }
    public final V getValue()     { return val; }
    public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
    public final String toString(){ return key + "=" + val; }
    public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

    public final boolean equals(Object o) {
        Object k, v, u; Map.Entry<?,?> e;
        return ((o instanceof Map.Entry) &&
                (k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
                (v = e.getValue()) != null &&
                (k == key || k.equals(key)) &&
                (v == (u = val) || v.equals(u)));
    }

    /**
     * Virtualized support for map.get(); overridden in subclasses.
     */
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

定义成volatile的变量能够在线程之间保持可见性,能够被多线程同时读,并且不会读到过期的值

  • 12 min read

CONTRIBUTORS


  • 12 min read