HashMap的底层数据结构及原理

HashMap 的底层数据结构是数组和链表（或红黑树）。当插入一个键值对时，首先根据键的 hashcode 计算出在数组中的位置，如果该位置为空，则直接插入；如果该位置已经有元素，则遍历链表（或红黑树），找到对应的键值对，如果找到则更新值，否则插入新的节点。当链表长度超过一定阈值时，链表会转换为红黑树，以提高查找效率。在查找时，首先根据键的 hashcode 计算出在数组中的位置，然后遍历链表（或红黑树），找到对应的键值对。