每日一道大厂面试题：HashMap的源码实现原理
每日一道大厂面试题：HashMap的源码实现原理，JDK8 中对 HashMap 做了怎样的优化？
HashMap 是 Java 中常用的一种数据结构，它实现了 Map 接口，提供了键值对的存储和查询功能。下面我将简要介绍 HashMap 的源码、实现原理以及 JDK8 中对其做的优化。
HashMap 的源码
HashMap 的源码位于 java.util 包下，其主要实现是通过一个数组加链表的方式来存储数据。具体实现可以分为以下几个部分：
内部类 Node<
K,V>：表示 HashMap 存储的每个键值对，包括键、值以及指向下一个节点的指针。
内部类 TreeNode<
K,V>：继承自 Node<
K,V>，用于在链表长度过长时将链表转换为红黑树以提高查询效率。
内部类 EntrySet、KeySet、Values：分别表示 HashMap 中键值对的集合、键的集合、值的集合。
内部类 HashIterator：实现了迭代器接口，用于遍历 HashMap 中的键值对。
内部类 KeyIterator、ValueIterator：分别表示遍历 HashMap 中键的迭代器和值的迭代器。
内部类 EntryIterator：表示遍历 HashMap 中键值对的迭代器。
实例变量 table：表示存储键值对的数组。
实例变量 size：表示 HashMap 中键值对的数量。
实例变量 threshold：表示数组的容量，当 size 大于等于 threshold 时，数组需要进行扩容。
实例变量 loadFactor：表示负载因子，用于计算 threshold 的值。
HashMap 的源码非常复杂，这里只是简要介绍，如果想要深入了解可以查看 JDK 中的源码。
HashMap 的实现原理
HashMap 的实现原理可以分为以下几个步骤：
根据键的哈希值计算出在数组中的位置，如果该位置上没有元素，直接插入。
如果该位置上已经有元素，判断该元素的键是否和插入的键相等，如果相等则替换值，否则将该元素放入链表的末尾。
当链表长度达到一定阈值时，将链表转换为红黑树，以提高查询效率。
当数组的容量不足以存储所有键值对时，进行扩容，重新计算每个元素在数组中的位置。
JDK8 中对 HashMap 做的优化
在 JDK8 中，HashMap 做了以下几个优化：
1.当链表长度小于等于
8 时，不再将其转换为红黑树，而是继续使用链表，以减少红黑树的创建和维护成本。
2.在扩容时，不再是简单地将数组大小翻倍，而是将容量增加为原来的两倍，并且使用了一种新的扩容方式，即当链表长度小于等于
6 时，将链表中的节点移动到新数组中，而不是创建新的节点。这种方式可以减少节点的创建和内存分配，提高性能。
3. 在计算哈希值时，使用了一种新的方式，即通过位运算代替了传统的取模运算，提高了计算哈希值的效率。
4. 在并发环境下，使用了一种新的方式来解决并发冲突的问题。具体来说，当多个线程同时访问同一个桶时，会使用一种叫做 CAS（Compare And Swap）的机制来保证线程安全，而不是使用传统的锁机制，以提高并发性能。
JDK8 引入了一种新的哈希算法，称为 MurmurHash3，用于计算键的哈希值。相比于传统的哈希算法，MurmurHash3 具有更好的随机性和分布性，可以减少哈希冲突的概率，提高 HashMap 的性能。另外也引入了一种新的数据结构 LinkedHashMap，它继承自 HashMap，并且保证了元素的顺序与插入顺序相同。这种数据结构可以在需要保持元素顺序时使用，比如实现 LRU 缓存等场景。
JDK8 中对 HashMap 的优化主要包括性能、并发性能和哈希算法的优化，这些优化和改进使得 HashMap 在实际应用中更加高效、稳定和灵活。
