HashMap简介

HashMap基于哈希表的Map接口实现，是以key-value存储形式存在，即主要用来存放键值对。HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

JDK8之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突（两个对象调用的hashCode()方法计算的哈希码值一致导致计算的数组索引值相同）。JDK8之后，当链表长度大于阈值（或者红黑树的边界值，默认为 8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。

补充：将链表转换成红黑树前会判断，即使阈值大于8，但是数组长度小于64，此时并不会将链表变为红黑树。而是选择进行数组扩容。

当然虽然增了红黑树作为底层数据结构，结构变得复杂了，但是阈值大于8并且数组长度大于等于64时，链表转换为红黑树时，效率也变的相对更高效。

特点小结：

存取无序的。
键和值位置都可以是null，但是键位置只能是一个null。
键位置是唯一的，底层的数据结构控制键的位置。
JDK8前数据结构是：链表 + 数组，JDK8之后是：链表 + 数组 + 红黑树。
链表长度阈值（边界值） > 8 并且数组长度大于等于64，才将链表转换为红黑树，变为红黑树的目的是为了高效的查询。

HashMap底层的数据结构

数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。说白了就是存储数据的一种方式。

在JDK1.8 之前 HashMap 由数组+链表数据结构组成的。

在JDK1.8 之后 HashMap 由数组+链表 +红黑树数据结构组成的。

HashMap底层数据结构存储数据的过程

存储规则

1、创建HashMap对象后，在JDK8之前，底层是创建了一个长度是16的Entry[] table，但是在JDK8之后，并没有在创建集合对象的时候创建数组，而是在首次调用put()方法时，底层创建长度为16的Node[] table数组。

2、假设向哈希表中存储数据“Mary-18”，根据 Mary 调用String类中的 hashCode() 方法计算出哈希码值，此哈希码经过某种算法计算以后，得到在Node数组中存放的位置，如果此位置上数据为空，就直接添加到该位置。

3、假设向哈希表中存储了”Tom-18”，根据 Tom 计算的哈希码结合数组长度计算出Node数组的索引是2，此时，该位置已经有了 Mary ，那么此时位置不为空，比对二者的hash值，如果哈希值不相同，那么 Tom 会在此空间划出一个节点变为链表来存储。

4、假设此时向哈希表中又存储了一个“Jack-29”，根据key计算出的哈希值结合数组计算出的索引是2，那么此时该位置已经有了数据，就比较后添加的数据的key和已存在的哈希值是否相同，如果相同，继续比较；调用后添加的 Jack 所在类的 equals() 方法，比较内容是否相等。如果返回false，就作为链表节点继续添加；如果返回true，则后添加的“Jack-29”，替换之前的”Tom-18”。

JDK8中HashMap存储流程

说明：

size表示 HashMap中K-V的实时数量，注意这个不等于数组的长度。
threshold（临界值）= capacity（容量）* loadFactor（加载因子 0.75）。这个值是当前已占用数组长度的最大值。size超过这个临界值就重新 resize（扩容），扩容后的 HashMap 容量是之前容量的两倍。在我们实际开发中，如果对效率要求很高，应当尽可能避免HashMap的扩容。

HashMap继承关系

HashMap继承关系如下图所示：

说明：

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

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

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

补充：通过上述继承关系我们发现一个很奇怪的现象，就是HashMap已经继承了AbstractMap而AbstractMap类实现了Map接口，那为什么HashMap还要在实现Map接口呢？同样在ArrayList中LinkedList中都是这种结构。

据 Java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在Java集合框架中，类似这样的写法很多，最开始写Java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

HashMap类的成员

成员变量

集合的初始化容量

//默认的初始容量 = 1<<4 = 16。HashMap的容量必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

问题：为什么必须是2的n次幂？如果输入值不是2的幂，比如10会怎么样？

HashMap构造方法还可以指定集合的初始化容量大小：

//
指定容量去初始化一个HashMap
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

