HashMap常见面试题（超全面）：实现原理、扩容机制、链表何时升级为红黑树、死循环

//默认的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大数量，该数组最大值为2^30。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子。如果构造的时候不传则为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一个位置里存放的节点转化成树的阈值，也就是8，比如数组里有一个node，这个node链表的长度达到该值才会转化为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当一个反树化的阈值，当这个node长度减少到该值就会从树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//满足节点变成树的另一个条件，就是存放node的数组长度要达到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具体存放数据的数组！！！
transient Node<K,V>[] table;  //见下
//entrySet，一个存放k-v缓冲区
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少个键值对
transient int size;
//对map的修改次数
transient int modCount;
//The next size value at which to resize (capacity * load factor).
int threshold;
//加载因子
final float loadFactor;

//链表中的键值对对象
static class Node<K,V> implements Map.Entry<K,V> {
    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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

//红黑树中的键值对对象
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
    
    //...
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //当容量大于2^31就取最大值1<<31;
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //当前数组table的大小，一定是2的幂次方
    // tableSizeFor保证了数组一定是2的幂次方，是大于initialCapacity最接近的值。
    this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

//找到大于或等于 cap 的最小2的幂
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;
}

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) {
    //tab 局部变量，用来记录哈希表中数组的地址值（成员变量table放在堆中，方法放在栈中，如果一直调用table 需要反复去堆中获取，故定义tab）
    //p 临时的第三方变量，用来记录键值对对象的地址值；n 表示当前数组的长度；i 表示索引
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    	//resize()方法逻辑：
        //1.如果当前是第一次添加数据，底层会创建一个默认长度为16、加载因子为0.75的数组
        //2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件：如果没有达到扩容条件，底层不会做任何操作；如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
        n = (tab = resize()).length;
    // i = (n - 1) & hash  拿着数组长度与键的哈希值进行计算，得出当前键值对对象 在数组中应存入的位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        //通过hash找到下标，如果hash值指定的位置数据为空，则创建一个键值对对象，直接放到数组中
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果通过hash找到的位置有数据，发生碰撞
        Node<K,V> e; K k;
        //p.hash == hash 判断键是否一样
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果需要插入的key和当前hash值指定下标的key一样，先将p赋值给e
            e = p;
        else if (p instanceof TreeNode)
            //如果此时桶中数据类型为 treeNode，使用红黑树进行插入，调用putTreeVal方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //如果此时桶中数据类型为链表，遍历
            // 进行循环。注意e = p.next这个一直将下一节点赋值给e，直到尾部，注意开头是++binCount
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果链表中没有最新插入的节点，将新放入的数据放到链表的末尾
                    p.next = newNode(hash, key, value, null);
                    //判断当前链表长度是否超过8.如果超过8 就会调用treeifyBin方法
                    //treeifyBin方法的底层还会继续判断 数组的长度是否大于等于64，如果同时满足这两个条件 就会把这个链表转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果哈希值一样，就会调用equals方法比较内部的属性值是否相同。若都相同 跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e为null 表示当前不需要覆盖任何元素
        //如果e不为null，表明当前的键是一样的，值会被覆盖
        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);  //与LinkedHashMap有关
    //表示当前没有覆盖任何元素，返回null
    return null;
}

1.看源码之前需要了解的一些内容

Node<K,V>[] table   哈希表结构中数组的名字

DEFAULT_INITIAL_CAPACITY：   数组默认长度16

DEFAULT_LOAD_FACTOR：        默认加载因子0.75



HashMap里面每一个对象包含以下内容：
1.1 链表中的键值对对象
    包含：  
			int hash;         //键的哈希值
            final K key;      //键
            V value;          //值
            Node<K,V> next;   //下一个节点的地址值
			
			
1.2 红黑树中的键值对对象
	包含：
			int hash;         		//键的哈希值
            final K key;      		//键
            V value;         	 	//值
            TreeNode<K,V> parent;  	//父节点的地址值
			TreeNode<K,V> left;		//左子节点的地址值
			TreeNode<K,V> right;	//右子节点的地址值
			boolean red;			//节点的颜色
					


2.添加元素
HashMap<String,Integer> hm = new HashMap<>();
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);

