HashMap工作原理及源码分析

设计理念

hash

HashMap是一种基于哈希表(hash table)实现的map,哈希表(也叫关联数组)一种通用的数据结构,其概念也比较简单:key经过hash函数作用后得到一个槽(buckets或slots)的索引(index),槽中保存着我们想要获取的值。如图:

很容易想到,一些不同的key经过同一hash函数后可能产生相同的索引,也就是产生了冲突,这是在所难免的。
所以利用哈希表这种数据结构实现具体类时,需要:

  1. 设计个好的hash函数,使冲突尽可能的减少
  2. 解决发生冲突后如何处理

源码分析部分会具体讲HashMap是怎么设计hash函数和解决冲突的!

类图

HashMap同时继承了抽象类AbstractMap与接口Map。

在语法层面继承接口Map是多余的,这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的,起到了文档的作用。

AbstractMap提供了Map操作的基本实现,减少了实现Map接口的成本。

特性

HashMap官方描述:

 * Hash table based implementation of the <tt>Map</tt> interface.  This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.

几个重要信息:

  1. 基于Map接口实现
  2. 允许null键/值
  3. 非同步、线程非安全的
  4. 不保证有序(比如插入的顺序)
  5. 也不保证序不随时间变化

源码分析

一些常量

     //默认初始化值,1左移4位即16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //默认负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //链地址冲突解决,链表转红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;
     //当红黑树的结点数目<6时,红黑树结构转化为单链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //树化的最小容量
    static final int MIN_TREEIFY_CAPACITY = 64;

重要参数

  • capacity
    capacity就是buckets的数目
  • loadFactor
    loadFactor就是buckets填满程度的最大比例。DEFAULT_LOAD_FACTOR = 0.75f;

put方法

大致思路

  1. 对key的hashCode()做hash,然后再计算index
  2. 如果没碰撞直接放到bucket里
  3. 如果碰撞了,以链表的形式存在buckets后
  4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD),就把链表转换成红黑树
  5. 如果节点已经存在就替换old value(保证key的唯一性)
  6. 如果bucket满了(超过load factor*current capacity),就要resize

具体实现

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);//对key的hashCode()做hash
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//tab为null则创建
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//计算index并对null做处理,index算法(n-1)&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 {//该链为链表
                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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key 写入
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//超过loadfactor*current capacity,resize
            resize();
        afterNodeInsertion(evict);
        return null;
    }


get方法

大致思路

  1. bucket里的第一个节点,直接命中
  2. 如果有冲突,则通过key.equals(k)去查找对应的entry
  3. 若为树,则在树中通过key.equals(k)查找,O(logn)
  4. 若为链表,则在链表中通过key.equals(k)查找,O(n)

