HashMap解析

[TOC]

存储结构

内部包含了一个 Entry 类型的数组 table,1.8之后改成Node。

//transient Entry[] table;
  transient Node<K,V>[] table;

Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当
成一个桶，一个桶存放一个链表。HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值和散列桶取模运算结
果相同的 Entry。

static class Node<K,V> implements Map.Entry<K,V> {
	//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置
	final int hash;
	final K key;
	V value;
	//指向单链表的下一个节点
	Node<K,V> next;

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

put方法

//put方法，会先调用一个hash()方法，得到当前key的一个hash值，
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法，我们姑且先认为是key.hashCode()，其实不是的，一会儿细讲
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

//把hash值和当前的key，value传入进来
//这里onlyIfAbsent如果为true，表明不能修改已经存在的值，因此我们传入false
//evict只有在方法 afterNodeInsertion(boolean 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;
	//判断table是否为空，如果空的话，会先调用resize扩容
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	//根据当前key的hash值找到它在数组中的下标，判断当前下标位置是否已经存在元素，
	//若没有，则把key、value包装成Node节点，直接添加到此位置。
	// i = (n - 1) & hash 是计算下标位置的，为什么这样算，后边讲
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else { 
		//如果当前位置已经有元素了，分为三种情况。
		Node<K,V> e; K k;
		//1.当前位置元素的hash值等于传过来的hash，并且他们的key值也相等，
		//则把p赋值给e，跳转到①处，后续需要做值的覆盖处理
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		//2.如果当前是红黑树结构，则把它加入到红黑树 
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
		//3.说明此位置已存在元素，并且是普通链表结构，则采用尾插法，把新节点加入到链表尾部
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					//如果头结点的下一个节点为空，则插入新节点
					p.next = newNode(hash, key, value, null);
					//如果在插入的过程中，链表长度超过了8，则转化为红黑树
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					//插入成功之后，跳出循环，跳转到①处
					break;
				}
				//若在链表中找到了相同key的话，直接退出循环，跳转到①处
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		//① 
		//1.说明发生了碰撞，e代表的是旧值，因此节点位置不变，但是需要替换为新值
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			//用新值替换旧值，并返回旧值。
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			//看方法名字即可知，这是在node被访问之后需要做的操作。其实此处是一个空实现，
			//只有在 LinkedHashMap才会实现，用于实现根据访问先后顺序对元素进行排序，hashmap不提供排序功能
			// Callbacks to allow LinkedHashMap post-actions
			//void afterNodeAccess(Node<K,V> p) { }
			afterNodeAccess(e);
			return oldValue;
		}
	}
	//fail-fast机制
	++modCount;
	//如果当前数组中的元素个数超过阈值，则扩容
	if (++size > threshold)
		resize();
	//同样的空实现
	afterNodeInsertion(evict);
	return null;
}

Hash方法

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

两个值进行与运算，结果会趋向于0；或运算，结果会趋向于1；而只有异或运算，0和1的比例可以达到1:1的平衡状态。（非呢？别扯犊子了，两个值怎么做非运算。。。）
所以，异或运算之后，可以让结果的随机性更大，而随机性大了之后，哈希碰撞的概率当然就更小了

这里，会先判断key是否为空，若为空则返回0。这也说明了hashMap是支持key传 null 的。若非空，则先计算key的hashCode值，赋值给h，然后把h右移16位，并与原来的h进行异或处理。为什么要这样做，这样做有什么好处呢？

可以看到，其实相当于，我们把高16位值和当前h的低16位进行了混合，这样可以尽量保留高16位的特征，从而降低哈希碰撞的概率。

思考一下，为什么这样做，就可以降低哈希碰撞的概率呢？先别着急，我们需要结合 i = (n - 1) & hash 这一段运算来理解。

i = (n - 1) & hash

i = (n - 1) & hash

令 x = 1<<4，即 x 为 2 的 4 次方，它具有以下性质：

令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：

y :       10110010
x-1 :     00001111
y&(x-1) : 00000010

这个性质和 y 对 x 取模效果是一样的：

y :   10110010
x :   00010000
y%x : 00000010

get方法

• 首先将key hash之后取得所定位的桶
• 如果桶为空，则直接返回null
• 否则判断桶的第一个位置（有可能是链表、红黑树）的key是否为查询的key，是就直接返回value
• 如果第一个不匹配，则判断它的下一个是红黑树还是链表
• 红黑树就按照树的查找方式返回值
• 不然就按照链表的方式遍历匹配返回值

为什么HashMap链表会形成死循环

准确的讲应该是 JDK1.7 的 HashMap 链表会有死循环的可能，因为JDK1.7是采用的头插法，在多线程环境下有可能会使链表形成环状，从而导致死循环。JDK1.8做了改进，用的是尾插法，不会产生死循环。