添加元素的时候至少考虑三种情况：
2.1 数组位置为null，底层会创建一个键值对对象，直接放到数组当中
2.2 数组位置不为null，键不重复，挂在下面形成链表或者红黑树
2.3 数组位置不为null，键重复，元素覆盖


//参数一：键
//参数二：值

//返回值：被覆盖元素的值，如果没有覆盖，返回null
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


//利用键计算出对应的哈希值，再把哈希值进行一些额外的处理
//简单理解：返回值就是返回键的哈希值
static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^ ：按位异或
    // >>>:⽆符号右移，忽略符号位，空位都以0补⻬
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//参数一：键的哈希值
//参数二：键
//参数三：值
//参数四：如果键重复了是否保留
//		   true，表示老元素的值保留，不会覆盖
//		   false，表示老元素的值不保留，会进行覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
	//定义一个局部变量，用来记录哈希表中数组的地址值。
	Node<K,V>[] tab;
	
	//临时的第三方变量，用来记录键值对对象的地址值
	Node<K,V> p;
	
	//表示当前数组的长度
	int n;
	
	//表示索引
	int i;
	
	//把哈希表中数组的地址值，赋值给局部变量tab
	tab = table;

	if (tab == null || (n = tab.length) == 0){
		//1.如果当前是第一次添加数据，底层会创建一个默认长度为16，加载因子为0.75的数组
		//2.如果不是第一次添加数据，会看数组中的元素是否达到了扩容的条件
		//如果没有达到扩容条件，底层不会做任何操作
		//如果达到了扩容条件，底层会把数组扩容为原先的两倍，并把数据全部转移到新的哈希表中
		tab = resize();
		//表示把当前数组的长度赋值给n
		n = tab.length;
	}

	//拿着数组的长度跟键的哈希值进行计算，计算出当前键值对对象，在数组中应存入的位置
	i = (n - 1) & hash;//index
	//获取数组中对应元素的数据
	p = tab[i];
	
	
	if (p == null){
		//底层会创建一个键值对对象，直接放到数组当中
		tab[i] = newNode(hash, key, value, null);
	}else {
		Node<K,V> e;
		K k;
		
		//等号的左边：数组中键值对的哈希值
		//等号的右边：当前要添加键值对的哈希值
		//如果键不一样，此时返回false
		//如果键一样，返回true
		boolean b1 = p.hash == hash;
		
		if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
			e = p;
		} else if (p instanceof TreeNode){
			//判断数组中获取出来的键值对是不是红黑树中的节点
			//如果是，则调用方法putTreeVal，把当前的节点按照红黑树的规则添加到树当中。
			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);
					//判断当前链表长度是否超过8，如果超过8，就会调用方法treeifyBin
					//treeifyBin方法的底层还会继续判断
					//判断数组的长度是否大于等于64
					//如果同时满足这两个条件，就会把这个链表转成红黑树
					if (binCount >= TREEIFY_THRESHOLD - 1)
						treeifyBin(tab, hash);
					break;
				}
				//e：			  0x0044  ddd  444
				//要添加的元素： 0x0055   ddd   555
				//如果哈希值一样，就会调用equals方法比较内部的属性值是否相同
				if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
					 break;
				}

				p = e;
			}
		}
		
		//如果e为null，表示当前不需要覆盖任何元素
		//如果e不为null，表示当前的键是一样的，值会被覆盖
		//e:0x0044  ddd  555
		//要添加的元素： 0x0055   ddd   555
		if (e != null) {
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null){
				
				//等号的右边：当前要添加的值
				//等号的左边：0x0044的值
				e.value = value;
			}
			afterNodeAccess(e);
			return oldValue;
		}
	}
	
	//threshold：记录的就是数组的长度 * 0.75，哈希表的扩容时机  16 * 0.75 = 12
	if (++size > threshold){
		 resize();
	}
	
	//表示当前没有覆盖任何元素，返回null
	return null;
}	

