Java面试必问：HashMap底层原理详解

HashMap是Java开发中最常用的集合之一，也是面试中的高频考点。这篇文章主要记录我对HashMap底层原理的理解。

HashMap的底层数据结构是数组加链表加红黑树。数组默认长度是16，每个位置叫一个“桶”。当多个元素hash到同一个桶时，会用链表把它们串起来。当链表长度超过8，并且数组长度超过64时，链表会转成红黑树，这样查询效率更高。如果链表长度超过8但数组长度还不到64，HashMap会优先扩容，而不是转树。

再说说put方法的执行流程。首先计算key的hash值，然后通过哈希值找到数组下标。如果那个位置是空的，就直接把元素放进去。如果不为空，就遍历链表，看看有没有相同的key，有就覆盖旧值，没有就挂到链表尾部。

get方法相对简单一些。同样是先计算hash值找到数组下标，然后遍历该位置的链表或红黑树，找到key相同的节点，返回对应的value。如果没找到就返回null。

最后说一下扩容机制。HashMap默认的负载因子是0.75，当数组中的元素个数超过数组长度的四分之三时，就会触发扩容。数组长度会扩容为原来的2倍，然后所有元素重新计算位置。

顺便补充一点：HashMap允许key和value为null，但ConcurrentHashMap和Hashtable都不允许。另外，HashMap是线程不安全的，多线程环境下要用ConcurrentHashMap。