Java Map - HashMap源码分析

HashMap 1.7及以前，底层数据结构使用 [数组+链表]，1.8 后使用 [数组+链表/红黑树] ，使用数组存储元素是因为查找快，链表是为了解决哈希冲突存在的，而红黑树是为了解决链表中查询速度慢对链表进行优化的一种数据结构。

HashMap 是非线程安全的，如果需要线程安全，使用 ConcurrentHashMap 或者 Collections.synchronizedMap() 包裹 HashMap 达到线程安全的目的。

QA

1、HashMap为什么线程不安全

初始化懒加载

// 初始化一个HashMap的时候，其实只是定义了initialCapacity和loadFactor这两个值，
// 并没有初始化数组，而是懒加载的思想，在第一次put时候通过resize()方法去加载。
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                        initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                        loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, 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;
    // 第一次个线程不安全的地方
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    ...
}

在jdk1.8中，在多线程环境下，在并发执行put操作时会发生数据覆盖的情况。
JDK1.7出现的问题，在JDK1.8中已经得到了很好的解决，JDK1.8直接在resize函数中完成了数据迁移。在进行元素插入时使用的是尾插法然后在扩容。

但是在1.8中仍会有数据覆盖这样的问题，先看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;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) //判断是否出现hash碰撞，如果没有hash碰撞则直接插入元素，此处线程不安全
        tab[i] = newNode(hash, key, value, null);
    else {
        // ...
    }
    ++modCount;
    if (++size > threshold) //++size此处线程不安全
        resize();
    afterNodeInsertion(evict);
    return null;
}

其中代码if ((p = tab[i = (n - 1) & hash]) == null) 是判断是否出现hash碰撞：
比如两个线程A、B都在进行put操作，并且hash函数计算出的插入下标是相同的，当线程A执行完第六行代码后由于时间片耗尽导致被挂起，而线程B得到时间片后在该下标处插入了元素，完成了正常的插入，然后线程A获得时间片，由于之前已经进行了hash碰撞的判断，所有此时不会再进行判断，而是直接进行插入，这就导致了线程B插入的数据被线程A覆盖了，从而线程不安全。

还有一种情况就是代码if (++size > threshold)中的++size：
同样还是线程A、B，这两个线程同时进行put操作时，假设当前HashMap的zise大小为10，当线程A执行到此行代码时，从主内存中获得size的值为10后准备进行+1操作，但是由于时间片耗尽只好让出CPU，线程B快乐的拿到CPU还是从主内存中拿到size的值10进行+1操作，完成了put操作并将size=11写回主内存，然后线程A再次拿到CPU并继续执行(此时size的值仍为10)，当执行完put操作后，还是将size=11写回内存，此时线程A、B都执行了一次put操作，但是size的值只增加了1，所有说还是由于数据覆盖又导致了线程不安全。

在jdk1.7中，在多线程环境下，当并发执行扩容时会造成死循环(环形链)或数据丢失。

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

JDK1.7中HashMap的transfer函数如上，扩容操作（先扩容再头插法插入）会重新定位每个桶的下标，并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转，这也是造成死循环和数据丢失的关键。

2、HashMap为什么选用红黑树这种数据结构优化链表

在JDK1.8之后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存到红黑树中，以加快检索速度。

红黑树也是一种平衡二叉树，每个节点有一个储存位表示节点的颜色，可以是红色或者黑色。通过对任意一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有任意一条从根到叶子的路径超过最短路径的两倍，因此红黑树是一种弱平衡二叉树。

相对于AVL树来说，红黑树的旋转次数少，对于搜索、插入、删除多的操作下用红黑树。

红黑树不追求”完全平衡”，即不像AVL那样要求节点的 |balFact| <= 1，它只要求部分达到平衡，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。

HashMap中链表转为红黑树的条件
在JDK1.8之后，HashMap中的链表在满足以下两个条件时，将会转化为红黑树(即自平衡的排序二叉树)：

条件一
数组 arr[i] 处存放的链表长度大于8；
条件二
数组长度大于等于64。

满足以上两个条件，数组 arr[i] 处的链表将自动转化为红黑树，其他位置如 arr[i+1] 处的数组元素仍为链表，不受影响

3、为什么默认初始容量为2次幂？不是2次幂会怎样？讲讲 HashMap 扰动函数？

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ......
    // 如果没有hash碰撞则直接插入元素
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        ......
    }
}

n 为 2次幂，可以保证数据的均匀插入，降低哈希冲突的概率，毕竟冲突越大，代表数组中的链表/红黑树越大，从而降低Hashmap 的性能。