当向HashMap中添加一个元素的时候，需要根据key的hash值，去确定其在数组中的具体位置。 HashMap 为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法。

这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，所以源码中做了优化，使用 hash&(length-1)，而实际上 hash%length 等于 hash&(length-1) 的前提是length是2的n次幂。

为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；举例：

如果不考虑效率，直接求余数的话，就不需要要求长度是2的n次幂。

小结：

由上面可以看出，当我们根据key的hash确定其在数组的位置时，如果数组长度为2的n次幂，就可以保证数据的均匀插入。如果不是2的n次幂，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大了hash碰撞。
另一方面，一般我们可能会想通过 % 求余数来确定位置，这样做其实也是可以的，但是性能不如 & 位与运算。而且当数组长度是2的n次幂时，hash & (length - 1)==hash % length因此，HashMap容量是2的n次幂，是为了数据的均匀分布，减少Hash冲突。Hash冲突越大，代表数组中一个链表就越长，这样会降低HashMap的性能。

如果在创建HashMap对象的时候，指定的容量不是2的n次幂，比如10，HashMap会通过一系列位移运算和或运算得到一个2的n次幂，这个数字是离我们指定容量最近的数字。

源码：

/**
 * 用指定的容量和负载因子初始化一个HashMap
 * @param initialCapacity 初始值
 * @param loadFactor      负载因子
 * @throws IllegalArgumentException 如果初始容量为负
或负载系数是非正的
 */
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);
}

//
该方法作用是让HashMap的容量永远是2的n次幂
// | （位或运算符）运算规则：两个数都转为二进制，然后从高位开始比较，两个数只要有一个为1则为1，否则就为0。
/*
>>> 表示符号位也会跟着移动，比如 -1 的最高位是1，表示是个负数，然后右移之后，
最高位就是0表示当前是个正数。
所以-1 >>>1 = 2147483647
>> 表示无符号右移，也就是符号位不变。那么-1 无论移动多少次都是-1
原理就是将最高位 1 右边的所有比特位全置为 1，然后再加 1，最高位进 1，右边的比特位全变成 0，从而得出一个 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;
}

说明：由此可以看到，当在实例化HashMap的时候，如果给定了initialCapacity（假设是10），由于HashMap的initialCapacity必须都是2的n次幂，因此这个方法用于找到大于等于initialCapacity的最小的是2的n次幂。如果initialCapacity已经是2的n次幂，则直接返回这个数。

分析这个算法：

首先，为什么要进行cap - 1 的操作。int n = cap - 1，这是为了防止cap已经是2的n次幂。如果cap已经是2的n次幂，又没有执行减1的操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个数的2倍。
如果这时候n是0，最后返回的是capacity是1，因为最后有个n+1的操作。
按位或 | 运算规则：相同位置的二进制数位上，如果都是0，那么结果就是0，否则为1。

默认的负载因子，默认值是0.75

/**
* 默认负载因子=0.75。与扩容有关。
* 当HashMap中元素的个数 >= 数组长度 * 负载因子
* 就会扩容数组
* 负载因子在使用的过程中，不建议改变
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

使用TreeNode的临界值

/**
* 使用TreeNode的临界值，默认=8
* 经过大量的计算得知，链表中元素符合泊松分布
* 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
* 上面是链表中，每个节点可能会存放元素的概率
* 网上还有另一种说法，红黑树的平均查找长度是log(n)，如果长度为8，平均查找长度是log(8) = 3
* 链表平均查找长度是 n/2，如果长度是8的情况下，8/2=4，效率低于红黑树，所以需要转换为红黑树。
* 如果链表长度小于等于6， 6/2=3.而log(6) ≈ 2.6，虽然比链表快，但是效率差距并不大
* 而且，链表转换为红黑树也需要一定的时间，所以这时候并不会转换为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;

集合最大容量

//最大容量 = 1<<30  2^30 二进制表示就是第31位是1，后面全都是0
static final int MAXIMUM_CAPACITY = 1 << 30;

当链表的值小于6则会从红黑树转回链表

//链表值小于6会从红黑树转回链表
static final int UNTREEIFY_THRESHOLD = 6;

当Map里面的数量超过这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化

//当数组长度大于这个数时才会转红黑树，否则只是扩容
static final int MIN_TREEIFY_CAPACITY = 64;

table用来初始化（必须是二的n次幂）

//实际存储的数组 Entry数组。jdk中称其为 hash桶
transient Node<K, V>[] table;

table在JDK8中我们了解到，是由数组+链表+红黑树来组成结构。JDK8之前，这个类型叫Entry。实际上也只是改了个名字而已。二者都是实现了一样的接口，都是Map.Entry。

用来存放缓存

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

HashMap中存放元素的个数

//实际存储的个数，这里的size是标识HashMap中key-value的数量，而不是数组的长度
transient int size;

用来记录HashMap的修改次数

//map中数据改变次数的统计，每次扩容或者更改map结构的计数器
transient int modCount;

用来调整大小下一个容量的值，计算方式为(容量*负载因子)

/**
 * 临界值，与HashMap扩容相关
 * 计算方式：数组长度 * 负载因子
 * 当HashMap中元素个数超过这个值的时候
 * 就会进行扩容
 * @serial
 */
