⭐️前面的话⭐️

本篇文章将介绍Java中HashMap的底层实现原理，有关HashMap为数组开辟内存的时期，默认的容量，默认负载因子，树化的条件，HashMap的扩容机制，put方法的过程以及HashMap中的哈希函数。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创，CSDN首发！
📆首发时间：🌴2022年8月31日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《数据结构》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

1.HashMap以及HashMap的基本原理

1.1什么是HashMap？

HashMap是Java集合框架中Map容器的一个实现类，它的底层是使用哈希表实现的，更加具体地说在jdk7中采用数组+链表实现，在jdk8中采用数组+链表+红黑树实现。

Map代表具有映射关系（key-value）的集合，其所有的key是一个Set集合（key值不能重复），即key无序且不能重复，而HashMap就是Map接口下的一个实现类，HashMap是一个储存键值对（EntrySet）的集合，并且支持储存key/value为null的元素。

下面我们基于jdk8来说一说HashMap的基本原理。

1.2HashMap的属性

HashMap对象被构造时，初始的默认容量为1<<4，也就是16，并且必须是2的幂（这与哈希函数有关）。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap最大的容量为1<<30，也就是 $2^{30}$。

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap默认的负载因子为0.75。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表树化的最小链表大小阈值8，当HashMap中数组大于64，数组所挂链表的大小超过8才会将数组所挂的链表转换为红黑树。

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

红黑树链表化的的阈值是6，当红黑树结点个数小于6时，就会转换为链表。

static final int UNTREEIFY_THRESHOLD = 6;

HashMap底层的数组，是一个链表数组：

transient Node<K,V>[] table;

元素个数阈值，当HashMap的size大于threshold时会执行resize操作，threshold=capacity*loadFactor，其中capacity表示数组的容量。

int threshold;

1.3HashMap的构造方法

HashMap最常用的构造方法，一个是无参的构造方法，使用无参构造方法构造HashMap时，默认的构造容量是16，但是此时不会真的去申请一个大小为16的数组，还有一个指定容量的构造方法也是如此，并且所取容量为大于或等于指定容量的一个最接近的2次幂数，日指定容量为19，那实际数组容量为32。

源码：

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

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

除此之外，还有指定容量和负载因子的构造方法，其中tableSizeFor(initialCapacity)方法会生成比initialCapacity大并最接近initialCapacity的一个2次幂。

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

从源码可以看出其实在使用以上三种构造方法进行对象构造的时候，并没有为数组分配空间，只是确定负载因子，容量等属性。

最后还有一个根据其他的Map对象构造HashMap的构造方法，使用这种方式构造，只要传入的参数有元素，那么数组空间肯定已经申请好了，否则也是没有去申请的。

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

所以我们可以得到一个结论：当HashMap对象创建时，内部的数组并没有分配内存。

1.4HashMap开辟数组的时机

真正为数组分配内存是在第一次put操作的时候，其中源码如下：

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

意思就是通过哈希函数hash生成对应数组的下标值，找到对应的位置进制插入。
如果是第一次插入，就会对链表数组进行扩容，也是正式地为数组初始化：

我们就不继续深入看了，在resize方法中，会为数组分配内存，并且大小为2的幂，至于为什么是这个值，这与HashMap中的哈希函数有关。

1.5HashMap中的put

如果是首次扩容，先判断数组是否为空，若数组为空则进行第一次扩容（resize），会为HashMap对象申请一个默认容量大小16的数组。

第一步，通过hash()方法计算索引，通过hash算法，计算键值对在数组中的索引，并通过索引找到在数组中的位置。
第二步，插入数据，分以下几种情况：

• 如果当前位置元素为空，则直接插入数据；
• 如果当前位置元素非空，遍历链表或红黑树，如果key已存在，则直接覆盖其value；
• 如果当前位置元素非空，遍历链表或红黑树，如果key不存在，则将数据链尾插（jdk7是头插）到链表；
• 若链表长度达到8，并且HashMap中的table数组大小达到64，则将链表转换成红黑树，并将数据插入树中，如果链表长度达到8但是table数组大小没有64则将数组扩容；

第三步，检查存储的元素个数，如果超过阈值threshold，则扩容。这一步其实也就是检查负载因子是否超过默认值，超过就扩容。

1.6HashMap中的哈希函数