不管是规定 Hashmap 的 n 为 2次幂，还是扰动函数，都是为了一个目标，降低哈希冲突的概率，从而使 HashMap 性能得到优化。
规定 n 为 2次幂，是在新建 Hashmap对象初始化时，规定其容量大小的角度来优化。
扰动函数是插入 key 值时改变 key 的散列值，增大key的散列程度，降低哈希碰撞的概率来达到优化效果。

4、为什么HashMap使用高16位异或低16位计算Hash值（HashMap的扰动函数）

putVal(hash(key), key, value, false, evict);

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 计算索引下标，key的hashCode的高16位与低16位异或 对数组的长度取余
    tab[i = (n -1) & hash]
}

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

hash值是一个int类型，二进制位为32位，而HashMap的table数组初始化size为16，计算索引下标的取余操作为hash & (length - 1) ==> hash & 1111，这里面的问题是，1111只会与hashCode的低4位进行与操作，hashCode的高位并没有参与运算，会导致很多hashCode值不同而高位有区别的数最后算出来的索引是一样的。

举个例子，假设hashCode为1111110001，那么1111110001 & 1111 = 0001，高位发生变化时1011110001 & 1111 = 0001，1001110001 & 1111 = 0001，也就是说在高位发生变化时，你最后算出来的索引都一样了，这样就会导致很多数据都被放到一个数组里面了，造成性能退化。

为了避免这种情况，HashMap将 key 的高16位与低16位进行异或，这样可以保证高位的数据也参与到与运算中来，以增大索引的散列程度，让数据分布得更为均匀 (个人觉得很多博客说的减小哈希碰撞是错误的说法，因为hash碰撞指的是两个hashCode相同，这里显然不是)。

主要原因是保留高16位与低16位的特性，增大散列程度。

为什么用异或，不用&或者|操作。因为异或可以保证两个数值的特性，&运算使得结果向0靠近， |运算使得结果向1靠近。

Object类中的hashCode方法

1	public native int hashCode();

这个方法不是抽象方法，带有native关键字，底层调用C++程序。

hashCode()方法返回的是哈希码：实际上就是一个java对象的内存地址，经过哈希算法，得出的一个值。所以hashCode()方法的执行结果可以等同看做一个java对象的内存地址。

Java8 HashMap

默认值

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; // 树化阈值
static final int UNTREEIFY_THRESHOLD = 6;   // 取消树化阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化数组容量，转换为红黑树的最小数组长度为64

影响HashMap性能的两个因素

1	public HashMap(int initialCapacity, float loadFactor) {}

初始容量。创建哈希表时的容量。
负载系数。衡量哈希表在自动增加容量之前的填充程度的容量，当哈希表中的数据数量超过 (负载因子 * 当前容量) 时，哈希表将被扩容、重建。
loadFactor的默认值为0.75f 是官方给出的一个比较好的临界值，这个值是经过多次推测得出的

防蠢货能力

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * Returns a power of two size for the given target capacity.
 */
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;
}

put方法 put过程分析

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// 第四个参数 onlyIfAbsent 如果是 true，那么只有在不存在该 key 时才会进行 put 操作
// 第五个参数 evict 我们这里不关心
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 节点数组为空
    // 第一次 put 值的时候，会触发下面的 resize()，类似 java7 的第一次 put 也要初始化数组长度
    // 第一次 resize 和后续的扩容有些不一样，因为这次是数组从 null 初始化到默认的 16 或自定义的初始容量
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 节点为空
    // 找到具体的数组下标，如果此位置没有值，那么直接初始化一下 Node 并放置在这个位置就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 3. 节点不为空，发生冲突
    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;
}

调用HashMap的put方法，实际上调用了HashMap的putVal方法。
首先putVal()先用hash(key)函数计算键值对key的hash。hash(key)与数组长度做取余的位运算，得到这个键值对节点在数组中的具体下标。
进入putVal()方法，如果第一次插入元素，会调用resize()方法，初始化数组长度以及负载因子。
如果不是第一次插入，先看这个下标有没有元素，如果没有的话，直接放在这个下标。
如果这个下标已经有元素了，就会发生哈希冲突，遍历这个下标的链表，如果key值相等，就替换value；如果key值不相等，就继续向下遍历，如果遍历完成仍然key不相等，就用尾插法将元素插入到链表中，然后判断链表是否要转化成红黑树。
插入完成后，HashMap的size++，如果size大于阈值就进行数组的扩容操作。（先插入，再扩容）

resize方法扩容

resize() 方法用于初始化数组或数组扩容，每次扩容后，容量为原来的 2 倍，并进行数据迁移。

