hashmap.put()原理
数组和链表
HashMap是Java中常用的一种数据结构，用于存储键值对。它基于哈希表的实现，通过散列函数将键映射到存储桶中，以提高数据的访问和查效率。在HashMap中，put()方法用于插入键值对。这里我们将详细介绍put()方法的原理。
HashMap的底层实现是一个由数组加链表或红黑树组成的哈希表。当调用put()方法时，HashMap会首先根据键的hashCode值计算出存储的位置，即确定键值对应的存储桶索引。然后根据该索引到对应的存储桶。
在存储桶中，HashMap采用链表或红黑树来处理哈希冲突。如果存储桶上已经存在元素，HashMap会遍历链表或红黑树，以到要插入的键值对。具体的插入流程如下：
1. 如果存储桶为空，则直接在该位置插入键值对。
2. 如果存储桶上已经存在元素，则需要遍历链表或红黑树。在遍历的过程中，HashMap会比较插入键的hashCode和链表中每个节点的键的hashCode，以判断是否存在相同的键。如果存在相同的键，则会更新对应的值。
3. 如果遍历到链表的末尾（没有到相同的键），则将新的键值对添加到链表的末尾。
4. 如果链表长度达到阈值（默认为8），且HashMap的容量大于64，则将链表转化为红黑树，以提高查的效率。
5. 如果存储桶上已经是一个红黑树，则根据键的hashCode通过红黑树的查操作到要插入的位置，然后插入新节点。
需要注意的是，在插入键值对时，HashMap还会比较键的equals方法来判断两个键是否相等。在遍历链表或红黑树的过程中，如果到了相同的键，则会更新对应的值。
当HashMap的容量超过负载因子和阈值的乘积时，会触发扩容操作。扩容操作会创建一个新的更大的数组，并将原有的键值对重新计算位置插入到新数组中。这是为了保持哈希表的负载因子在指定范围内，避免过多的哈希冲突和链表过长。
总结起来，HashMap的put()方法的原理是根据键的hashCode值计算出存储的位置，然后通过链表或红黑树处理哈希冲突，并根据键的equals方法判断键是否相等。如果存在相同的键，则更新对应的值；否则，在链表或红黑树的末尾添加新的键值对。当存储桶中的链表长
度达到阈值时，将链表转化为红黑树。同时，当HashMap的容量超过阈值时，触发扩容操作，重新计算键值对的位置插入到新的数组中。
参考内容：
- 《深入理解Java集合框架》
- 《Java核心技术卷I》
- 《Effective Java》
- 《数据结构与算法分析》