前面我们说到了hash方法，HashMap中的hash方法是与我们直接根据key生成hashCode值再取模的方式不同，在HashMap中的hash算法中，首先会key计算出hashCode值，然后再将hashCode值与右移16为的hashCode值进行按位异或操作，得到一个新的哈希值，这样做的目的其实就是为了增强哈希值的随机性，这个方法也叫做“扰动方法”。

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

在进行put等需要找到某个key所对应的数组索引的时候，HashMap不是通过直接取数组长度的模来得到对应的下标，取而代之的是使用按位与&运算来进行下标的计算，毕竟位运算的效率是大于取模%操作的。假设HashMap底层数组table的长度为length，不妨记n=length-1，key对应的哈希值为h。

在jdk8源码中，使用h&(n-1)来获取对应table数组的索引（下标）,这也解释了为什么HashMap当中的数组长度一定是2的幂。

因为使用2的幂再减去一个1，得到的数n它的所有有效二进制位均为1，如64的二进制数为1000000，减去1得到n，它的值为0111111，数组的长度的二进制有效位是7位，因为数组长度是二的幂，数组下标最大下标有效位一定是6位，并且全为1，我们知道0与任何数按位与得到的均为0，而1与任何数运算得到的结果可能是1也可能是0，这就保证了在使用&操作时，每一位有效位的值都有可能是0或1，进一步就保证了数组table的所有下标均有可能被映射到，反之如果存在含有0的二进制有效位，则那一位按位与的操作结果一定是0，这样的话，一定存在数组table中某些下标无法被映射，增大了哈希冲突的可能性。

做个小总结，HashMap中计算的哈希值是通过hashCode值与右移16位hashCode值按位异或的结果，这个目的就是为了增强哈希值的随机性。HashMap确定索引的方法是将n&h，毕竟按位与的效率大于取模，为了数组每个下标都可能被映射到，则n的每一位二进制有效位均得为1，所以数组的长度必须为2的幂，因为只有2的幂减1得到的有效二进制位均为1。

其中n表示数组长度减去一个1，h表示通过hash方法得到的哈希值。

1.7HashMap的扩容机制

HashMap中table数组初始默认大小为16，根据上述对hash方法的分析，数组table长度一定得是2的幂，从这里就不难猜出，HashMap极有可能是2倍扩容，毕竟2倍扩容比较合理，并且它能够保证扩容后的数组大小也是2的幂。

在jdk8中，HashMap的扩容，确实是采用了2倍扩容。

当HashMap对象中元素个数size大于threshold或者数组为null时会触发扩容resize。

为了解决哈希冲突，jdk8采用了数组+链表+红黑树的方式实现，当数组中某链表的长度大于8，并且数组table的长度达到64，就会将链表转换为红黑树来提高效率，当数组中某链表长度大于8但是数组table长度没有达到64，此时就会进行扩容。

当红黑树结点个数小于6时，就会将红黑树转换回链表。

在扩容的时候，会将所有的元素遍历，全部重新计算哈希值并全部重新确定在数组中的位置。

2.HashSet的基本实现原理

HashSet是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。它封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

3.有关HashMap其他的面试题

3.1HashMap是否是线程安全的？有没有线程安全的"HashMap"？

HashMap不能保证线程安全，因为在并发的情况下进行put操作，可能会导致数组中链表死循环。
线程安全的“HashMap”有HashTable，它相比于HashMap，给关键的方法加上了锁，那么给方法加锁本质上就是给对象加锁，那么每种操作都需要拿对象锁，这样会造成激烈的锁竞争。
相比于HashTable，更推荐使用CurrentHashMap，在jdk7中，它是给每一个数组中的元素都加上了锁，或者说创建了一个新的数组Segment，这个数组用于实现加锁操作，每个 Segment 里包含一个 HashEntry 数组，Segment 中元素的结构和 HashMap 类似，是一个数组和链表结构。
在jdk8中，已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap，简单说，在HashMap的基础上，就是给每个数组中的元素加锁，来保证线程安全，并且由于每个数组元素都有锁，所以相比于HashTable锁竞争的激烈程度小得多。

3.2HashMap有什么特点？

1. HashMap是线程不安全的，支持序列化。
2. HashMap可以使用null作为key或value。
3. HashMap查找的效率可达到O(1)。
4. HashMap遍历方式比较单一，主要使用EntrySet 和 KeySet进行遍历，遍历方式有增强for循环和迭代器。
5. HashMap是Map容器的一种实现，是无序的键值对集合。