/**
 * 初始化或增加表的大小，如果表为空，根据初始容量分配。扩容表，2次幂
*/
final Node<K,V>[] resize() {
    // 获取旧元素数组的各种信息
    Node<K,V>[] oldTab = table;
    // 旧数组长度 
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧数组临界值
    int oldThr = threshold;
    // 定义新数组的长度及扩容的临界值
    int newCap, newThr = 0;
    // 如果原 table 不为空
    if (oldCap > 0) {
        // 如果数组长度达到最大值,修改临界值为最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 扩容操作(2倍)
        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 {               // zero initial threshold signifies using defaults
        // 新数组初始容量和阈值使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;  // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 16 * 0.75 
    }
    // 临界值还为0，设置临界值
    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;
    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;
}

treeifyBin方法

判断是否真的需要转换红黑树，如果数组长度小于MIN_TREEIFY_CAPACITY = 64 将会扩容resize()；
如果符合转换的条件，数组长度大于等于MIN_TREEIFY_CAPACIT(64) && 链表长度大于TREEIFY_THRESHOLD(8)，将该槽中所有的链表节点转换成树形节点，并且构造成双链表，为 treeify 转换成红黑树准备。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果table为null  或者table数组的长度小于MIN_TREEIFY_CAPACITY  64
    //MIN_TREEIFY_CAPACITY这个其实是转化成红黑树的另外一个条件，就是数组长度要大于64
    //如果小于64 就可以通过扩容的方法，来减小冲突，没有必要转换成红黑树，因为红黑树的转换也是需要很大是 时间和空间的代价
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //进行扩容
        resize();
        //获得需要树形化的 链表的第一个节点 也就是数组对应的数组节点table[i]
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            //将普通的node节点 构造成TreeNode  拥有更多的属性
                /**
                 * parent
                 * right
                 * left
                 * red
                 * key
                 * value
                 * next
                 * prev
                 */
            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);
        //替换成 构造成双链表的节点
        if ((tab[index] = hd) != null)
        //进行红黑树转换
            hd.treeify(tab);
    }
}

treeify方法

该方法的主要作用就是，将链表的元素一个一个的插入到树中，并且保持排序树的特性：当左、右子树不为空的时候左子树小于根节点右子树大于根节点。
这里的大小通过comparable方法比较key的大小。如果key没有实现该接口，那么通过比较hash值来判定。

/**
* 将链表中每个值进行红黑树插入操作
*/
final void treeify(Node<K, V>[] tab) {
    TreeNode<K, V> root = null;
    for (TreeNode<K, V> x = this, next; x != null; x = next) {
        //根据链表进行遍历
        next = (TreeNode<K, V>) x.next;
        x.left = x.right = null;
        if (root == null) {
            //如果根节点还没设置则当前节点设置为根节点root
            x.parent = null;
            //根节点一定是黑色的
            x.red = false;
            root = x;
        } else {
            //获取当前循环节点的key和哈希值
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            //每次都从根节点开始循环
            TreeNode<K, V> p = root;
            for (; ; ) {
                //遍历当前红黑树
                int dir;
                //获得p的hash值和key
                int ph = p.hash;
                K pk = p.key;
                //比较hash值，然后根据比较值dir决定插入左边还是右边
                if (ph > h) {
                    dir = -1;
                } else if (ph < h) {
                    dir = 1;
                } else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0) {
                    //k不是不是课比较类或者比较结果为0，使用tieBreakOrder方法比较
                    dir = tieBreakOrder(k, pk);
                }
                TreeNode<K, V> xp = p;
                p = (dir <= 0) ? p.left : p.right;
                //仅当当前要插入的位置上没有节点时才进行插入，否则继续向下遍历
                if (p == null) {
                    //设置父节点
                    x.parent = xp;
                    //根据dir值设置为父节点的左右子节点
                    if (dir <= 0) {
                        xp.left = x;
                    } else {
                        xp.right = x;
                    }
                    //插入成功后平衡红黑树
                    root = balanceInsertion(root, x);
                    //跳出当前循环
                    break;
                }
            }
        }
    }
    //确保当前的root是直接落在table数组上的
    moveRootToFront(tab, root);
}

Java7 HashMap

HashSet

HashSet仅仅是对HashMap做了一层包装，也就是说HashSet里面有一个HashMap(适配器模式)。

//HashSet是对HashMap的简单包装
public class HashSet<E>
{
	......
	private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

Java Map - HashMap源码分析

Java Map - HashMap源码分析

QA

1、HashMap为什么线程不安全

2、HashMap为什么选用红黑树这种数据结构优化链表

3、为什么默认初始容量为2次幂？不是2次幂会怎样？讲讲 HashMap 扰动函数？

4、为什么HashMap使用高16位异或低16位计算Hash值（HashMap的扰动函数）

Object类中的hashCode方法

Java8 HashMap

默认值

影响HashMap性能的两个因素

防蠢货能力

put方法 put过程分析

resize方法 扩容

treeifyBin方法

treeify方法

Java7 HashMap

HashSet

resize方法扩容