JDK7与JDK8中HashMap的不同点

• JDK8中使用了红黑树

• JDK7中链表的插入使用的头插法（扩容转移元素的时候也是使用的头插法，头插法速度更快，无需遍历链表，但是在多线程扩容的情况下使用头插法会出现循环链表的问题，导致CPU飙升），JDK8中链表使用的尾插法（JDK8中反正要去计算链表当前结点的个数，反正要遍历的链表的，所以直接使用尾插法

那为啥用16不用别的呢？

因为在使用是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。

只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。这是为了实现均匀分布。

为什么是0.75？

HashMap负载因子为什么是0.75？
HashMap有一个初始容量大小，默认是16
static final int DEAFULT_INITIAL_CAPACITY = 1 << 4; // aka 16
为了减少冲突概率，当HashMap的数组长度达到一个临界值就会触发扩容，把所有元素rehash再放回容器中，这是一个非常耗时的操作。
而这个临界值由负载因子和当前的容量大小来决定：
DEFAULT_INITIAL_CAPACITYDEFAULT_LOAD_FACTOR
即默认情况下数组长度是160.75=12时，触发扩容操作。
所以使用hash容器时尽量预估自己的数据量来设置初始值。
那么，为什么负载因子要默认为0.75，在HashMap注释中有这么一段：

Ideally, under random hashCodes, the frequency of
\* nodes in bins follows a Poisson distribution
\* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
\* parameter of about 0.5 on average for the default resizing
\* threshold of 0.75, although with a large variance because of
\* resizing granularity. Ignoring variance, the expected
\* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
\* factorial(k)). The first values are:
*
\* 0:  0.60653066
\* 1:  0.30326533
\* 2:  0.07581633
\* 3:  0.01263606
\* 4:  0.00157952
\* 5:  0.00015795
\* 6:  0.00001316
\* 7:  0.00000094
\* 8:  0.00000006
\* more: less than 1 in ten million

在理想情况下，使用随机哈希吗，节点出现的频率在hash桶中遵循泊松分布，同时给出了桶中元素的个数和概率的对照表。
从上表可以看出当桶中元素到达8个的时候，概率已经变得非常小，也就是说用0.75作为负载因子，每个碰撞位置的链表长度超过8个是几乎不可能的。
hash容器指定初始容量尽量为2的幂次方。
HashMap负载因子为0.75是空间和时间成本的一种折中。

什么时候变成红黑树

一个是链表长度到8,一个是数组长度到64.

HashMap在多线程环境下存在线程安全问题，那你一般都是怎么处理这种情况的？

1.Hashtable

2.ConcurrentHashMap

不过出于线程并发度的原因，我都会舍弃前两者使用最后的ConcurrentHashMap，他的性能和效率明显高于前两者。

Hashtable效率低

他在对数据操作的时候都会上锁，所以效率比较低下。

扩容

resize 方法：扩容数组,分为两个部分，一个是扩容数组，一个是重新规划长度。

重新规划长度和阈值，如果长度发生了变化，部分数据节点也要重新排列。

1 HashMap实行了懒加载, 新建HashMap时不会对table进行赋值, 而是到第一次插入时, 进行resize时构建table;
2 当HashMap.size 大于 threshold时, 会进行resize;threshold的值我们在上一次分享中提到过: 当第一次构建时, 如果没有指定HashMap.table的初始长度, 就用默认值16, 否则就是指定的值; 然后不管是第一次构建还是后续扩容, threshold = table.length * loadFactor;

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;
            }
            //设置新容量为旧容量的两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //阈值也变为原来的两倍
                newThr = oldThr << 1; // double threshold
        }
        /**
        * 从构造方法我们可以知道
        * 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
    	* 如果指定了initialCapacity, 该值被初始化成大于initialCapacity的最小的2的次幂
		* 这里这种情况指的是原table为空，并且在初始化的时候指定了容量，
		* 则用threshold作为table的实际大小
		*/
        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);
        }
        // 计算指定了initialCapacity情况下的新的 threshold
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;


    /**从以上操作我们知道, 初始化HashMap时, 
    *  如果构造函数没有指定initialCapacity, 则table大小为16
    *  如果构造函数指定了initialCapacity, 则table大小为threshold,
    *  即大于指定initialCapacity的最小的2的整数次幂
    
    *  从下面开始, 初始化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) {
                  /** 这里注意, table中存放的只是Node的引用,这里将oldTab[j]=null只是清除旧表的引用, 
                   * 但是真正的node节点还在, 只是现在由e指向它
                   */
                    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;
    }

重新规划长度

① 判断原来的table是否不为空，是的话判断: 如果原容量大于等于最大容量，那么将阈值设为 Integer 的最大值，并且 return 终止扩容，由于 size 不可能超过该值因此之后不会再发生扩容。如果 size 超出扩容阈值，把 table 容量增加为之前的2倍。否则 把 table 容量增加为之前的2倍。

