HashMap作为java中一个基本的数据结构，经常会在面试中被频繁提起，同时也是程序中经常使用的一个数据结构。

原理

HashMap的主体结构是数组加链表的形式。其中数组位置是通过key的hashcode对数组长度取模来进行定位。当多个key的hashcode相等时，会使用链表进行存储。

HashMap

HashMap有几个有趣的、值得注意的特性：

• 数组的容量总是2^n大小。
• 扩容时，总是扩大一倍。
• 当链表的长度大于8时，会将链表结构转换为红黑树。
• HashMap是非线程安全的，如果出现并发resize可能会产生死循环情况。
• 当使用hashMap.entrySet().iterator()迭代器时，如果中途HashMap结构发生变化，会快速失败，抛出ConcurrentModificationException异常。

put过程

在放置一对key-value（Node）时，主要的操作流程如下：

1. 计算key的hashcode值

为了更好的防止hash冲突，在实际实现中，获取到对象的hashcode后，还会将hashcode与高16位进行按位与运算，减少某些情况下的hash冲突概率。

2.取模计算数组位置

在取模运算中，我们发现实际并不是使用%运算符，而是用的(n - 1) & hashcode。这里也解释了为什么HashMap的大小为什么总是2^n大小，因为在这个大小的数组下，取模运算可以巧妙地转换为位运算，从而提高计算效率。

3.检查该位置的数据状态

• 如果当前位置为空，直接插入即可。
• 否则查看已存在的数据，如果通过equal方法对比key相等，则覆盖旧的value，并返回历史value。
• 如果没有key相等，那么将key-value添加到链表尾部。（实际实现可能和jdk版本和类型有关，包括有头插法和尾插法）

4. 检测数据状态，进行可能的链表转树操作，或者扩容操作。

HashMap触发扩容，是依据扩容阈值来决定扩容时机的。扩容阈值=容量*负载因子。负载因子默认为0.75f。
当链表的长度大于8时，会触发链表转树操作（如果HashMap的容量小于64时，会通过resize代替转树操作）。

get操作

get操作的原理和put中使用的思路一致，就不展开介绍了。