HashMap源码分析

HashMap由数组和链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的。Java 8开始HashMap的实现是综合利用了数组、链表与红黑树。

如果定位到的数组位置不含链表，那么查找、添加等操作很快，仅需一次寻址即可，其时间复杂度为O(1)；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)——首先遍历链表，存在即覆盖，不存在则新增；对于查找操作来讲，仍需要遍历链表，然后通过key对象的equals方法逐一对比查找。从性能上考虑，HashMap中的链表出现越少，即哈希冲突越少，性能也就越好。所以，在日常编码中，可以使用HashMap存取键值映射关系。

Links

• https://zhuanlan.zhihu.com/p/79219960 HashMap源码分析（jdk1.8，保证你能看懂）

• https://zhuanlan.zhihu.com/p/21673805 Java 8系列之重新认识HashMap

• hashmap-changes-in-java-8/