前言HashMap是Java中最常用的集合类框架，也是Java语言中非常典型的一种数据结构。必须问的问题之一；今天我们就来讲解分析下，HashMap底层实现原理分析常见的三种数据结构：数组结构，链表结构，哈希表结构1.数组结构的存储区间是连续的，占用内存严重，空间复杂度也很大，时间复杂度为O(1)。优点：随机读效率很高，因为数组是连续的（随机访问强，查找速度快）。缺点：插入和删除数据的效率较低。因为插入数据，这个位置后面的数据在内存中必须要后移，而且大小是固定的，不容易动态扩展。2、链表结构的范围离散，内存松散，空间复杂度小，时间复杂度为O(N)。优点：插入删除速度快，内存利用率高，无固定大小，扩展灵活。缺点：不能随机查找，每次都从第一个开始遍历（查询效率低）。3、哈希表结构结合了数组结构和链表结构的优点，实现了查询和修改效率高，插入和删除效率高的数据结构。常见的HashMap就是这样一种数据结构4.HashMapput()和get()的实现原理：①、map.put(k,v)实现原理(1)首先将k、v封装成Node对象(节点)。(2)然后它的底层会调用K的hashCode()方法获取hash值。(3)通过哈希表函数/哈希算法，将哈希值转换为数组的下标。如果下标位置没有元素，则在该位置添加Node。如果下标对应的位置存在链表。此时，需要k和链表上每个节点的k执行相等。如果所有的equals方法都返回false，那么这个新节点将被添加到链表的末尾。如果其中一个equals返回true，则该节点的值将被覆盖。②、map.get(k)实现原理(1)首先调用k的hashCode()方法获取hash值，通过hash算法转换为数组的下标。(2)上一步通过hash算法转换为数组下标后，通过数组下标快速定位到某个位置。如果此位置没有任何内容，则返回null。如果该位置存在单向链表，则对K和单向链表上每个节点的K进行equals。如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K执行equals返回true，那么这个节点的值就是我们此时要找的值，get方法最终返回的就是我们要找的值。5、为什么随机增删改查效率这么高？原因：增删改查都是在链表上进行，查询只需要扫描一部分，效率高。HashMap集合的key会依次调用两个方法，hashCode和equals方法，这两个方法都需要重写。6、为什么hashMap集合中放在key部分的元素需要重写equals方法？因为equals方法默认比较的是两个对象的内存地址。8最重要的是介绍一下红黑树的设计。当哈希表的单链表长度超过8时，链表结构将转为红黑树结构。为什么要这样设计？好处是避免链表在最极端的情况下变得很长，查询的时候效率会很慢。红黑树查询：其访问性能类似于半查找，时间复杂度O(logn)；链表查询：此时需要遍历所有元素，时间复杂度O(n)；简单的说，红黑树是一种近似平衡的二叉查找树。它的主要优点是“平衡”，即左右子树的高度几乎相同，从而防止树退化为链表。这样就保证了查找的时间复杂度为log(n)。关于红黑树的内容，网上给出的内容很多，主要有以下几个特点：每个结点不是红就是黑，但是根结点永远是黑的；每个红色节点的两个子节点必须都是黑色的；红色节点不能是连续的（也就是说，红色节点的子节点和父节点都不能是红色的）；从任何节点到其子树中每个叶节点的路径包含相同数量的黑色节点；all叶子节点全黑（注意叶子节点其实就是上图中的NIL节点）；当树的结构发生变化（插入或删除操作）时，往往会破坏上述条件3或条件4，需要调整搜索树再次满足红黑树的条件；