具体实现

    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)//在树中get
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {//在链表中get
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

hash方法

在get和put的过程中,计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标。如图:

hash实现

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

这个函数的作用就是:高16bit不变,低16bit和高16bit做了一个异或。
设计hash函数时,因为目前的table长度n为2的幂,而计算下标的算法是(n - 1) & hash,使用了&位操作,而非%求余!

不妨思考一下,在n - 1为15(0x1111)时,其实散列真正生效的只是hash的低4bit的有效位,容易发生碰撞。

因此,设计者想了一个顾全大局的方法(综合考虑了速度、作用、质量),就是把高16bit和低16bit异或了一下。设计者还解释到因为现在大多数的hashCode的分布已经很不错了,就算是发生了碰撞也用O(logn)的tree去做了。仅仅异或一下,既减少了系统的开销,也不会造成的因为高位没有参与下标的计算(table长度比较小时),从而引起的碰撞。

如果还是产生了频繁的碰撞,怎么解决?

在Java 8之前的实现中是用链表解决冲突的,在产生碰撞的情况下,进行get时,两步的时间复杂度是O(1)+O(n)。因此,当碰撞很厉害的时候n很大,O(n)的速度显然是影响速度的。

因此在Java 8中,利用红黑树替换链表,这样复杂度就变成了O(1)+O(logn)了,这样在n很大的时候,能够比较理想的解决这个问题。

resize方法

当put时,如果发现目前的bucket占用程度已经超过了Load Factor所希望的比例,那么就会发生resize。

在resize的过程,简单的说就是把bucket扩充为2倍,之后重新计算index,把节点再放到新的bucket中。

因为bucket的大小使用的是2次幂的扩展(指长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置!

怎么理解呢?
例如16扩容到32,具体的变化如下:

    //16 => 32
    //n-1   0000 0000 0000 0000 0000 0000 0000 1111    =>    0000 0000 0000 0000 0000 0000 0001 1111
    //hash  =>  (n-1)^hash
    //hash1 1111 0000 0000 0000 0000 1111 0000 0101    =>    1111 0000 0000 0000 0000 1111 0000 0101
    //hash2 1111 0000 0000 0000 0000 1111 0001 0101    =>    1111 0000 0000 0000 0000 1111 0001 0101

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit,因此新的index就会发生这样的变化:

因此,我们在扩充HashMap的时候,不需要重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图:

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。

源码实现

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)//没超过最大值,就扩充为原来的2倍
                newThr = oldThr << 1; // double threshold
        
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {//计算新的resize上限
            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;
        if (oldTab != null) {// 把每个bucket都移动到新的buckets中
            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 {// 原索引+oldCap
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {// 原索引放到bucket里
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {// 原索引+oldCap放到bucket里
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

resize 并发死循环问题

并发情况下,resize时,链地址可能形成相互引用的环路,导致get寻找对应key时发生死循环!

死循环形成详细原因可以参考这篇文章
老生常谈,HashMap的死循环

如图所示,节点a和b互相引用,形成了一个环,当在数组该位置get寻找对应的key时,就发生了死循环。

另外,如果线程2把newTable设置成到内部的table,节点c的数据就丢了,看来还有数据遗失的问题。

所以在并发的情况,发生扩容时,可能会产生循环链表,在执行get的时候,会触发死循环,引起CPU的100%问题,所以一定要避免在并发环境下使用HashMap。
曾经有人把这个问题报给了Sun,不过Sun不认为这是一个bug,因为在HashMap本来就不支持多线程使用,要并发就用ConcurrentHashmap。

序列化

保存数据的table数组为transient的,也就是说在进行序列化时,并不会包含该成员。

    transient Node<K,V>[] table;
    transient Set<Map.Entry<K,V>> entrySet;

为什么呢?
因为Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值,可以试想下面的场景:

我们在机器A上算出对象A的哈希值与索引,然后把它插入到HashMap中,然后把该HashMap序列化后,在机器B上重新算对象的哈希值与索引,这与机器A上算出的是不一样的,所以我们在机器B上get对象A时,会得到错误的结果。
所以说,当序列化一个HashMap对象时,保存Entry的table是不需要序列化进来的,因为它在另一台机器上是错误的。

因为这个原因,HashMap重写了writeObject与readObject 方法:

   private void writeObject(java.io.ObjectOutputStream s)
        throws IOException {
        int buckets = capacity();
        // Write out the threshold, loadfactor, and any hidden stuff
        s.defaultWriteObject();
        s.writeInt(buckets);
        s.writeInt(size);
        internalWriteEntries(s);
    }

    /**
     * Reconstitute the {@code HashMap} instance from a stream (i.e.,
     * deserialize it).
     */
    private void readObject(java.io.ObjectInputStream s)
        throws IOException, ClassNotFoundException {
        // Read in the threshold (ignored), loadfactor, and any hidden stuff
        s.defaultReadObject();
        reinitialize();
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        s.readInt();                // Read and ignore number of buckets
        int mappings = s.readInt(); // Read number of mappings (size)
        if (mappings < 0)
            throw new InvalidObjectException("Illegal mappings count: " +
                                             mappings);
        else if (mappings > 0) { // (if zero, use defaults)
            // Size the table using given load factor only if within
            // range of 0.25...4.0
            float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
            float fc = (float)mappings / lf + 1.0f;
            int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                       DEFAULT_INITIAL_CAPACITY :
                       (fc >= MAXIMUM_CAPACITY) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor((int)fc));
            float ft = (float)cap * lf;
            threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                         (int)ft : Integer.MAX_VALUE);
            @SuppressWarnings({"rawtypes","unchecked"})
                Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
            table = tab;

            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < mappings; i++) {
                @SuppressWarnings("unchecked")
                    K key = (K) s.readObject();
                @SuppressWarnings("unchecked")
                    V value = (V) s.readObject();
                putVal(hash(key), key, value, false, false);
            }
        }
    }

参考:

http://liujiacai.net/blog/2015/09/03/java-hashmap/

http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/

老生常谈,HashMap的死循环

# java 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×