[数据结构与算法]HashMap

HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。
容量 是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。
加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 rehash 方法将容量翻倍。

通常，默认加载因子 (.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地降低 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

HashMap的特点

1. HashMap中允许存放null键和null值
2. 线程不安全----------线程不同步
3. 与Hashtable相似
4. Hashset是HashMap的实例，HashMap的底层是HashTable哈希表

HashMap底层原理

1.基于Map接口实现 元素以键值对的方式存储
2.可以存储null键和null值 key不能够重复的 null只能有一个null键
3.HashMap不能够保证元素的顺序 无序的
4.线程不安全的

HashMap继承关系与实现接口

HashMap 继承 AbstractMap<K,V>
HashTable 继承 Dictionary
Map接口<K,V> entry<K,V>是Map接口的内部接口

相关属性

初始容量INITIAL_CAPACITY为1*2的4次方

 /**
                   * The default initial capacity - MUST be a power of two.
                   */
                  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量MAXIMUM_CAPACITY为1*2的30次方

 /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

加载因子LOAD_FACTOR为0.75f

/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

TREEIFY_THRESHOLD=8 指的是链表的长度大于8 的时候进行树化

/**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;
    

UNTREEIFY_THRESHOLD=6 说的是当元素被删除链表的长度小于6 的时候进行退化，由红黑树退化成链表

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

MIN_TREEIFY_CAPACITY=64 意思是数组中元素的个数必须大于等于64之后才能进行树化

 /**
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
     * between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

modCount

modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

阈值 threshold

threshold = (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)

它是加在因子乘以初始值大小，后续扩容的时候和数组大小一样，2倍进行扩容

HashMap.hashcode算法

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

HashMap的 hash计算方式：

key 的hashcode 进行了二次hash 为了能够得到更好的散列值

hash 方法的实现方式

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

JDK 1.8 中，是通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞

为什么要用异或运算符？

保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。

1.7版本 数组+链表
1.8 版本 数组+链表+红黑树 当阀值超过8的时候

Node

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;
    }

• Node是HashMap的一个静态内部类。实现了Map.Entry接口，本质是就是一个映射(键值对),主要包括
  hash、key、value 和 next 的属性。
• 我们使用 put 方法像其中加键值对的时候，就会转换成 Node 类型。其实就是newNode(hash, key, value,
  null);

TreeNode

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);
        }

当桶内链表到达 8 的时候，会将链表转换成红黑树，就是 TreeNode类型，它也是 HashMap中定义的静态内部类。

存储容器 table

定义如下

 /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

实际存储元素个数 size

size 默认大小是0 ，它指的是数组存储的元素个数，而不是整个hashmap 的元素个数，对于下面这张图就是3 而不是11

/**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

进入 putval()

进入putval 方法之后，整体数据流程如下，下面会详细介绍每一步

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)
    		// 当前位置为空，则直接插入，同时意味着不走else 最后直接返回null
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        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) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 可以看出只有当前key 的位置为空的时候才判断时候需要reszie 已经返回 null 其他情况下都走了else 的环节
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

判断数组是否为空,需不需要调用resize 方法
第一次调用，这里table 是null,所以会走resize 方法

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)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            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) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

所以第一次调用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;
        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 {               // 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;
        @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;
    }

table 为空首次初始化
如果是的话，初始化数组大小和threashold

newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

初始化之后，将新创建的数组返回，在返回之前完成了对变量table 的赋值

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
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;

最后完成table 的初始化，返回table

table = newTab;

判断当前位置是否有元素
1 .没有 直接放入当前位置

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)
tab[i] = newNode(hash, key, value, null);

2 .有将当前节点记做p
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;

当前节点记做p 然后进入else 循环

else {
    Node<K,V> e; K k;
    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) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
 }

判断直接覆盖(判断是否是同一个key)
判断新的key 和老的key 是否相同，这里同时要求了hash 值和 实际的值是相等的情况下然后直接完成了e=p 的赋值，其实也就是完成了替换，因为key 是相同的。
如果不是同一个key 的话这里就要将当前元素插入链表或者红黑树了，因为是不同的key 了

判断插入红黑树
如果当前元素是一个 TreeNode 则将当前元素放入红黑树，然后

else if (p instanceof TreeNode)

判断插入链表
如果不是同一key并且当前元素类型不是TreeNode 则将当前元素插入链表(因为key对应的位置已经有元素了，其实可以认为是链表的头元素)

可以看出采用的是尾插法，循环过程中当下一个节点是null的时候则进行插入，插入完毕之后判断是否需要树化

JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法

for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }

if ((e = p.next) == null) {
       p.next = newNode(hash, key, value, null);
       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
           treeifyBin(tab, hash);
       break;
   }

这段代码也是上图中的第一个if这段代码的意思就是在遍历链表的过程中，一直都没有遇到和待插入key 相同的key(第二个if) 然后当前要插入的元素插入到了链表的尾部(当前if 语句)

第二个if 的意思 如果有发生key冲突则停止 后续这个节点会被相同的key覆盖

2、插入之后判断判断局部变量binCount 时候大于7(TREEIFY_THRESHOLD-1),这里需要注意的是binCount 是从0开始的，所以实际的意思是判断链表的长度在插入新元素之前是否大于等于8，如果是的话则进行树化

3、并且这个时候变量e 的值是null ，因为是插入到链表的尾部的，所以这个时候key 是没有对应的oldValue 的，所以e是null 在最后面的判断返回中，也返回的是null

4、关于树化，首先这是发生在插入链表的时刻,并且是插入链表尾部的时候，因为判断过程是在第一个if 中，为了保证文章的结构关于树化放在下面讲

if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    break;
// 这个赋值很有意思，它完成了你可以使用for 循环完成链表遍历的核心功能    
p = e;

1、这一段代码的意思是在遍历的过程中(e=p.next)!=null 的的时候，也就是在循环链表的过程中，判断是否有和当前key 相等的key，相等的话e 就是要覆盖的元素，如果不相等的话就继续循环，知道找到这样的e 或者是将链表循环结束，然后将元素插入到链表的尾部(第一个if)
2、因为是当key 存在的时候则跳出循环，所以链表的长度没有发生变化，所以这里没有判断是否需要树化

最后 返回oldValue 完成新值替换
其实能走到这一步，是那就说明放入元素的时候，key 对应的位置是没有元素的，所以相当于数组中添加了一个新的元素，所以这里有判断是否需要resize 和返回空值。

++modCount;
 if (++size > threshold)
     resize();
 afterNodeInsertion(evict);
 return null;

resize 方法

选需要记住resize 方法是会返回扩容后的数组的
第一部分初始化新数组
这一部分不论是不是首次调用resize 方法，都会有的，但是数据迁移部分在首次调用的时候是没有的

Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 判断是oldCap 是否大于0 因为可能是首次resize，如果不是的话 oldCap
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;
//第一次调用resize 方法，然后使用默认值进行初始化
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;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

1. 如果数组的大小 大于等于MAXIMUM_CAPACITY之后，则 threshold = Integer.MAX_VALUE;
   然后不扩容直接返回当前数组，所以可以看出hashmap 的扩容上限就是MAXIMUM_CAPACITY(230)
2. 如果数组的大小 在扩容之后小于MAXIMUM_CAPACITY 并且原始大小大于DEFAULT_INITIAL_CAPACITY(16)
   则进行扩容(DEFAULT_INITIAL_CAPACITY的大小限制是为了防止该方法的调用是在树化方法里调用的，这个时候数组大大小可能小于DEFAULT_INITIAL_CAPACITY)
3. 新的数组创建好之后，就可以根据老的数组是否有值决定是否进行数据迁移

第二部分数据迁移
oldTab 也就是老的数组不为空的时候进行迁移

if (oldTab != null) {
 			// 遍历oldTable，拿到每一个元素准备放入大新的数组中去
      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;
                  }
              }
          }
      }
  }

1. 判断当前元素的next 是否为空，是则直接放入，其实就是只有一个元素，说明这是一个最正常的节点，不是桶内链表，也不是红黑树，这样的节点会重新计算索引位置，然后插入。
2. 是的话，判断是不是TreeNode,不是的话则直接遍历链表进行拷贝，保证链表的顺序不变。
3. 是的话则调用 TreeNode.split() 方法，如果是一颗红黑树，则使用 split方法处理，原理就是将红黑树拆分成两个 TreeNode 链表，然后判断每个链表的长度是否小于等于 6，如果是就将 TreeNode 转换成桶内链表，否则再转换成红黑树。
4. 完成数据的拷贝，返回新的数组

第三部分 返回新的数组

return newTab;

树化treeifyBin方法

for (int binCount = 0; ; ++binCount) {
     if ((e = p.next) == null) {
         p.next = newNode(hash, key, value, null);
         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
             treeifyBin(tab, hash);
         break;
     }
     if (e.hash == hash &&
         ((k = e.key) == key || (key != null && key.equals(k))))
         break;
     p = e;
 }

• 首先判断是符满足链表长度大于8(binCount 是否大于等于7)
  需要注意的是插入到链表的尾部导致链表的长度发生了变化的情况下，才判断是否需要树化
• 然后进入treeifyBin 方法中，进入树化方法之后又判断了,Hashmap 的大小是否大于64，如果不是的话，只是调用了resize
  方法，让数组扩容，而不是树化

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    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);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

获取元素的过程

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
 
/**
 * Implements Map.get and related methods.
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
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);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

总结

resize 方法总结
resize(扩容) 的上限
resize 不是无限的，当到达resize 的上限，也就是230 之后，不再扩容

resize 方法只有三种情况下调用

• 第一种 是在首次插入元素的时候完成数组的初始化
• 第二种 是在元素插入完成后判断是否需要数组扩容，如果是的话则调用
• 第三种 是在元素插入链表尾部之后，进入树化方法之后，如果不树化则进行resize

resize 的返回值

• 第一种情况下 返回老的数组也就是没有resize 因为已经达到resize 的上限了

• 第二种情况下 返回一个空的数组 也就是第一次调用resize方法

• 第三章情况下 返回一个扩容后的数组 完成了数据迁移后的数组

key 的判断

• 第一次判断是当前位置有元素的时候，如果两个key 相等则准备覆盖值

• 第二次判断是遍历链表的时候，决定能否覆盖链表中间key 相等的值而不是链表的尾部

为什么要用异或运算符？
保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。尽可能的减少碰撞。
链表法导致的链表过深问题为什么不用二叉查找树代替
之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了，造成很深的问题)，遍历查找会非常慢。

而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

jdk8中对HashMap做了哪些改变
在java 1.8中，如果链表的长度超过了8，那么链表将转换为红黑树。(桶的数量必须大于64，小于64的时候只会扩容)

发生hash碰撞时，java 1.7 会在链表的头部插入，而java 1.8会在链表的尾部插入

在java 1.8中，Entry被Node替代(换了一个马甲)

Hashmap 的容量大小为什么要求是2n
这里首选要说明一个前提，那就是元素在数组中的位置的计算方式是 tab[i = (n - 1) & hash] 也就是通过对数组大小求模得到的，因为我们知道hash 的计算方式是 hashCode() 的高 16 位异或低 16 位实现的，32 位值只要有一位发生改变，整个 hash() 返回值就会改变，也就是说我们的hash 值发生冲突的概率是比较小的，也就是说hash 值是比较随机的

所以更多的冲突是发生在取模的时候，所以这个时候只要保证了我们的取模运算 (n - 1) & hash，尽量能保证hash 值的特性也就是随机性。因为我们知道与运算的特点是,两位同时为“1”，结果才为“1”，否则为0

所以这个时候我们只要 (n - 1) 让的二进制表示都是一串1，例如"011111" 就可以了，因为安位与1 结果是不变的，也就是可以延续hash 值的散列性

其实到这里就差不多了，然后我们看2n 的表示特点，然后就知道为什么要就hashmap 的大小是 2n了, 2n次方的二进制表示大家肯定都很清楚，2的6次方，就是从右向左 6 个 0，然后第 7 位是 1

因为只有数组的长度是2的次方了，n-1 的二进制才能尽可能多的是1

参考来源请点击此处