理论：第一章：HashMap底层实现原理，红黑树，B+树，B树的结构原理，volatile关键字，CAS（比较与交换）实现原理

首先HashMap是Map的一个实现类，而Map存储形式是键值对(key,value)的。可以看成是一个一个的Entry。Entry所存放的位置是由key来决定的。

Map中的key是无序的且不可重复的，所有的key可以看成是一个set集合，如果出现Map中的key如果是自定义类的对象，则必须重写hashCode和equals方法，因为如果不重写，使用的是Object类中的hashCode和equals方法，比较的是内存地址值不是比内容。

Map中的value是无序的可重复的，所有的value可以看成是Collection集合，Map中的value如果是自定义类的对象必须重写equals方法。

至于要重写hashCode和equals分别做什么用，拿hashMap底层原理来说：

当我们向HashMap中存放一个元素(k1,v1)，先根据k1的hashCode方法来决定在数组中存放的位置。

如果这个位置没有其它元素，将(k1,v1)直接放入Node类型的数组中，这个数组初始化容量是16，默认的加载因子是0.75，也就是当元素加到12的时候，底层会进行扩容，扩容为原来的2倍。如果该位置已经有其它元素(k2,v2)，那就调用k1的equals方法和k2进行比较二个元素是否相同，如果结果为true，说明二个元素是一样的，用v1替换v2，如果返回值为false，二个元素不一样，就用链表的形式将(k1,v1)存放。

不过当链表中的数据较多时，查询的效率会下降，所以在JDK1.8版本后做了一个升级，hashmap就是当链表中的元素达到8并且元素数量大于64时，会将链表替换成红黑树才会树化时，会将链表替换成红黑树，来提高查找效率。因为对于搜索，插入，删除操作多的情况下，使用红黑树的效率要高一些。

原因是因为红黑树是一种特殊的二叉查找树，二叉查找树所有节点的左子树都小于该节点，所有节点的右子树都大于该节点，就可以通过大小比较关系来进行快速的检索。

在红黑树上插入或者删除一个节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树，可以通过左旋和右旋，使这颗树重新成为红黑树。怕大家搞混，我把二个树之间的区别给上（红黑树与平衡二叉树的区别？https://blog.csdn.net/qfc8930858/article/details/89856274）

在这里插入图片描述

而且像这种二叉树结构比较常见的使用场景是Mysql二种引擎的索引.

首先B树它的每个节点都是Key.value的二元组，它的key都是从左到右递增的排序，value中存储数据。这种模式在读取数据方面的性能很高，因为有单独的索引文件，Myisam 的存储文件有三个.frm是表的结构文件，.MYD是数据文件，.MYI是索引文件。不过Myisam 也有些缺点它只支持表级锁，不支持行级锁也不支持事务，外键等，所以一般用于大数据存储。

更多内容请见原文，原文转载自： https://blog.csdn.net/weixin_44519496/article/details/120592016