Java源码之HashMap

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/07/24/Java源码之HashMap/

访问原文「Java源码之HashMap」

关于HashMap

相信同学们在Coding（搬砖）的过程中经常会用到HashMap，那么HashMap到底是个什么东东呢？
以JDK8来讲，HashMap继承Map接口，在Map接口中描述Map是“An object that maps keys to values. A map cannot contain duplicate keys each key can map to at most one value.” 也就是说Map是一个映射键值的对象。映射中不能包含重复键，并且每个键可以映射到最多一个值。HashMap实现了Map接口，并且为基本操作（如：get、put）提供了常量时间的性能。

HashMap主要成员变量

下面的代码注释里详细的说明了HashMap的几个重要的成员变量。从这几个变量中可以分析得出，所有的键值对都存放在table变量中，而table变量的大小不是固定不变的，是在动态变化的，而且大小始终为2的幂。

/**
 * HashMap的表结构，在首次使用的时候进行初始化，然后在需要的时候进行大小调整
 * 表的大小始终为2的幂
 * 初始值为16（DEFAULT_INITIAL_CAPACITY）
 */
transient Node<K,V>[] table;

/**
 * 映射项集合
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * Map中映射对的数量
 */
transient int size;

/**
 * 这个HashMap已被结构化修改的次数
 * 结构修改是改变HashMap中的映射数或者修改其内部结构（例如rehash）的修改次数。
 * 此字段用于使HashMap的Collection-views上迭代器更快的失效。 （请参阅ConcurrentModificationException）。
 */
transient int modCount;

/**
 * 下一次调整大小的阈值 (capacity * load factor).
 */
int threshold;

/**
 * 负载系数，默认为0.75f（DEFAULT_LOAD_FACTOR）
 */
final float loadFactor;

从上面的代码总可以看到，table属性的类型为Node，这个Node实现了Map.Entry接口，所以本质上还是Map.Entry。另外，HashMap包含另外一种TreeNode，TreeNode本身为红黑树结构。在HashMap中，当一个普通Node（Plain Node）的长度大于一定值时会转换为TreeNode，而TreeNode长度小于一定值时会转换普通Node。

从下面的代码中可以看到，Node实现了Map.Entry接口，并且本身为链表结构，这样是为了处理不同键值可能会出现相同Hash的情况。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        // 下一个Node'指针'
        Node<K,V> next;

        ...
    }

HashMap中的get方法

get方法是我们常用的方法之一，下面是这个方法的源码。这个方法非常简单，可以看到它是委托给了getNode方法。

/**
 *
 * 返回键为key对应的值，如果不存在这个键，则返回null
 *
 * 更正式的说明是，如果这个map包含key到value的映射，这个方法会返回value
 * 否则返回null
 *
 * 当然，返回null并不能说明这个map不包含这个key的映射，可以过containsKey这个方法判断是否包含这个key
 *
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

下面是getNode方法，已经在主要代码上面加上了注释，比较好理解。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table为null或者长度不大于0则返回null
    // 根据key的hash值判断table中对应下标有没有对应的值，没有的话返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断第一个Node的键是否与查询的key一致，一致的话返回这个映射
        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);
            // 如果不是树结构就是链表结构，然后沿着链表进行查询
            // 如果链表节点的key与查询的key一致，返回这个映射
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 没有查询到返回null
    return null;
}

HashMap中的put方法

put方法也是我们常用的方法之一，下面是这个方法的源码。这个方法也非常简单，可以看到它是委托给了putVal方法。

/**
 * 
 * 在map中放入key到value的映射
 * 如果已经存在key，则更新这个key对应的value
 *
 * @param key 与指定值相关联的键
 * @param value 与指定键关联的值
 * @return 与键关联的前一个值，如果没有映射键的键值，则为null。(null返回还可以表明映射之前与键关联的映射。)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

下面是putVal方法，方法比getNode复杂不少，但是整体思路也是很简单的。简单描述就是首先查找时候已经存在键为key的映射，如果存在的话，判断是否允许替换旧值，如果允许则替换；如果不存在键为key的映射，则新建一个这个映射，如果存在hash冲突，则加载对应hash列表的最后。最后判断map的大小是否大于需要调整大小的阈值，大于的话进行resize。

/**
 * 实现了Map.put以及相关方法
 *
 * @param hash 键的hash值
 * @param key 键
 * @param value 键对应的值
 * @param onlyIfAbsent 如果是true, 不修改已经存在的值
 * @param evict 如果是false, 表示在创建模式中
 * @return 键对应的旧值，没有旧值返回null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果table是null或者空，进行resize
    // 实际上HashMap实例初始化的时候不会初始化table，而是在使用的时候初始化，也就是这段代码
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果在table中找不到对应下标为hash值的Node，则新建一个Node，并将这个Node放入在table下标为hash值的地方
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果找到的Node中的键与key一直，那么e=p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果找到的Node为TreeNode，那么调用TreeNode的putTreeVal放入该映射
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 循环判断是否有Node满足键与将要放入的key一致
            for (int binCount = 0; ; ++binCount) {
                // 如果没有找到与key一致的Node则新建一个Node
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 判断这个Node列表长度是否大于等于要树形化的阈值
                    // 大于等于的话将这个Node列表转换为树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }

                // 如果找到的Node中的键与key一致，那么e=p
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果有Node满足键与将要放入的key一致
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 是否允许替换旧值，允许则替换
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果map大小大于阈值，则resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

HashMap中的resize方法

HashMap中很重要的一个函数就是resize，代表HashMap容量的调整。首先是在首次往HashMap中放入数据的时候需要初始化table大小，另外是在map中映射数量大于threshold的时候进行容量调整。在具体的调整过程中，分为树形列表调整和普通单链表的调整。详细请看下面的注释。

/**
  * 初始化或将大小增加一倍。
  * 如果为空，则在字段阈值中分配初始容量目标。
  * 否则，由于我们使用的是2的幂次扩展，每个容器中的元素必须保持在相同的索引中，或者在新表中使用2偏移量移动。
  *
  * @return the table
  */
 final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table;
     int oldCap = (oldTab == null) ? 0 : oldTab.length;
     int oldThr = threshold;
     int newCap, newThr = 0;
     // 如果已经存在容量大于0
     if (oldCap > 0) {
         // 如果已经存在容量大于最大值，不改变容量大小，改变阈值为Integer最大值
         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
     }
     // 如果旧阈值大于0，新容量为旧阈值
     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) {
         float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                   (int)ft : Integer.MAX_VALUE);
     }
     threshold = newThr;
     // 将旧table的数据拷贝至新table
     @SuppressWarnings({"rawtypes","unchecked"})
         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     table = 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;
                 // TreeNode使用本身的方法赋值
                 else if (e instanceof TreeNode)
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 // 链表赋值，具体复制的过程中考虑到了hash值的高位修改问题，不是很复杂，不详细说明
                 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);
                     // 处理'低位'hash列表的尾节点
                     if (loTail != null) {
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     // 处理'高位'hash列表的尾节点
                     if (hiTail != null) {
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
 }

###　小结一下

本篇文章详细介绍了HashMap的相关内容，包含主要成员变量和主要成员方法。但是可以看到的是，HashMap的Node分为普通单链表和树链表，只介绍的单链表，而有一些操作是委托给树链表解决的。首先要说明的是，如果key的hash分散性很好，基本不会将单链表转换为树链表；另外树链表是红黑树，属于比较复杂并且可以单独拿出讲，或者说比较独立不放在HashMap里讲也可以。有时间的话我会对红黑树这块做一个专门的讲解。