HashMap集合详解

HashMap 底层数据结构

• JDK1.7 及之前：数组 + 链表
• JDK1.8：数组 + 链表 + 红黑树

HashMap 添加元素分析

hash 算法：当添加元素时，会通过 哈希值 和 数组长度 计算下标来准确定位该元素应该 put 的位置，通常我们为了使元素时分布均匀会使用取模运算，用一个值去模上总长度，例如：index = hash % arr.length（实际采用的与运算 hash & (length-1) 取代取模运算hash % length，因为这两种方式记算出来的结果是一致的，也就是hash & (length-1) = hash % length），计算这个索引位置的算法就是 hash 算法

计算出 index 后，就会将该元素添加进去，理想状态下是将每个值都均匀的添加到数组中，但问题是不可能达到这样的理想状态，如果某个元素通过计算产生的索引位置已经有其他元素了，这时候就会产生哈希冲突，此时，就产生了第二种数据结构——链表，冲突的元素会在该索引处以链表的形式保存

但是当链表的长度过长时，其固有弊端就显现出来了，即查询效率较低，时间复杂度可能会达到 O(n) 级别，而数组的查询时间复杂度仅为 O(1)

此时，就引出了第三种数据结构——红黑树，红黑树是一棵接近于平衡的二叉树，其查询时间复杂度为 O(logn)，远远比链表的查询效率高。但如果链表长度不到一定的阈值，直接使用红黑树代替链表也是不行的，因为红黑树的自身维护的代价也是比较高的，每插入一个元素都可能打破红黑树的平衡性，这就需要每时每刻对红黑树再平衡（左旋、右旋、重新着色）

jdk1.8 以前 HashMap 的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n) ，完全失去了它的优势。

针对这种情况，jdk1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。

HashMap 继承关系

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

说明

Cloneable 空接口，表示可以克隆。创建并返回 HashMap 对象的一个副本

Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化

AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作

HashMap 的主要属性

// 序列化版本号
private static final long serialVersionUID = 362498820763181265L;

// 默认Hash表的大小:16（必须是 2 的 n 次幂）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// Hash表最大大小
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子
// 加载因子是表示Hsah表中元素的填满的程度
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 链表转换为红黑树条件：链表长度阈值为8，和hash表的阈值为64
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

// 红黑树转化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 存储元素的数组：散列数组
 * 其中 table 就是 HashMap 中的数组
 * table 用来初始化（必须是二的n次幂）
 * jdk8 之前数组类型是 Entry<K,V> 类型
 * jdk1.8 之后是 Node<K,V> 类型
 * 只是换了个名字，都实现了一样的接口：Map.Entry<K,V>：负责存储键值对数据的
 */
transient Node<K,V>[] table;

// 存放具体元素的集合
transient Set<Map.Entry<K,V>> entrySet;

// HashMap 中存放元素的个数
transient int size;

// 每次扩容和更改(put) map 结构的计数器
// 用来记录 HashMap 的修改次数
transient int modCount;

// 扩容阈值（数组容量*加载因子） 当哈希表中的元素超过阈值时，触发扩容
int threshold;

// 哈希表的加载因子
final float loadFactor;

构造方法

构造一个空的 HashMap，默认初始容量（16）和默认负载因子（0.75）

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

构造一个具有指定的初始容量和默认负载因子（0.75）HashMap 。

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

构造一个具有指定的初始容量和负载因子的 HashMap。

/**
 * @param  initialCapacity 指定的容量
 * @param  loadFactor      指定的负载因子
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 判断初始化容量initialCapacity是否小于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);

    // 判断初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;

    // 判断负载因子loadFactor是否小于等于0或者是否是一个非数值
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 返回比指定初始化容量大的 最小的2的n次幂,最小返回16
 */
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;
}

调用 putMapEntries() 方法将目标 Map 拷贝到当前 Map

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