int threshold;

哈希表的加载因子

//负载因子，初始值=0.75，与扩容有关
final float loadFactor;

说明：

1、loadFactor负载因子，是用来衡量HashMap满的程度，表示HashMap的疏密程度，影响hash操作到同一个数组位置的概率，计算HashMap的实时加载因子的方法为：size / capacity。

2、loadFactor太大会导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。0.75是官方经过大量的数据测试，得出的最好的数字。

3、当HashMap中容纳的元素超过边界值时，认为HashMap太挤了，就需要扩容。这个扩容的过程涉及到rehash、复制等操作，非常的消耗性能，所以开发中尽量减少扩容的次数，可以通过创建HashMap时指定初始化容量来尽量的避免。

比如：我们需要存放1000个元素到HashMap，那么我们可能需要new HashMap(1024)。但是1024*0.75=768<1000，就会扩容，因此这个时候我们应该new HashMap(2048)。

构造方法

1、空参构造，构造一个空的HashMap，默认负载因子是0.75，JDK7中，在我们new HashMap的时候，会立即创建Hash桶，而在jdk8中，在new HashMap时，并不会创建数组，而是在put方法中，先判断table是否为空。

//用默认的容量去初始化一个HashMap（16）
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

2、构造一个指定初始容量和默认负载因子的HashMap。（推荐）

//指定容量去初始化一个HashMap
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

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

/**
 * 用指定的容量和负载因子初始化一个HashMap
 *
 * @param initialCapacity 初始值
 * @param loadFactor      负载因子
 * @throws IllegalArgumentException 如果初始容量为负或负载系数为非正
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 判断初始化容量 initialCapacity 是否小于0
    if (initialCapacity < 0) {
        // 如果小于 0，抛出非法的参数异常
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    }
    // 判断初始化容量 initialCapacity 是否大于集合的最大容量 MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY) {
        // 如果超过最大容量，将最大容量赋值给 initialCapacity
        initialCapacity = MAXIMUM_CAPACITY;
    }
    // 判断加载因子 是否小于等于0，或者是否是一个非法数值
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        // 如果满足上面条件，抛出非法参数异常
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    }
    // 将指定的负载因子赋值给 loadFactor
    this.loadFactor = loadFactor;
    /*
        tableSizeFor 判断指定的初始化容量是否为 2 的n次幂，
        如果不是，那就变为比指定容量大的最小的2的n次幂。
        但是注意，这里计算出初始化容量之后，直接赋值给了threshold
        有人认为这是个bug
        事实上，在put方法中，会对threshold重新计算
     */
    this.threshold = tableSizeFor(initialCapacity);
}

