1、特点

• 底层是链表+数组，JDK1.8开始，当链表长度超过8时，会将链表转换为红黑树。

• 储存的是key-value类型数据。

• key值不允许重复，key重复会被覆盖，value允许重复。

• 数据储存无序（不记录存入的顺序）。

• key和value都允许为空，但是只能有一个空的key。

2、相较于其他集合

• HashMap是一种基于哈希表的Map接口实现。它提供了常数时间的get和put操作，这意味着无论HashMap中有多少元素，获取和插入元素所需的时间都大致相同。这是因为HashMap使用了哈希表来存储键值对，它通过计算键的哈希值来快速定位键值对在哈希表中的位置。

• 相比之下，其他一些集合（如ArrayList或LinkedList）需要线性时间来搜索元素，这意味着它们在元素数量增加时性能会下降。

• 当然，HashMap也有一些局限性。例如，它不保证元素的顺序，而且在某些情况下可能需要进行扩容，这会导致性能下降。

• HashMap适用于需要快速查找、插入和删除键值对的场景。例如，您可以使用HashMap来存储一个字典，其中键是单词，值是定义。这样，您就可以快速查找单词的定义，而不需要遍历整个字典。

• 此外，HashMap还可以用于缓存数据，以便快速访问。例如，您可以使用HashMap来存储从数据库中检索的数据，这样下次需要相同数据时，就可以直接从HashMap中获取，而不需要再次查询数据库。

• 当然，HashMap并不适用于所有场景。例如，如果您需要按照元素插入的顺序来遍历元素，那么您应该使用LinkedHashMap而不是HashMap。如果您需要对元素进行排序，那么您应该使用TreeMap而不是HashMap。

3、底层结构

1.7:数组+链表 (由于是链表长度长了。查询效率不高。所以在设计初衷1.7的hash算法更复杂。数据也更散列)

1.8:数组+链表+红黑树（JDK8中即使用了单向链表，也使用了双向链表，双向链表主要是为了红黑树相关链表操作方便，应该在插入，扩容，链表转红黑树，红黑树转链表的过程中都要操作链表）

Node是链表的节点，它包含了key、value和next三个属性。

TreeNode是红黑树的节点，它包含了key、value、next、left、right和parent六个属性。

 3.1 链表——》红黑树

当链表中的元素个数大于8（此时 node 有9个），并且数组的长度大于等于64时才会将链表转为红黑树。而当红黑树中的元素个数小于等于6时，会将红黑树转为链表形式

    为什么要将链表转化为红黑树呢

链表转换为红黑树的最终目的，是为了解决在map中元素过多，hash冲突较大，而导致的读写效率降低的问题。

    转化的流程

并不是简单地将链表转换为红黑树，而是先判断table的长度是否大于64，如果小于64，就通过扩容的方式来解决，避免红黑树结构化（转化为红黑树浪费性能）。

链表长度大于8有两种情况：

• table长度足够，hash冲突过多

• hash没有冲突，但是在计算table下标的时候，由于table长度太小，导致很多hash不一致的
  第二种情况是可以不转为红黑树、改为调用resize方法进行扩容来避免的，扩容后链表长度变短，读写效率自然提高。另外，扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。
  由此可见并不是链表长度超过8就一定会转换成红黑树，而是先尝试扩容

  3.2 红黑树——》链表

在扩容方法 resize()中的“将原Node数组中的元素拷贝到新的Node数组”中的步骤中，如果遍历到的Node元素是一个红黑树的时候，出现了一个split()方法，

该split方法的目的是：将该红黑树进行拆分，然后迁移到新的Node数组中。

（如果拆分后的子树过小(子树的节点小于等于6个)，则取消树化，即将其转为链表结构）；

介绍一下resize（）方法

4、常用方法

• .put(K key, V value) 将键（key）/值（value）映射存放到Map集合中（也就是将两值存入集合中）

• .get(Object key) 返回指定键所映射的值，没有该key对应的值则返回 null，即获取key对应的value。（只返回的了value值）

• . size() 返回Map集合中数据数量，准确说是返回key-value的组数。

• .clear() 清空Map集合

• .isEmpty () 判断Map集合中是否有数据，如果没有则返回true，否则返回false

• .remove(Object key) 删除Map集合中键为key的数据并返回其所对应value值。

• .containsKey(Object key) 判断是否含有key,如果有返回true，如果没有返回false。

• .containsValue(Object value) 判断是否含有value。如果有返回true，如果没有返回false。

• .replace(Object key,Object value)将这个key的value值替换掉，替换为方法为中这个value值。

• .putAll(HashMap )添加另一个同一类型的map下的所有数据.( 下面为此方法代码)

5、putVal（）方法详解

调用HashMap的put方法时，它会调用putVal方法来插入键值对。在putVal方法中，它会进行判断，如果是第一次插入数据，或者达到了扩容阈值会调用resize（）方法，对数组进行操作。

在这个方法中会通过数组的长度和键的hash计算出应存入到数组中的下标。index=（length-1）&hash

总之就是将这个键值对节点放入到它应该处于的集合当中的位置。

6、HashMap的扩容

   6.1为什么要进行扩容

我们知道理论上哈希表的读时间复杂度是O(1)，但是没有一种哈希方法能保证绝对的哈希均匀，为了解决哈希冲突又往往采用链地址法解决，那这样时间复杂度愈发偏离O(1)了，此时进行扩容，其实是让哈希表分散的更均匀，解决性能不够好的问题。

   6.2如何扩容

HashMap的扩容是通过调用resize()方法实现的。

java1.8+在扩容时，不需要重新计算元素的hash进行元素迁移。

而是用原先位置key的hash值与旧数组的长度（oldCap）进行"与"操作。

• 如果结果是0，那么当前元素的桶位置不变。

• 如果结果为1，那么桶的位置就是原位置+原数组 长度

值得注意的是：为了防止java1.7之前元素迁移头插法在多线程是会造成死循环，java1.8+后使用尾插法

注意：

java1.8 扩容的时候会判断当前的桶的位置有没有链表或者红黑树，如果没有链表或者红黑树，那么当前元素还是和JDK1.7中的求法一样，求新的桶的位置。如果有链表，那么链表的元素会按照上述方法求新的桶的位置。如果是红黑树，则会调用split()方法，将红黑树切分为两个链表，之后进行扩容操作。