hashmap底层原理

HashMap的底层原理是基于数组和链表（或红黑树）实现的。

首先，HashMap内部维护了一个数组table，这个数组的大小是固定的，一般是2的幂次方，例如16、32、64等。数组的每个元素称为桶，每个桶可以存放一个键值对（Entry）的链表的头节点。

当向HashMap中添加元素时，首先根据键的哈希值计算出该键值对在数组中的索引位置，然后将该键值对插入到相应索引位置的链表中。如果该索引位置已经存在键值对，则通过equals方法比较键的值是否相等，如果相等则替换原来的值，如果不相等则将新的键值对插入到链表的末尾。

当从HashMap中获取元素时，首先根据键的哈希值计算出该键值对在数组中的索引位置，然后遍历对应索引位置的链表，通过equals方法比较键的值是否相等，如果相等则返回对应的值，如果不相等则继续遍历链表直到找到相等的键或者链表为空。

为了提高查询性能，当链表中的键值对数量超过一定阈值（默认是8），HashMap会将链表转换为红黑树。这是因为链表的查询时间复杂度是O(n)，而红黑树的查询时间复杂度是O(log n)，在键值对数量较大时可以提高查询效率。

当链表中的键值对数量小于一定阈值（默认是6），HashMap会将红黑树转换为链表，这是为了避免红黑树带来的额外开销。

需要注意的是，哈希冲突是指不同的键通过哈希函数计算得到相同的哈希值，这种情况下会发生哈希碰撞。HashMap使用链表或红黑树解决哈希冲突，通过equals方法来区分相同哈希值的键值对