4、参数是Map的构造方法。

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

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 获取map的元素个数
    int s = m.size();
    if (s > 0) {
        // 判断 table是否已经初始化
        if (table == null) {
            // 未初始化， s是m的元素个数
            /*
                假设 s 是 6，s / loadFactor = 8
             */
            float ft = ((float) s / loadFactor) + 1.0F;
            int t = ((ft < (float) MAXIMUM_CAPACITY) ?
                    (int) ft : MAXIMUM_CAPACITY);
            // 判断得到的值是否大于阈值，如果大于阈值，则初始化阈值
            if (t > threshold) {
                threshold = tableSizeFor(t);
            }
        } 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);
        }
    }
}

注意：loat ft = ((float) s / loadFactor) + 1.0F; 为什么要 +1？S / loadFactor结果是小数，+1.0F作用是相当于给小数向上取整，尽可能保证更大容量。更大的容量能够减少resize次数。

成员方法

put()方法

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

1）先通过hash值计算出key映射到哪个桶；
2）如果桶上没有碰撞冲突，则直接插入；
3）如果出现碰撞冲突了，则需要处理冲突：
	a:如果该桶使用红黑树处理冲突，则调用红黑树的方法插入数据；
	b:否则采用传统的链式方法插入。如果链的长度达到临界值，则把链转变为红黑树；
4）如果桶中存在重复的键，则为该键替换新值value；
5）如果size大于阈值threshold，则进行扩容；

具体的方法如下：

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

说明：

1）HashMap只提供了put()用于添加元素，putVal()方法只是给put()方法调用的一个方法，并没有提供给用户使用。所以我们重点看putVal()方法。

2）我们可以看到在putVal()方法中key在这里执行了一下hash()方法，来看一下hash方法是如何实现的。

hash()方法