/**
 * Implements Map.putAll and Map constructor.
 *
 * @param m the map
 * @param evict false when initially constructing this map, else
 * true (relayed to method afterNodeInsertion).
 */
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 获取传入的数组长度
    // 比如oldMap使用的无参构造器
    // 因此容量是16，装载因子是0.75，阈值是12，s=16
    int s = m.size();
    if (s > 0) {
        // 判断table是否已经初始化
        if (table == null) { // pre-size
            // 未初始化，元素数量/加载因子 + 1
            float ft = ((float)s / loadFactor) + 1.0F;
            // 计算得到t值，确定哈希表长度
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 计算得到的t如果大于扩容阈值，则初始化阈值
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 已初始化，并且m元素个数大于阈值，进行扩容处理
        else if (s > threshold)
            resize();

        // 遍历，将m中的所有元素添加至HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

关于 float ft = ((float)s / loadFactor) + 1.0F;

• oldMap 使用的无参构造器（会使用到 HashMap 的默认值），因此容量是 16，装载因子是 0.75，阈值是 12。而 newMap 使用的拷贝构造器，而后会调用 putMapEntries ，因为传入 map 的 size 是 12，那么 12 / 0.75=16, 16 + 1 = 17, tableSizeFor(17) = 32，因此最终形成 newMap 的容量是 32，阈值是 24。
• 坏处：newMap 的 size 明明和 oldMap 的 size 同样，可是其容量和阈值都是 oldMap 的二倍了（变成了原有的二倍）。
• 可能你会想，这是为了保护另外一种特例，这种特例若是不作加 1 操做，就会致使分配的容量不够大，因此我这种特例就得牺牲一下了。但你就算把 s 的值（传入 map 的 size）从 6 试到 12，也会发现，就算不作加 1 操做，分配的容量也会够大。
• 其实咱们忽略了一点，就是 loadfactor 可能会被用户给一个奇怪的小数，由于在 HashMap 里，容量必须为 2 的 n 次幂，且默认的 loadfactor 又是 0.75，因此算出来的阈值确定是整数了。若是用户给一个小数，使得 capacity * loadfactor = 小数，那么这个阈值必须向下取整（反过来想，若是阈值向上取整，那岂不是使得 size 可能会大于了真正的 threshold 而不用 resize，详见resize()函数的newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);，这里的(int)ft就是向下取整）。因此反过来想，用 size / loadfactor 算出的 capacity，确定也要向上取整了。

成员方法

增加方法 put()

put 方法是比较复杂的，实现步骤大致如下：

• 先通过 hash 值计算出 key 映射到哪个桶；

• 如果桶上没有碰撞冲突，则直接插入；

• 如果出现碰撞冲突了，则需要处理冲突：

  • 如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；
  • 否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；

• 如果桶中存在重复的键，则为该键替换新值 value；

• 如果 size 大于阈值 threshold，则进行扩容；

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

 static final int hash(Object key) {
     int h;
     // HashMap 是支持 key 为空的
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

/**
 * putVal 方法只是给 put 方法调用的一个方法，并没有提供给用户使用
 */
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
     // Node<K,V>[] tab：表示存储Map集合中元素的数组
     Node<K,V>[] tab; Node<K,V> p; int n, i;
     // (tab = table) == null 表示将空的table赋值给tab，然后判断tab是否等于null，第一次肯定是null
     // (n = tab.length) == 0 表示将数组的长度赋值给n，然后判断n是否等于0
     if ((tab = table) == null || (n = tab.length) == 0)
         // 满足一个条件， 进行数组初始化，并将初始化好的数组长度赋值给n
         n = (tab = resize()).length;
     // 计算数组的索引，获取计算出的索引位置的数据赋值给结点p
     if ((p = tab[i = (n - 1) & hash]) == null)
         // 如果当前桶没有哈希碰撞冲突，根据键值对创建新的结点放入该位置的桶中
         tab[i] = newNode(hash, key, value, null);
     else {
         // 执行else说明tab[i]不等于null，表示这个位置已经有值了
         Node<K,V> e; K k;
     /**
      * 比较桶中第一个元素(数组中的结点)的hash值和key是否相等
      *
      * 1）p.hash == hash  p.hash表示原来存在数据的hash值
      * hash表示后添加数据的hash值 比较两个hash值是否相等
      *   说明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node对象
      *   而在Node类中具有成员变量hash用来记录着之前数据的hash值的
      *
      * 2）(k = p.key) == key  p.key获取原来数据的key赋值给k
      * key 表示后添加数据的key比较两个key的地址值是否相等
      *
      * 3）key != null && key.equals(k)：能够执行到这里说明两个key的地址值不相等
      * 那么先判断后添加的key是否等于null,如果不等于null再调用equals方法判断两个key的内容是否相等。
      */
         if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             // 两个元素哈希值相等，并且key的值也相等，将旧的元素整体对象赋值给e，用e来记录
             e = p;
         // hash值不相等或者key不相等；判断p是否为红黑树结点
         else if (p instanceof TreeNode)
             // 放入树中
             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         // 说明是链表结点
         else {
             // 如果是链表的话需要遍历到最后结点然后插入
             // 采用循环遍历的方式，判断链表中是否有重复的key
             for (int binCount = 0; ; ++binCount) {
                 // 获取p的下一个元素赋值给e
                 // 等于null，说明p没有下一个元素，那么此时到达了链表的尾部
                 if ((e = p.next) == null) {
                     // 没有找到重复的key,则说明HashMap没有包含该键，创建一个新的结点插入到尾部
                     // 注意第四个参数next是null，因为当前元素插入到链表末尾了，那么下一个结点肯定是null
                     // 这种添加方式也满足链表数据结构的特点，每次向后添加新的元素
                     p.next = newNode(hash, key, value, null);
                     // 判断此时结点个数是否大于TREEIFY_THRESHOLD临界值8，满足条件则将链表转换为红黑树
                     // 注意binCount是从0开始计数，值表示节点的个数，值为7表示8个节点
                     // 但是上一步还执行了p.next = newNode(hash, key, value, null);
                     // 所以此时binCount=7，但是一共有9个节点
                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                         // 转换为红黑树
                         treeifyBin(tab, hash);
                     break;
                 }
                 // 执行到这里说明不是最后一个元素
                 // 继续判断链表中结点的key值与插入的元素的key值是否相等
                 if (e.hash == hash &&
                     ((k = e.key) == key || (key != null && key.equals(k))))
                     // 要添加的元素和链表中的存在的元素的key相等，则跳出for循环
                     // 直接执行下面的if语句去替换新值 if (e != null)
                     break;
                 // 与前面的e = p.next组合，实现链表遍历
                 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()

下图为 16 扩充为 32 的 resize 示意图

final Node<K,V>[] resize() {
    // oldTab：扩容前的哈希表
    Node<K,V>[] oldTab = table;
    // oldCa：扩容前的table数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //oldThr：扩容前的扩容阈值，触发本次扩容的阈值
    int oldThr = threshold;
    // newCap：新的散列表的
    // newThr：扩容之后，下次再次触发扩容的条件
    int newCap, newThr = 0;
    // 已经初始化过了，不是第一次扩容，
    if (oldCap > 0) {
        // oldCap已经达到了最大值 则不扩容，且设置扩容条件为 int 最大值。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // newCap等于oldCap数组翻倍  newCap 小于数组最大值限制 且扩容之前的阈值 >= 16
        // 这种情况下，则下一次扩容的阈值 等于当前阈值翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // oldCap == 0,说明hashMap中的散列表是null
    // 构造函数指定过oldThr
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // oldCap=0 oldThr=0
    // 调用的new HashMap();
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // newThr为零时，通过newCap和loadFactor计算出一个newThr
    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;
    // hashMap本次扩容之前，table不为null
    if (oldTab != null) {
        // 把每个bucket都移动到新的buckets中
        // 遍历旧的哈希表的每个桶，重新计算桶里元素的新位置
        for (int j = 0; j < oldCap; ++j) {
            // e 当前Node节点
            Node<K,V> e;
            // 如果桶的当前位置不为空
            if ((e = oldTab[j]) != null) {
                // 原来的数据赋值为null 便于GC回收
                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;
                        // 这里来判断如果等于true e这个结点在resize之后不需要移动位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        // 低位链表，当前位置
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        // 高位链表 当前位置+扩容前的链表的值
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

删除方法 remove()

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;
    // 根据hash找到位置
 // 如果当前key映射到的桶不为空
    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;
        // 如果桶上的结点就是要找的key，则将node指向该结点
        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 {
                // 判断是否以链表方式处理hash冲突，是的话则通过遍历链表来寻找要删除的结点
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 比较找到的key的value和要删除的是否匹配
        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;
}

查找方法 get()

public V get(Object key) {
   // tab当前的哈希表
   // n哈希表的长度
   // first 桶位中的头元素 e：临时node元素
    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;
    // 如果哈希表不为空并且key对应的桶上不为空
    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) {
            // 判断是否是红黑树，是的话调用红黑树中的getTreeNode方法获取结点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 不是红黑树的话，那就是链表结构了，通过循环的方法判断链表中是否存在该key
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

总结

1、hash 函数

hash 函数，即散列函数，或叫哈希函数。它可以将不定长的输入，通过散列算法转换成一个定长的输出，这个输出就是散列值。需要注意的是，不同的输入通过散列函数，也可能会得到同一个散列值。因此我们不能使用散列函数来获取唯一值。

2、HashMap 为什么要使用 hash 函数

Java 的 HashMap 中使用的是数组 + 链表的结构，但在保存时，一个 K - V 键值对如果按照存入顺序存放。那么在取值时需要遍历整个数组，然后一个个去比较它们的 key 是否相等，这对于性能的损耗无疑是很大的。所以通过 hash 函数来优化。

3、HashMap 中 hash 函数是怎么实现的？还有哪些 hash 函数的实现方式？

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

对于 key 的 hashCode 做 hash 操作：无符号右移 16 位然后做异或运算。

无符号右移 16 位然后做异或运算的目的？

如果当 n 即数组长度很小，假设是 16 的话，那么 n - 1 即为 1111 ，这样的值和 hash 直接做按位与操作，实际上只使用了哈希值的后 4 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题

除此以外还有平方取中法，伪随机数法和取余数法。这三种效率都比较低。而无符号右移 16 位 异或运算（^）效率是最高的

按位异或运算（^）：相同的二进制数位上，都是 1 的时候，结果为 1，否则为 0

4、hash 算法【确定数组索引 index】

通过 hash() 方法得到 hash 函数后，返回的是一个返回 int 类型的散列值，如果直接拿散列值作为下标访问 HashMap 主数组的话，考虑到 2 进制 32 位带符号的 int 表值范围从 -2147483648 到 2147483648 ，前后加起来大概 42 亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组索引 index。

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的值是table.length
        n = (tab = resize()).length;
    // 索引index的确定：(n - 1) & hash
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 当查找不到对应的索引时，就会新建一个新的结点作为链表的头结点
        tab[i] = newNode(hash, key, value, null);

就是将 散列值 和 数组长度-1 进行与运算

按位与运算（&）：相同的二进制数位上，都是 1 的时候，结果为 1，否则为 0

5、为什么要用 i = (n - 1) & hash 作为索引运算呢？

这其实是一种优化手段，由于数组的大小永远是一个 2 次幂，在扩容之后，一个元素的新索引要么是在原位置，要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算，&运算只会关注 n – 1（n =数组长度）的有效位

当扩容之后，n 的有效位相比之前会多增加一位（n 会变成之前的二倍，所以确保数组长度永远是 2 次幂很重要），然后只需要判断 hash 在新增的有效位的位置是 0 还是 1 就可以算出新的索引位置，如果是 0，那么索引没有发生变化，如果是 1，索引就为原索引加上扩容前的容量。

通过位运算，在每次扩容时都不用重新计算 hash，省去了不少时间，而且新增有效位是 0 还是 1 是带有随机性的，之前两个碰撞的 Entry 又有可能在扩容时再次均匀地散布开，达到较好的分布离散效果。

举个例子，数组长度为 16，经过扩容后变为 32

0001 1111 —>31

和上面图中的 hash 进行与运算

0001 0101

结果为 21，即索引为原索引 5 加上扩容前的容量 16=21

0001 0101

5、HashMap 为什么数组的大小是 2 的指数次幂，如果输入值不是 2 的幂比如 10 会怎么样?

为了提高效率，方便&运算

根据一开始提到的，hash 算法实际就是取模操作：hash % length，因为计算机中直接求余效率不如位移运算

计算机的运行效率：加法(减法)>乘法>除法>取模，取模的效率是最低的。所以我们要在 HashMap 中避免频繁的取模运算，又因为在我们 HashMap 中他要通过取模去定位我们的索引，并且 HashMap 是在不停的扩容，数组一旦达到容量的阈值的时候就需要对数组进行扩容。那么扩容就意味着要进行数组的移动，数组一旦移动，每移动一次就要重回记算索引，这个过程中牵扯大量元素的迁移，就会大大影响效率。那么如果说我们直接使用与运算，这个效率是远远高于取模运算的

所以源码中做了优化，使用 hash & (length - 1)

而上面提到过 hash % length 等于 hash & ( length - 1) ，前提是 length 是 2 的 n 次幂

怎么确保数组大小一定是 2 的指数次幂

HashMap 构造方法可以指定集合的初始化容量大小（默认 16）

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

而在实例化 HashMap 实例时，如果给定了 initialCapacity

下面这个方法用于找到 大于等于 initialCapacity 的最小的 2 的幂

/**
 * Returns a power of two size for the given target capacity.
 */
// cap为传入的数组初始化容量
static final int tableSizeFor(int cap) {
   /*
    * 如果 cap 已经是2的指数次幂，又没有这个减 1 操作
    * 则执行完后面的几条无符号操作之后，返回的 capacity 将是这个 cap 的 2 倍
    */
    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;
}

_|=_： a|=b 就等于 a = a | b，按位或。两个二进制对应位都为 0 时，结果等于 0，否则结果等于 1

完整例子

比如输入的 cap 值为 10，最后得到的结果为 16

6、当两个对象的 hashCode 相等时会怎么样？

会产生哈希碰撞。若 key 值内容相同则替换旧的 value，不然连接到链表后面，链表长度超过阈值 8 就转换为红黑树存储。

7、什么是哈希碰撞，如何解决哈希碰撞？

只要两个元素的 key 计算的哈希码值相同就会发生哈希碰撞。jdk8 之前使用链表解决哈希碰撞。jdk8 之后使用链表 + 红黑树解决哈希碰撞。

8、如果两个键的 hashCode 相同，如何存储键值对？

通过 equals 比较内容是否相同。相同：则新的 value 覆盖之前的 value。不相同：则将新的键值对添加到哈希表中。

9、为什么选择红黑树而不用其他树，比如二叉查找树

二叉查找树在特殊情况下也会变成一条线性结构，和原先的链表存在一样的深度遍历问题，查找性能就会慢

使用红黑树主要是提升查找数据的速度，红黑树是平衡二叉树的一种，插入新数据后会通过左旋，右旋、变色等操作来保持平衡，解决单链表查询深度的问题

10、为什么不一直开始就用红黑树

数据量少的时候操作数据，遍历线性表比红黑树所消耗的资源少，且前期数据少。平衡二叉树保持平衡是需要消耗资源的，所以前期采用线性表，等到一定数之后变换到红黑树

这其实是基于空间和时间平衡的考虑，JDK 的源码里已经对这个问题做了解释：

/*
 * Because TreeNodes are about twice the size of regular nodes, we
 * use them only when bins contain enough nodes to warrant use
 * (see TREEIFY_THRESHOLD). And when they become too small (due to
 * removal or resizing) they are converted back to plain bins.
 */

单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，这个足够多的标准就是由 TREEIFY_THRESHOLD 的值（默认值 8）决定的。而当桶中节点数由于移除或者 resize (扩容) 变少后，红黑树会转变为普通的链表，这个阈值是 UNTREEIFY_THRESHOLD（默认值 6）。

11、为什么树化标准是 8 个

在源码中，上面那段笔记后面还有一段较长的注释，我们可以从那一段注释中找到答案，原文是这样：

/*
 * In usages with well-distributed user hashCodes, tree bins are
 * rarely used.  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
 */

大概意思就是：如果 hashCode 的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，注释中给我们展示了 1-8 长度的具体命中概率，当长度为 8 的时候，概率概率仅为 0.00000006，这么小的概率，HashMap 的红黑树转换几乎不会发生，因为我们日常使用不会存储那么多的数据，当然，这是理想的算法，如果用户重写了hashCode，并且算法实现比较差的话，就很可能会使 hashCode 分布离散很差，这个时候再转换为红黑树就是一种很好的退让策略。

总结

一方面遵循泊松分布，链表中元素个数为 8 时的概率已经非常小

另一方面红黑树查找时间复杂度是 log(n)，长度为 8 的时候，平均查找长度大约为 2.83（取 3），如果继续使用链表（链表的平均查找长度为 n/2），平均查找长度为 8/2=4，这才有转换为树的必要。链表长度如果是小于等于 6，6/2=3，，而 log(6) = 2.6，虽然速度也很快的，但是链表和红黑树之间的转换也很耗时

12、为什么退化为链表的阈值是 6

上面说到，当链表长度达到阈值 8 的时候会转为红黑树，但是红黑树退化为链表的阈值却是 6，为什么不是小于 8 就退化呢？比如说 7 的时候就退化，偏偏要小于或等于 6？

主要是一个过渡，避免链表和红黑树之间频繁的转换。如果阈值是 7 的话，删除一个元素红黑树就必须退化为链表，增加一个元素就必须树化，来回不断的转换结构无疑会降低性能，所以阈值才不设置的那么临界。

13、为什么 HashMap 的加载因子要设置为 0.75

加载因子如果定的太大，比如 1，这就意味着数组的每个空位都需要填满，如果一直等数组填满才扩容，虽然达到了最大的数组空间利用率，但会产生大量的哈希碰撞，同时产生更多的链表，显然不符合我们的需求。

但如果设置的过小，比如 0.5，这样一来保证了数组空间很充足，减少了哈希碰撞，这种情况下查询效率很高，但消耗了大量空间。

因此，我们就需要在时间和空间上做一个折中，选择最合适的负载因子以保证最优化，取到了 0.75

当 HashMap 里面容纳的元素已经达到 HashMap 数组长度的 75% 时，表示 HashMap 太挤了，需要扩容，而扩容这个过程涉及到 rehash、复制数据等操作，非常消耗性能。所以开发中尽量减少扩容的次数，可以通过创建 HashMap 集合对象时指定初始容量来减少扩容。