Java8集合系列之HashMap（四）

Map数据结构相比较List而言无疑在底层实现变的更复杂了一些，Map系列的源码学习尝试从最基本最常用的HashMap成员开始。其中设计思路部分取自于JDK1.8HashMap源码中英文的翻译，这部分内容感觉对HashMap的源码整体实现的学习和理解还是有一定帮助，值得一看。

HashMap 设计思路

初试容量和负载因子

HashMap基于哈希表的Map接口实现，并允许null键和null值。（HashMap类大致相当于Hashtable，除了它是不同步的并允许null）。这个类不保证映射的顺序。这个实现提供了基本操作（get和put）的恒定时间性能，假设散列函数在桶中正确地分散条目。对集合视图的迭代时间与HashMap实例的容量和键值映射的数量相关。因此，如果要求迭代性能较好，不要将初始容量设置得太高（或负载系数太低），这一点非常重要。

HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。负载因子是已存储条目数目与容量的一个比例，超过这个比例会触发哈希表的自动扩容。 当散列表中的条目数量超过负载因子和当前容量的乘积时，散列表被重新散列（即，重建内部数据结构），使得散列表具有大约两倍的桶数量。

一般来说，默认负载因子（0.75）在时间和空间成本之间提供了良好的平衡。较高的值会减少空间开销，但会增加查找成本，因为碰撞会跟着增加，就会逐渐失去哈希表的优势。在设置其初始容量时，应考虑映射中的预期条目数及其负载系数，以便减少扩容的次数。如果初始容量乘以负载系数大于需要存储的最大条目数，则不会发生重新擦除（扩容）操作。

如果许多映射要存储在HashMap实例中，则使用足够大的容量来创建映射将比不断地扩容来满足映射条目的存储更加高效。注意，使用具有相同hashCode（）的许多键会减慢散列表的性能。为了改善影响，当键是可比较（Comparable）时，此类可以使用键之间的比较顺序来帮助打破关系。

线程不安全

请注意，HashMap此实现未同步。如果多个线程并发访问散列映射，并且至少一个线程在结构上修改映射，那么它必须在外部同步。（这种结构修改是指添加或删除一个或多个映射的任何操作。不过，仅仅改变该实例已经包含的键相关联的值不是结构修改。）这通常通过在自然地封装映射的某个对象上同步来实现。

如果没有这样的对象存在，映射应该使用Collections.synchronizedMap方法“包装”。这最好在创建时完成，以防止意外的不同步访问，如：

1	Map m = Collections.synchronizedMap(new HashMap());

所有这个类的“集合视图方法”返回的迭代器都是失败的：如果在创建迭代器之后的任何时候结构地修改映射，除了通过迭代器自己的remove方法之外，迭代器将抛出一个ConcurrentModificationException。因此，面对并发修改，迭代器快速而干净地失败（fail-fast），而不是在将来的未确定时间冒任意的，非确定性的行为。

    /**
     * 演示Map结构修改引发异常
     * @param args
     */
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        map.put("语文", 1);
        map.put("数学", 2);
        map.put("英语", 3);
        map.put("历史", 4);
        map.put("政治", 5);
        map.put("地理", 6);
        map.put("生物", 7);
        map.put("化学", 8);
        //error：Exception in thread "main" java.util.ConcurrentModificationException
//      for(Entry<String, Integer> entry : map.entrySet()) {
//          if(entry.getKey().equals("语文")){
//              map.remove(entry.getKey());
//              map.entrySet().remove(entry);
//          }
//      }
        //success!
        Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Entry<String,  Integer> entry = (Entry<String,  Integer>) iterator.next();
            if(entry.getKey().equals("语文")){
                iterator.remove();
            }
        }
        for(Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }

注意，迭代器的故障快速行为不能被保证，因为一般来说，在不同步并发修改的情况下不可能做出任何硬的保证。（意思就是有时候会跑出错误有时候不一定会抛出。）故障快速迭代器在尽力而为的基础上抛出ConcurrentModificationException。因此，编写一个依赖于此异常的程序是正确的是错误的：迭代器的fail-fast行为应该仅用于检测bug。

HashMap 源码分析

构造方法

//Map默认初始的容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//默认负载因子，0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//最大容量，如果更高的值由具有参数的任何构造函数隐式指定，则使用此容量。
//必须是二的幂<= 1 << 30。
static final int MAXIMUM_CAPACITY = 1 << 30;
//扩容的阀值=capacity * load factor
int threshold;
//哈希表的负载因子
final float loadFactor;
//将负载因子设置为默认的负载因子值
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