static final int hash(Object key) {
    int h;
    //如果key为null，返回的哈希值是0
    //如果key不为null，首先计算出key的hashCode，
	//然后赋值给h，接着，h进行无符号右移16位，再进行异或运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

从上面我们可以得知，HashMap是支持null key的，而HashTable是直接使用key来获取hashCode，所以key为空会抛异常。

上面已经解释了为什么HashMap的长度要是2的n次幂，因为HashMap设计的非常巧妙，它通过 hash & (length - 1) 来得到该对象的保存位，等价于hash % length，但是&效率比%要高。

探究为什么 h 要右移16位？

key.hashCode，返回散列值也就是hashCode，假设生成一个值。
Length表示数组长度，16。
^ 异或运算符，运算规则：相同的二进制数位上，数字相同，结果为0，否则为1。

说明：高16位不变，低16位和高16位进行了一个异或运算。

问题：为什么要怎么操作？

如果当length的长度很小，假设是16，那么length-1→1111 ，这样的值和hashCode直接做按位与操作，实际上只使用了哈希值的后4位，高位将没有任何意义。如果当哈希值高位变化很大，低位变化很小，这样就非常容易造成哈希冲突，所以这里要把高位和低位都利用起来，从而解决这个问题。说白了，这个操作的作用，其实就是为了防止哈希冲突。

putVal()方法

HashMap中put()方法的核心方法。向HashMap中添加数据的主要逻辑在这个方法中。

/**
 * 实现 Map.put 和相关方法
 * @param hash         key的hash值
 * @param key          原始key
 * @param value        key对应的value
 * @param onlyIfAbsent 如果为true代表不更改现有的值
 * @param evict        如果为false，表示table为创建状态
 * @return 以前的值，如果没有，则为null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K, V>[] tab;
    Node<K, V> p;
    // n存放数组长度。i存放key的hash计算后的值
    int n, i;
    /*
        判断table是否为空
        1. table 表示存储在Map中的元素的数组
        2. (tab = table) == null 表示将table赋值给tab，并且判断tab是否为null。
        3. (n = tab.length) == 0 表示，将tab的长度赋值给n，并判断n 是否等于-
     */
    if ((tab = table) == null || (n = tab.length) == 0) {
        // 如果为空就通过resize实例化一个数组
        /*
            这里的代码等价于
            tab = resize();
            n = tab.length
         */
        n = (tab = resize()).length;
    }
    /*
        i = hash & (n - 1) 计算当前key所在下标，确定在哪个桶中，并将下标赋值给i
        p = tab(i) 将该位置的元素赋值给p，并且判断是否为null
     */
    if ((p = tab[i = (n - 1) & hash]) == null) {
        // 直接创建一个Node元素，赋值给当前下标位置
        tab[i] = newNode(hash, key, value, null);
    } else {
        // 当前下标位置不为null
        // 注意，我们在上面的if中，已经把当前下标位置的元素，赋值给了p
        Node<K, V> e;
        K k;
        /*
            比较桶中第一个元素的hash值和key是否相等。
            1. p.hash == hash ：判断第一个元素的hash与我们传进来的hash是否相等
            2. ((k = p.key) == key || (key != null && key.equals(k)))
                2.1 (k = p.key) == key 将第一个元素的key赋值给k，并且判断是否和我们传进来的key相等
                2.2 判断我们传进来的key不等于null，并且key的值和k相等
             上面如果都满足的情况下，说明第一个元素的key和我们传进来的key值是相等的
         */
        if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) {
            // 将该位置的节点赋值给e
            e = p;
        } else if (p instanceof TreeNode) {
            // 判断当前下标位置的数据类型是否为红黑树
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        } else {
            // 说明当前元素是个链表
            // 不是红黑树，当前下标位置的key也与要插入的key不相等
            // 遍历链表
            for (int binCount = 0; ; ++binCount) {
                /*
                    (e = p.next) == null 将p的下一个元素赋值给e，并判断e是否为null
                    如果等于null，说明当前元素是表尾，已经没有下一个元素了
                    如果不为null，说明下一个元素还存在，可以继续遍历
                 */
                if ((e = p.next) == null) {
                    // 进入，说明e是表尾
                    // 直接将数据写到下一个节点
                    p.next = newNode(hash, key, value, null);
                    /*
                        1. 节点添加完成之后判断此时节点个数是否大于临界值 8，如果大于则将链表转为红黑树。
                        2. int binCount = 0，表示for循环的初始化值，从0开始计算，记录遍历节点的个数
                            |- 0表示第一个节点
                            |- 1表示第二个节点
                            |- ...
                            |- 7表示第八个节点
                            因此这里TREEIFY_THRESHOLD需要-1
                     */
                    if (binCount >= TREEIFY_THRESHOLD - 1) {
                        // 将链表转为红黑树
                        treeifyBin(tab, hash);
                    }
                    break;
                }
                // 如果当前位置的key与要存放位置的key相同，直接跳出
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                    /*
                        要添加的元素和链表中存在的元素相等了，则跳出for循环，不需要再比较后面的元素了
                        直接进入下面的if语句去替换e的值
                     */
                    break;
                }
                // 说明新添加的元素和当前节点不相同，继续找下一个元素。
                p = e;
            }
        }
        // e不为空，说明上面找到了一个去存储Key-Value的Node
        if (e != null) {
            // 拿到旧Value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) {
                // 新的值赋值给节点
                e.value = value;
            }
            afterNodeAccess(e);
            // 返回旧value
            return oldValue;
        }
    }
    // 统计数据改变次数
    ++modCount;
    // 当最后一次调整之后的Size大于临界值，就需要调整数组容量
    if (++size > threshold) {
        resize();
    }
    afterNodeInsertion(evict);
    return null;
}

数组扩容resize()

什么时候才需要扩容？

当HashMap中元素个数超过数组长度负载因子就会进行扩容。也就是说，当HashMap数组长度是16的时候，如果元素个数超过 160.75=12 的时候，就会给数组扩容，扩容方式就是将原数组扩大2倍 16*2=32。然后重新计算每个元素在数组中的位置。而这是个非常消耗性能的过程，所以当我们已经预知到HashMap中元素个数的时候，应当赋予一个基本不可能让这个HashMap扩容的长度。

