HashMap底层
在jdk1.8之前，HashMap底层是基于数组和链表实现
在jdk1.8后，HashMap底层基于数组+链表+红黑树实现
原因是随着数据量的不断增加，出现hash碰撞的概率大幅上升，此时会形成一个很长的线性链表，导致数据结构线性化严重，效率随之降低。因此在jdk1.8引入了红黑树（当数组大小超过64，链表节点超过8个，底层会自动将链表结构转为红黑树结构，下面会详细分析数组、链表、红黑树的创建时机和创建规则）
1.1数组的作用是什么？什么时候会创建数组？
数组本质上就是用来存储键值对的，当我们首次调用put方法时，会创建一个默认长度为16，加载因子为0.75的数组。
1.2链表的作用是什么？什么时候会创建链表？
HashMap存储数据时，是通过hash(key) 方法计算出key的哈希值，再将次哈希值和数组最大索引进行位运算，得到一个小于等于最大索引的值（这里的二级制位运算可以保证计算的索引值一定是小于等于数组的最大索引，确保了不会出现索引越界）。了解了获取索引的方式，那么就要来看看key的哈希值！！我们都知道，不同的key，可能会存在相同的hash值，那么此时就会出现哈希冲突（计算出来的数组索引位置处已经有key-V的数据存在了）。此时就需要判断本次新增数据的key，是否与原本的key一致（相当于调用hash+equal方法比较key），如果不一致，此时会创建一个链表，将本次的数据以链表的形式，挂载在当前索引下。总结一下，就是当出现hash冲突时，并且两个key不一致，会创建链表。
1.3红黑树的作用是什么？什么时候会创建？
在上面介绍过，当数据量很大时，hash冲突会越来越多，会导致线性的长链表。当链表节点超过8个，底层会将链表转为红黑树。
1.4数组扩容为什么是2倍？
这个问题，其实和hash值与最大索引位运算得到索引值有异曲同工之妙。举个例子，当前数组长度是16，2倍扩容后就是32，那么最大索引就是32-1=31，对应二进制0001 1111，仔细观察，不论哈希值是多少，与0001 1111进行与位运算，得到的值一定是小于等于31的，这样就保证了不会出现索引越界。
2.1关于put方法
2.1.1 根据key进行哈希运算 得到哈希值
底层会将key作为参数，调用hash(key)方法，计算出一个int类型的哈希值（底层在计算时，还会与运算h>>>16，将哈希值散列，尽量避免哈希冲突）
2.1.2 创建默认数组
首次会默认创建一个长度为16，加载因子为0.75的数组。
2.1.3 哈希值与数组最大索引进行与运算
哈希值与数组最大索引进行与运算，得到一个小于等于最大索引的值，这个值就是数据存储到数组的索引
2.1.4 判断与运算结果，是否出现hash冲突
如果上面计算的索引处，已经有值，那么久出现了哈希冲突。此时我们需要去判断key是否真的一致，那就是hash+equal方法比较key。如果key一致，那么覆盖原有的数据，如果key不一致，此时就会做链表挂载或者红黑树新增节点
2.1.5 出现哈希冲突，存在的是链表还是红黑树，如果是链表判断是否需要转为红黑树
这里到底是挂载链表还是新增红黑树节点，取决于目前的数据结构（没有达到转红黑树条件时，都是链表）。如果当前是链表挂载，需要判断当前挂载完成后，长度是否超过8，以此来判断是否需要转为红黑树。
2.1.6 判断是否需要数组扩容
如果当前数据没有产生哈希冲突，那么需要考虑到数组的扩容问题。例如当前数组长度是16，本次数据保存后，数组被使用的长度是否超过12，如果超过，就进行两倍扩容。
当然，在我们日常使用中，可能没有去在意底层的一些执行逻辑，有兴趣的同学可以看看源码。关于get方法，我们下次再聊。
以上是作者对HashMap底层的一些看法，有不对或者不严谨的地方，希望大家多多指正。
本文转载自: 掘金