在执行下列代码new一个HashMap的时候，只做了一件事，就是将负载因子设置为默认的负载因子值。用默认的初试容量构造一个空的（empty）HashMap。而真正创建HashMap则是在我们第一次添加条目的时候进行。

1	HashMap<String, String> hashMap =new HashMap<String, String>();

put(K key, V value)

static final int TREEIFY_THRESHOLD = 8;
...
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//HashMap里面自带了静态的hash方法
static final int hash(Object key) {
    int h;
    //1.这里姑且思考一下为什么下面的位运算符是^(异或)，因为异或能确保改变任意一个位值（0/1）都会改变最终的hash值，而与和或都不能做到，这一点我起初并不知道，还是同学无意间讨论提出来的。
    //2.>>> :按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。
    //3.根据key值获取的hash
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//真正添加k-v方法
//onlyIfAbsent：如果为true，则不改变存在的值。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; //数组，用来存放条目，就是哈希表了
    Node<K,V> p; 
    int n, i;
    //如果哈希表为null，则说明是第一次添加了，需要调用resize()方法，创建哈希表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)//如p为空，则未发生碰撞
        tab[i] = newNode(hash, key, value, null);//以该键值对创建新Node
    else {//如p不为空，则发生碰撞
        Node<K,V> e; 
        K k;
        //p此时为碰撞域的第一个Node，如果key值相同
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)//如果key值不同，而且还是TreeNode类型，则按照TreeNode的方式添加条目
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//如果key值不同，不是TreeNode，则说明是链表的形式处理碰撞
            for (int binCount = 0; ; ++binCount) {
                //到达链表的最后一个结点，直接挂在结点后面
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果超过链表结点数目阀值8，则将该数组index下的链表转化为二叉树（实际是红黑树）提高查询效率
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //遇到key值相同的结点，就直接break中断
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果存在key值相同的条目，则替换原来的值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)//当哈希表内存储条目超过阀值时，重新扩容。
        resize();
    afterNodeInsertion(evict);//留给LinkedHashMap拓展的，LinkedHashMap继承了HashMap，并且实现了afterNodeInsertion()方法
    return null;
}

treeifyBin

对于数组中链表长度较长的链表（长度大于默认值8）进行二叉树化，但是需要注意的是，先要判断这个数组的长度，如果数组的长度tab.length<64，这个时候没必要去转化为红黑树，而是进行`resize()`扩容。

static final int MIN_TREEIFY_CAPACITY = 64;
/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果tab=null或者tab数组的长度小于需要链表二叉树化时的最小数组长度（64）时候，进行重新散列。
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //hd.treeify调整为红黑树
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

resize

有两种情况会调用resize()方法，其一是当第一次在HashMap中添加数据时候，其二是当冲突链表的长度超过TREEIFY_THRESHOLD=8的时候，会检查当前数组的长度，如果数组长度小于MIN_TREEIFY_CAPACITY=64也会调用resize()方法。

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//数组目前的长度
        int oldThr = threshold;//数组扩容的阈值
        int newCap, newThr = 0;
        ///////////////oldTab.length>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) // initial capacity was placed in threshold
            newCap = oldThr;
        else {      //第一次创建数组时，用默认值：默认负载因子0.75*默认长度16
            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);
        }
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
           ...
           //重新散列
        }
        return newTab;
    }

以上可以看出HashMap的数据结构主要由数组、链表和红黑树构成，而put方法的主要流程梳理下来应该是比较清晰的了，这里面有几个关键的点需要注意：

如果没发生碰撞，直接new一个新node，赋值到tab数组中。
如果发生碰撞，则根据碰撞数目的大小，用两种方式来处理碰撞：
- 链表结构（桶内条目没超过转变阀值）
- 红黑树结构（桶内条目超过转变阀值）
遇到key值相同的，用新值替换旧值
条目数目超过负载阀值（数组长度*负载因子0.75），进行自动扩容，数组长度翻倍

另外，在putVal方法中还涉及到resize(…)、newNode(…)、treeifyBin(…)等具体功能方法，以及Node、TreeNode两种结点的数据结构，在此不做详述。

get(Object key)

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);
            //循环查询链表中相同的key
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

知道put的流程之后，get查询的源码阅读起来便变得毫无压力，说一下，JDK源码中的判断逻辑确实很严密，这是应该学习的地方。

remove(Object key)

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        ///////////////此处逻辑几乎与get方法相同//////////////////////
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;//p指向目标节点（e）的前驱结点
                } while ((e = e.next) != null);
            }
        }
        ////////////////查询到需要删除的Node/////////////////////////
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)//碰撞链表的第一个结点时
                tab[index] = node.next;
            else//碰撞链表其他结点
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

-EOF-