当HashMap中的其中一个链表的对象个数达到了8个，此时如果数组长度没有达到64，那么HashMap也会进行扩容。如果达到了64，那么这个链表会变成红黑树，节点类型由Node变成TreeNode。

HashMap的扩容是什么？

进行扩容，会伴随着一次重新的Hash分配，并且会遍历hash表中的所有元素，是非常耗时的，所以在编写代码的过程中，应当尽量的避免HashMap的resize。

HashMap在进行扩容的时候，使用rehash非常的巧妙。因为，每次扩容都是翻倍，与原来的(n-1)&hash的结果相比，只是多了一个二进制位，所以节点要么在原来的位置，要么就被分配到原位置+原容量这个位置。

比如我们从16扩容到32：

在元素重新计算hash之后，因为n变为2倍，那么n-1的标记范围在高位多1，因此我们的新index就会发生这样的变化。

因此，我们在扩容HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就可以了。是0的话下标不变，是1的话下标变为原位置+旧容量。可以看下图是16扩容到32的示意图。

正是因为这样巧妙地rehash方式，既省去了重新计算hash的时间，而且同时，因为新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每一个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的hash冲突，均匀的把之前的冲突的节点分散到新的桶中。

//数组扩容
final Node<K, V>[] resize() {
    // 先拿到旧的hash桶
    Node<K, V>[] oldTab = table;
    // 获取未扩容前的数组容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 旧的临界值
    int oldThr = threshold;
    // 定义新的容量和临界值
    int newCap, newThr = 0;
    // 旧容量大于0
    if (oldCap > 0) {
        // 旧的容量如果超过了最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 临界值就等于Integer类型最大值
            threshold = Integer.MAX_VALUE;
            // 不扩容，直接返回就数组
            return oldTab;
        }
        /*
            没超过最大值，数组扩容为原来的2倍
            1.(newCap = oldCap << 1) < MAXIMUM_CAPACITY 扩大到2倍之后赋值给newCap，判断newCap是否小于最大容量
            2.oldCap >= DEFAULT_INITIAL_CAPACITY 原数组长度大于等于数组初始化长度
         */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY) {
            // 当前容量在默认值和最大值的一半之间
            // 新的临界值为当前临界值的2倍
            newThr = oldThr << 1; // double threshold
        }
    } else if (oldThr > 0) // initial capacity was placed in threshold
    {
        // 旧容量为0，当前临界值不为0，让新的临界值等于当前临界值
        newCap = oldThr;
    } else {
        // 当前容量和临界值都为0，让新的容量等于默认值，临界值=初始容量*加载因子
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 经过上面对新临界值的计算后如果还是0
    if (newThr == 0) {
        // 计算临界值为新容量 * 加载因子
        float ft = (float) newCap * loadFactor;
        // 判断新容量小于最大值，并且计算出的临界值也小于最大值
        // 那么就把计算出的临界值赋值给新临界值。否则新临界值默认为Integer最大值
        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];
    // 赋值给hash桶
    table = newTab;
    // 下面一堆是复制值
    // 如果旧的桶不为空
    if (oldTab != null) {
        // 遍历旧桶，把旧桶中的元素重新计算下标位置，赋值给新桶
        // j 表示数组下标位置
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            /*
               (e = oldTab[j]) != null 将旧桶的当前下标位置元素赋值给e，并且e不为null
             */
            if ((e = oldTab[j]) != 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
                    // 到这里说明该位置的元素是链表
                    /*
                    loHead：链表头结点
                    loTail：数据链表
                    hiHead：新位置链表头结点
                    hiTail：新位置数据链表
                     */
                    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) {
                                loTail.next = e;
                            } else {
                                loHead = 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;
}

remove()删除

/**
 * 根据key删除元素
 * 删除是有返回值的
 * 并且返回值是被删除key所对应的value
 */
@Override
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;
    /*
        1. (tab = table) != null  把hash桶赋值给tab，并且判断tab是否为nul
        2. (n = tab.length) > 0 获取tab的长度，赋值给n，判断n是否大于0
        3. (p = tab[index = (n - 1) & hash]) != null 根据hash计算索引位置，赋值给index
            并从tab中取出该位置的元素，赋值给p，并判断，p不为null
     */
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
        // 进入这里面，说明hash桶不为空，并且当前key所在位置的元素不为空
        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;
        }
        // 取出p的下一个节点赋值给e，并且e不为空
        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)))) {
            if (node instanceof TreeNode) {
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            } else if (node == p) {
                // node==p，说明node是第一个节点，那么直接将下一个节点赋值给当前下标
                tab[index] = node.next;
            } else {
                p.next = node.next;
            }
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

get()方法

@Override
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;
    // first存放对应下标位置的第一个元素
    Node<K, V> first, e;
    int n;
    K k;
    /*
        1.(tab = table) != null 把table赋值给tab，并且判断tab不为空
        2.(n = tab.length) > 0 把tab的长度赋值给n，并且判断n大于0
        3.(first = tab[(n - 1) & hash]) != null 根据传进来的hash计算下标位置，取出该下标位置的元素赋值给first，并且判断first不为空
     */
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
        // 下标位置第一个元素的key就是我们要找的key
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k)))) {
            return first;
        }
        // 获取下一个节点赋值给e，并且判断e不为空
        if ((e = first.next) != null) {
            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;
}

