HashMap的工作原理详解：数组+链表+红黑树
HashMap的工作原理详解：数组+链表+红黑树
HashMap是Java中非常常用的数据结构，它基于哈希表实现，提供了所有可选的映射操作，并允许使用null值和null键。HashMap不保证映射的顺序，其性能依赖于哈希函数将元素均匀分布在各个桶之间。
HashMap的内部结构
HashMap采用数组加链表的复合结构。数组是HashMap的主干，被划分为多个桶（bucket），每个桶存储一个或多个键值对（Entry）。键值对的存储位置由哈希值决定，哈希值相同的Entry将以链表形式存储。
数组结构
当我们创建一个HashMap对象时，默认数组长度为16，初始值都为null。插入第一个键值对时，会通过哈希函数计算key的哈希值，然后将Entry对象存入对应下标的位置。
例如，插入键值对map.put(99, "huang")时，假设计算出的哈希值为333，则将该Entry存入数组下标为333的位置。
链表结构
当发生哈希冲突时，即多个Entry映射到同一个数组位置时，HashMap会使用链表来存储这些Entry。每个数组元素都是链表的头节点，新插入的Entry会通过"头插法"插入到链表中。
例如，插入键值对map.put(520, "liuliu")时，如果计算出的哈希值也是333，那么这个新的Entry会插入到下标为333的链表中。
Put方法与Get方法原理
Put方法
当调用put方法插入或更新键值对时，首先通过哈希函数计算key的哈希值，确定存储位置。如果该位置已有Entry，则通过equals方法检查key是否已存在，存在则覆盖，不存在则使用"头插法"插入新Entry。
例如，更新键值对map.put(99, "gege")时，会先计算出哈希值333，然后在链表中查找key为99的Entry，找到后进行覆盖。
Get方法
当调用get方法获取值时，首先通过哈希函数计算key的哈希值，定位到数组的某个位置，然后在链表中通过equals方法逐个比对key，直到找到匹配的Entry并返回其value。
例如，获取值map.get(99)时，会计算出哈希值333，然后在链表中查找key为99的Entry，找到后返回其value。
JDK1.7与JDK1.8的区别
在JDK1.7中，HashMap的内部结构是数组+链表。而在JDK1.8中，为了优化大量数据时的查询效率，引入了红黑树。当链表长度超过8时，链表会自动转换为红黑树，以提高查询效率。此外，JDK1.8中在发生哈希冲突时采用"尾插法"，而不是JDK1.7中的"头插法"。