文
章
目
录
章
目
录
Java面试题：请你解释下HashMap的底层原理
得分点:
数据结构、put()流程、扩容机制
标准回答:
在Java 8中，HashMap底层数据结构是基于”数组+链表+红黑树”的组合来实现的。
数据结构
HashMap的底层数据结构包括数组、链表和红黑树。HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上。当链表长度达到一定阈值（默认是8）时，链表会转化为红黑树，以提高查找效率。
put()流程
在向HashMap中插入元素时，put()方法的执行过程包括以下步骤：
- 首先，计算键的哈希值，然后根据哈希值找到对应的槽位。
- 如果槽位为空，直接将键值对存入槽位。
- 如果槽位不为空，可能存在三种情况：
- 如果键已经存在于槽位的头节点上，直接更新该键对应的值。
- 如果槽位已经是红黑树节点，将键值对插入红黑树。
- 如果槽位是链表节点，将键值对插入链表的尾部。如果链表长度达到阈值（默认是8），则可能会触发链表转换为红黑树的操作。
- 插入完成后，会检查是否需要扩容。如果元素数量超过了容量的阈值（默认容量的0.75倍），则会触发扩容操作，将容量翻倍，并重新将元素分布到新的槽位中。
扩容机制
扩容是为了保证HashMap的负载因子在一个可接受的范围内，通常默认为0.75。当元素数量达到容量的0.75倍时，HashMap会自动触发扩容操作。扩容过程包括以下步骤：
- 创建一个新的数组，其容量是原数组的2倍。
- 遍历原数组中的每个槽位，将其中的元素重新分布到新数组的槽位中。
- 扩容后，新数组会取代旧数组成为HashMap的底层数据结构。
HashMap通过扩容机制来避免数据存储冲突，并且保证了查找、插入和删除的高效性。
需要注意的是，HashMap是非线程安全的，如果在多线程环境中使用，需要采取额外的同步措施，或者使用线程安全的ConcurrentHashMap。