② 判断oldThr>0, 如果是hashmap传入指定的initialCapacity，这个初始值会给到oldThr.

③ 否则的话 传入默认的容量和负载因子

重新排列数据节点

① 如果节点为 null 值则不进行处理。② 否则如果节点没有next节点，那么重新计算其散列值然后存入新的 table 数组中。③ 如果节点为 TreeNode 节点，那么调用 split 方法进行处理，该方法用于对红黑树调整，如果太小会退化回链表。④ 如果节点是链表节点，需要将链表拆分为 超出旧容量的链表和未超出容量的链表。对于hash & oldCap == 0 的部分不需要做处理，反之需要放到新的下标位置上，新下标 = 旧下标 + 旧容量。

假设原数组长度 capacity 为 16，扩容之后 new capacity 为 32：

capacity : 00010000
new capacity : 00100000

   old:
   10: 0000 1010
   15: 0000 1111
    &: 0000 1010    
    
   new:
   10: 0000 1010
   31: 0001 1111
    &: 0000 1010    

从上面的示例可以很轻易的看出, 两次indexFor()的差别只是第二次参与位于比第一次左边有一位从0变为1, 而这个变化的1刚好是oldCap, 那么只需要判断原key的hash这个位上是否为1: 若是1, 则需要移动至oldCap + i的槽位, 若为0, 则不需要移动;

对于一个 Key
它的哈希值如果在第 5 位上为 0，那么取模得到的结果和之前一样；
如果为 1，那么得到的结果为原来的结果 +16。

线程不安全：Java 7 扩容时 resize 方法调用的 transfer 方法中使用头插法迁移元素，多线程会导致 Entry 链表形成环形数据结构，Entry 节点的 next 永远不为空，引起死循环。Java 8 在 resize 方法中完成扩容，并且改用了尾插法，不会产生死循环的问题，但是在多线程的情况下还是可能会导致数据覆盖的问题，因此依旧线程不安全。

为啥Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null？

ConcurrentHashmap和Hashtable都是支持并发的，这样会有一个问题，当你通过get(k)获取对应的value时，如果获取到的是null时，你无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射。HashMap是非并发的，可以通过contains(key)来做这个判断。而支持并发的Map在调用m.contains（key）和m.get(key),m可能已经不同了

和HashTable的对比

1. 线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
2. 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
4. 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
5. 底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

fail-fast

fail-fast的字面意思是“快速失败”。在迭代器遍历元素的过程中，需要比较操作前后 modCount 是否改变，如果改变了说明集合结构被改变，需要抛出ConcurrentModificationException,防止继续遍历。

fail-safe

当我们对集合结构上做出改变的时候，fail-fast机制就会抛出异常。但是，对于采用fail-safe机制来说，就不会抛出异常(大家估计看到safe两个字就知道了)。

这是因为，当集合的结构被改变的时候，fail-safe机制会在复制原集合的一份数据出来，然后在复制的那份数据遍历。

因此，虽然fail-safe不会抛出异常，但存在以下缺点：

1.复制时需要额外的空间和时间上的开销。

2.不能保证遍历的是最新内容

死循环

resize方法

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    boolean oldAltHashing = useAltHashing;
    useAltHashing |= sun.misc.VM.isBooted() &&
            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean rehash = oldAltHashing ^ useAltHashing;//判断是否需要对原node重新hash定位table的index
    transfer(newTable, rehash); //扩容核心方法
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

JDK7的transfer

void transfer(Entry[] newTable, boolean rehash) {
    //新table的容量
    int newCapacity = newTable.length;
    //遍历原table
    for (Entry<K,V> e : table) {
        while(null != e) {
            //保存下一次循环的 Entry<K,V>
            Entry<K,V> next = e.next;
            if (rehash) {
                //通过e的key值计算e的hash值
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //得到e在新table中的插入位置
            int i = indexFor(e.hash, newCapacity);
            //采用链头插入法将e插入i位置，最后得到的链表相对于原table正好是头尾相反的
            e.next = newTable[i];
            newTable[i] = e;
            //下一次循环
            e = next;
        }
    }
}

扩容时 resize 调用 transfer 使用头插法迁移元素，每个线程都会生成newTable (newTable 是局部变量)，但原先 table 中的 Entry 链表是共享的.假设两个线程，线程1挂起，线程二执行迁移完成，此时线程1继续执行，本来是用e遍历table，用next保存下一个结点，但这样顺序就颠倒了。

JDK8 在 resize 方法中完成扩容，并改用尾插法，不会产生死循环，但并发下仍可能丢失数据。可用 ConcurrentHashMap 或 Collections.synchronizedMap 包装同步集合