HashMap 是 Java 中非常重要的集合类型，其具有快速存储，快速查找（时间复杂度非常低，非效非常高），自动扩容等特点，在实际开发中经常用到。

关于 HashMap 特性，底层原理也是面试中被问到概率极高的问题，因为 HashMap 涉及到好几个基本数据结构及相关算法知识，如组数，链表，二叉树及变种，Hash算法等。所以有必要对其深入理解。

HashMap 使用了基本的数据结构，先了解下有助于理解。详细可能考 数据结构与算法(一)：数组、链表、哈希表。

哈希表（Hash Table）：，提供键（Key） 和值（Value）映射关系。只要给出 key ，就可以高效查找到映射的 Value，时间复杂度接近于 Ο(1)，在哈希表中添加，删除，查找等操作，性能非常高 。

哈希表在本质上也是一个数组，通过 哈希函数 将 Key 的哈希值转换为数组的索引，使key:hashcode -> index 建立映射关系。

例如一个长度为 8 的数组，key 为 001121，使用取模运算，转换为数组下标 index = hashcode("001121") % Array.length = 1420036703 / 8 = 7。

通过哈希函数得出的元素在数组中的索引位已被占用， 就出现了哈希冲突。将哈希值转换为有限的数组索引，很大概率出现哈希冲突的问题。解决此问题通常有两种方式：一种是开放 寻址法，一种是 链表法（数组+链表）。

HashMap 用到了链表法，数组中的每一个元素不仅是一个 Entry 对象，还可能是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需插入到对应的链表中即可。

链表法缺点：如果链表越来越长，则链表查找的性能就会越来越差，在 HashMap 中执行插入和查询操作的时间复杂度就提高到了 O(n)。（HashMap 是遍历到链表尾节插入）。

JDK 7 的 HashMap 的数据结构是基于 哈希表+链表。

JDK 8 对 HashMap 的数据结构进行了优化，引入了 红黑树，即采用了 哈希表+链表 / 红黑树 的数据结构，当链表长度超过 8 时，则将链表树化，这样就避免了超长链表的缺点，红黑树的查询插入的时间复杂度是 O(logn)，提高了性能。

Java 语言中，要了解某一功能特性，最好的方式是阅读源码上的注释，JDK 源码的注释是非常严谨和规范的。这一点值的学习。

HashMap 是基于 哈希表 的 Map 接口的实现，提供所有可选的 Map 操作。

假设哈希函数将元素适当地分布在存储桶(Buckets)之间，为基本的 get/put 操作提供了稳定的性能。迭代 Collection 视图所需的时间与 HashMap 实例的容量(capacity：桶的数量)及其大小（键/值映射的元素数量）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。

HashMap 继承自父类（AbstractMap），实现了Map、Cloneable、Serializable 接口。

HashMap 实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中存储桶的数量，初始容量只是创建哈希表时的容量。

size（个数）：Map 中 Key-Value 元素的个数。

Capacity（容量）：是哈希表中存储桶(Buckets)的数量，初始容量（initialCapacity）只是创建哈希表时的容量，默认是 16，最大容量是 1073741824。

loadFactor（负载因子）：是在哈希表的容量自动扩容之前，衡量哈希表满表的系数，默认是 0.75f。

当哈希表中的元数个数超过了负载因子和当前容量的乘积时，则认为满表并对哈希表进行重置（即，内部数据结构被重建），使得新哈希表的存储桶数大约是之前桶数的两倍。

默认负载因子(0.75f)在时间和空间成本之间提供了一个较好的权衡。较高的值会减少空间开销，但会增加查找成本。

设置初始容量，应考虑 Map 中预期的元数个数及其负载因子，以最大程序地减少重新哈希操作的次数。

如果设置了初始容量且大于最大容量除以负载因子的值，则不会发生任何重新哈希操作。附加参考load factor in HashMap。

threshold（扩容前阀值）：threshold = capacity * loadFactor，当 size 大于 threshold 时会执行 resize 扩容操作。

成员变量：