HashMap 底层结构与实现
HashMap 底层是基于哈希表（Hash Table）实现的，它存储的元素是键值对（key-value）。底层的数据结构是一个数组，数组的每个元素是一个 桶（bucket），用于存储发生哈希碰撞的元素。每个桶本质上是一个链表或红黑树。
1.7 版本（数据结构：数组 + 链表）
在 JDK 1.7 中，HashMap 底层的哈希表是由数组和链表实现的：
- 数组：用来存储数据的容器，数组的每个元素是一个桶（bucket）。
- 链表：当发生哈希冲突时，将多个元素（具有相同哈希值）存储在同一个桶中，链表的形式连接。
1.8 版本（数据结构：数组 + 链表/红黑树）
从 JDK 1.8 开始，HashMap 进行了优化，链表部分当元素数量大于 8 时会转化为 红黑树，以提高查找性能。新的底层结构为：
- 数组：依然是用来存储桶。
- 链表：当桶中的元素较少（<= 8）时，继续使用链表。
- 红黑树：当桶中的元素较多（> 8）时，链表会转化为红黑树，红黑树的查找时间复杂度是 O(log n)，比链表的 O(n) 更高效。
哈希冲突的处理
当发生哈希冲突时（即多个键具有相同的哈希值，经过哈希函数映射到相同的数组索引），HashMap 会通过链表或红黑树来处理冲突。
Java 1.7 中的处理方式：
-
链表插入：当哈希冲突发生时，新的元素会被添加到 链表的头部。这意味着
HashMap中的键值对按照插入顺序在链表中排列。例如，假设发生冲突的桶索引为
i，原来有一个元素 A（keyA，valueA）在该桶，接着插入一个新元素 B（keyB，valueB）。那么，在 Java 1.7 中，B 会插入到链表的头部，A 会位于链表的后面，形成：bucket[i] --> Node(keyB, valueB) -> Node(keyA, valueA)
Java 1.8 中的处理方式：
-
链表插入：在 Java 1.8 中，哈希冲突时，元素会被插入到 链表的尾部。这意味着新的元素会添加到链表的末尾，而不是头部。
举个例子，如果桶
i中原来有元素 A（keyA，valueA），插入 B（keyB，valueB）时，B 会被添加到链表的尾部，形成：bucket[i] --> Node(keyA, valueA) -> Node(keyB, valueB) -
红黑树转化：当某个桶中的链表长度超过 8 时（默认阈值），链表会转化为红黑树，从而提高查询性能（O(log n)），避免了链表查找的 O(n) 性能瓶颈。
扩容机制
在 Java 1.7 和 Java 1.8 中，当 HashMap 中的元素数量超过负载因子（默认是 0.75）时，会进行扩容，数组的大小通常会翻倍。扩容时，所有的元素需要重新计算哈希值并重新分配到新的桶中。
总结：Java 1.7 vs Java 1.8 之间的主要区别
-
哈希碰撞的处理：
- Java 1.7：哈希冲突发生时，元素插入到链表的头部。
- Java 1.8：哈希冲突发生时，元素插入到链表的尾部。
-
红黑树优化：
- Java 1.7：只有链表来处理哈希冲突。
- Java 1.8：当某个桶的链表长度大于 8 时，链表会转化为红黑树，以提高查找效率。
-
性能优化：
- Java 1.8 在哈希冲突较多的情况下，链表转红黑树的方式能有效提升性能，避免了链表查找的 O(n) 时间复杂度，提升了查询效率。
性能差异
- 1.7 版本中，当哈希冲突较多时，查找元素的性能会下降，因为冲突处理采用链表，导致最坏情况下需要遍历整个链表（O(n)）。
- 1.8 版本中，当链表长度较长时，链表会被转换为红黑树（O(log n) 查找），大大提升了查询效率。
因此，Java 1.8 对于 HashMap 的性能优化，特别是在冲突较多的情况下，有显著提升。