HashMap的遍历

//分别遍历key和value
@Test
public void testMap1() {
    HashMap<String, Integer> map = getMap();
    for (String key : map.keySet()) {
        System.out.println(key);
    }
    for (Integer value : map.values()) {
        System.out.println(value);
    }
}

//使用iterator迭代器迭代
@Test
public void testIterator() {
    HashMap<String, Integer> map = getMap();
    Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, Integer> entry = iterator.next();
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
}

//通过get方式，根据阿里开发手册，不建议此方式，因为要迭代多次，keySet一次，get一次
@Test
public void testGet() {
    HashMap<String, Integer> map = getMap();
    Set<String> keySet = map.keySet();
    for (String key : keySet) {
        System.out.println(key + ":" + map.get(key));
    }
}

//JDK8以后使用Map接口中的一个默认方法
@Test
public void testForeach() {
    HashMap<String, Integer> map = getMap();
    map.forEach((key, value) -> {
        System.out.println(key + ":" + value);
    });
}

HashMap使用细节

1、HashMap初始化问题描述

如果我们确切的知道我们有多少键值对需要存储，那么我们在初始化HashMap的时候就应该指定它的容量，以防止HashMap自动扩容，影响使用效率。

默认情况下HashMap容量是16，如果用户通过构造方法指定了一个数字作为容量，那么HashMap会选择大于等于该数字的第一个2的n次幂作为容量。《阿里巴巴Java开发手册》中建议我们使用HashMap的初始化容量。

2、HashMap中容量的初始化

当我们使用HashMap(int initialCapacity)来初始化容量的时候，JDK会默认给我吗计算一个相对合理的值来当做初始容量。那么，我们是不是直接把元素个数作为initialCapacity就可以了呢？

答案是否定的。因为在我们使用HashMap的过程中，随着元素的数量不断增大，hashmap会不断地进行扩容。并且扩容条件是元素个数=数组长度*0.75。比如我们需要存放1000个元素，那么我们设置1000会有两个不合理之处。

（1）1000不是2的n次幂，设置为1000hashmap会给我们计算成1024；

（2）1024虽然是2的n次幂，但是1024*0.75 < 1000，因此当我们使用的过程中，肯定会出现扩容，造成性能上的浪费，因此我们需要设置为2048。

红黑树

二叉搜索树

上面这张图就是个二叉搜索树。二叉搜索树满足下面几条特征：

