HashMap put() 方法底层实现详解 - 数组、链表和红黑树

HashMap 的 put() 方法的底层实现是通过数组和链表/红黑树来实现的。\n\n首先，当调用 put() 方法时，HashMap 会根据键的哈希值计算出在数组中的索引位置。如果该位置上没有元素，那么直接将键值对插入到该位置。如果该位置上已经有元素，那么会进行以下操作：\n\n1. 如果已存在的元素的键和要插入的键相等（根据 equals() 方法判断），那么直接替换该元素的值。\n2. 如果已存在的元素的键和要插入的键不相等，那么会将新的键值对插入到链表（或红黑树）的末尾。\n\n当链表的长度超过阈值（默认为 8）时，链表会被转化为红黑树，以提高查找和插入的效率。\n\n当数组的容量超过阈值（默认为 16）时，数组会进行扩容。扩容的过程包括以下步骤：\n\n1. 创建一个新的数组，容量是原数组的两倍。\n2. 将原数组中的元素重新计算索引位置，并插入到新数组中。\n3. 如果原数组中的某个索引位置上有多个元素（即存在链表或红黑树），那么会按照遍历顺序将这些元素插入到新数组中。\n\n扩容操作会导致所有的原有元素重新计算索引位置，这是为了保持哈希表的性能。因为数组的容量增加，可以降低哈希冲突的概率，从而提高查找和插入的效率。\n\n总结起来，HashMap 的 put() 方法会通过哈希计算确定元素在数组中的索引位置，并根据键的相等性将键值对插入到链表或红黑树中。当链表或红黑树的长度超过阈值时，会进行相应的转换操作。当数组的容量超过阈值时，会进行扩容操作。