n = (tab = resize()).length;  //table尚未初始化的时候，会调用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;
    
    //1.table已经初始化，且容量 > 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
    }
    //2.阈值大于0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //3.threshold 和 table 皆未初始化情况，此处即为首次进行初始化
    //也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题
    else {               // zero initial threshold signifies using defaults
        //如果阈值为零，表示使用默认的初始化值。这种情况在调用无参构造的时候会出现，此时使用默认的容量和阈值
        newCap = DEFAULT_INITIAL_CAPACITY;
        //此处阈值即为 threshold=initialCapacity*loadFactor
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // newThr 为 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;
    
    //如果之前的数组桶里面已经存在数据，由于table容量发生变化，hash值也会发生变化，需要重新计算下标
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果指定下标下有数据
            if ((e = oldTab[j]) != null) {
                //1）将指定下标数据置空
                oldTab[j] = null;
                //2）指定下标只有一个数据
                if (e.next == null)
                    //直接将数据存放到新计算的hash值下标下
                    newTab[e.hash & (newCap - 1)] = e;
                //3）如果是TreeNode数据结构
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //4）对于链表，数据结构
                else { // preserve order
                    //如果是链表，重新计算hash值，根据新的下标重新分组
                    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;
}

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) {
        //1）根据hash算法找到对应位置的第一个数据，如果是指定的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);
            //如果该节点是链表，则遍历查找到数据。当链表后续为null 退出循环
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

static final int hash(Object key) {
    int h;
    // key.hashCode()：返回散列值也就是hashcode
    // ^ ：按位异或
    // >>>:⽆符号右移，忽略符号位，空位都以0补⻬
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

first = tab[(n - 1) & hash])

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;
    //根据key和key的hash值，查找到对应的元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        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;
                } while ((e = e.next) != null);
            }
        }
        
        //如果查找到了元素node，移除即可
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //如果是TreeNode，通过树进行移除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //如果是第一个节点，移除第一个节点，将index下标的位置指向第二个节点
            else if (node == p)
                tab[index] = node.next;
            else
                //如果不是链表的第一个节点，则移除该节点
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

final Node<K,V>[] resize() {
    //扩容前原本的table
    Node<K,V>[] oldTab = table;
    //这里进行判断，区分尚未初始化的情况
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {   //非初始化情况
        /*
         * 当原本的capacity已经超过最大值以后
         * HashMap选择不再扩容，然后threshold置为最大值
         */
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        /*
         * 这种是常见的的扩容情况，table容量会扩大两倍
         * 同时HashMap的阈值也跟着扩大两倍
         */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold，2倍阈值
    }
    else if (oldThr > 0) // 指定大小n的初始化情况下，table容量取>n的最小2倍数。initial capacity was placed in threshold
        newCap = oldThr;
    // 不指定初始化大小，table容量取默认值16
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        // 指定大小初始化情况下，阈值 = table容量 * 负载因子(默认0.75)
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //确定新阈值。原来默认是12，现在变为24
    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) {
            // 遍历原本的table
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  //为了GC
                if (e.next == null)
                    // 如果table上没有链表的情况下，直接转移到对应位置
                    // 转移到的位置就是get方法中取的下标位置，tab[(n - 1) & hash]
                    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;
                        //如果entry的哈希值高位为0，会被拆分到lo链表
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                             //如果entry的哈希值高位为1，会被拆分到hi链表
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        // 高位是0，因此lo链表不需要移位，
                        // hash & (newCap-1)和hash & (oldCap-1)获得下标位置一样
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 高位是1，hi链表移位到 j+oldCap位置，
                        //  j + oldCap相当于高位补1，直接移到这个位置
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //...
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //...
}

int index  =(n - 1) & hash;
	 	   = (16 - 1) & xxxx 1011
	 	   = 15  & xxxx 1011
	 	   = 1111 & xxxx 1011
	 	   = 1011
	 	   = 11

int index  =(n - 1) & hash;
	 	   = (32 - 1) & xxxx 1011
	 	   = 31  & xxxx 1011
	 	   = 1 1111 & xxxx 1011

11011 = 1011 + 1 0000 ;
新下标 = 旧下标 + 旧容量;

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {   //确保value不为null
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();    //如果key为null，此处会报空指针异常
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

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

static final int hash(Object key) {
    int h;
    //当key为null的时候，不走hashCode()方法，直接返回0
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

public class MapNull {
    public static void main(String[] args) {
        Map<Object, Object> map1 = new HashMap<>();
        map1.put("name", "wj");
        map1.put("study", null);
        map1.put(null, "unknown");
        map1.put(null, null);
        System.out.println(map1);
    }
}

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

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // 在此处直接过滤掉key或value为null的情况
    if (key == null || value == null) throw new NullPointerException();
    // 另外其hash值采用了二次hash，使得hash值分布更均匀
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}