左子树上所有节点的值均小于或者等于它的根节点的值
右子树上所有节点的值均大于或者等于它的根节点的值
左右子树也分别为二叉搜索树

红黑树

红黑树是一种自平衡的二叉搜索树，每个节点都带有颜色属性，颜色是红色或者黑色。在二叉搜索树的特征以外，任何一条红黑树都有以下额外的特性：

节点是红色或者黑色
根节点一定是黑色
每个叶子结点（NIL节点）是黑色的
每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不可能有两个连续的红色节点）
从任意一个节点到其每个叶子节点的所有路径包含相同数目的黑色节点

红黑树查找

因为红黑树是一个自平衡的二叉搜索树，查询操作不会破坏红黑树的平衡，所以查找和二叉搜索树的查询方式没有区别。

从根节点开始，把根节点设置为当前节点。
若当前节点为空，则返回null。
若当前节点不为空，用当前节点的key和查找key做比较。
若当前节点的key等于要查找的key，那么该key就是查找目标，返回当前节点。
若当前节点key大于查找的key，把当前节点的左子节点设置为当前节点，重复2。
若当前节点key小于查找的key，把当前节点的右子节点设置为当前节点，重复2。

final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
    TreeNode<K, V> p = this;
    do {
        int ph, dir;
        K pk;
        TreeNode<K, V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h) {
            p = pl;
        } else if (ph < h) {
            p = pr;
        } else if ((pk = p.key) == k || (k != null && k.equals(pk))) {
            return p;
        } else if (pl == null) {
            p = pr;
        } else if (pr == null) {
            p = pl;
        } else if ((kc != null ||
                (kc = comparableClassFor(k)) != null) &&
                (dir = compareComparables(kc, k, pk)) != 0) {
            p = (dir < 0) ? pl : pr;
        } else if ((q = pr.find(h, k, kc)) != null) {
            return q;
        } else {
            p = pl;
        }
    } while (p != null);
    return null;
}

treeifyBin方法

put()的时候，节点添加完成之后就会判断此时节点个数是否大于8，如果大于则将链表转换为红黑树。

//替换指定哈希表的所引出桶中的所有节点，除非表太小，否则将修改大小
final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index;
    Node<K, V> e;
    /*
        如果当前数组为空，或者数组长度小于进行树形化的阈值（64）就去扩容，而不是转换为红黑树。
        目的：如果数组很小，那么转换为红黑树然后遍历效率要低一些，这时候进行扩容，那么重新计算哈希值
        链表的长度就有可能变短了，数据会放到数组中，这样相对来说效率高一些
     */
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize();
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
        /*
            1.执行到这里说明哈希表中数组长度大于阈值64，开始进行树形化。
            2.(e = tab[index = (n - 1) & hash]) != null 通过当前key的hash计算当前key所在的下标位置，取出来赋值给e，判断e不为空
         */
        // hd：红黑树的头结点。tl：红黑树的尾结点
        TreeNode<K, V> hd = null, tl = null;
        do {
            // 重新创建一个树节点，内容和当前链表节点e一致
            TreeNode<K, V> p = replacementTreeNode(e, null);
            if (tl == null) {
                // 将新创建的p节点赋值给红黑树的头结点
                hd = p;
            } else {
                /*
                p.prev = tl 将上一个节点p赋值给现在的p的前一个节点
                tl.next = p 将现在的节点p作为树的为节点的下一个节点
                 */
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //让桶中第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树，而不是链表
        if ((tab[index] = hd) != null) {
            hd.treeify(tab);
        }
    }
}

自平衡

红黑树能自平衡，就是左旋、右旋、变色三个操作。

左旋：以某个节点作为支点，其右节点变为旋转节点的父节点，右节点的左节点变为旋转节点的右节点，其余不变。

右旋：以某个节点作为支点，其左节点变为旋转节点的父节点，左节点的右节点变为旋转节点的左节点，其余不变。

变色：节点的颜色由红变黑或者由黑变红的过程。

目录CONTENT

HashMap原理