hashmap底层原理

HashMap 是一种基于哈希表的 Map 接口实现，用于存储键-值对。它的底层原理是数组加链表/红黑树。具体来说，HashMap 通过哈希函数将键映射到数组的索引位置上，然后将键值对存储在该位置上，如果存在冲突，就将键值对存储在同一个索引位置上的链表或红黑树中。

在 JDK8 中，当链表长度超过 8 时，相应的链表会被转换成红黑树，以提高查询效率。同时，当哈希表中元素数量超过容量的 0.75 倍时，就会触发扩容操作，此时会重新计算哈希值，并将键值对重新分配到新的数组中。

HashMap 的查询、插入和删除操作的时间复杂度都为 O(1)，但是由于哈希冲突的存在，最坏情况下的时间复杂度可能会退化至 O(n)。因此，为了避免哈希冲突，需要合理设计哈希函数，使得键能够均匀地分布在数组中。