一HashMap的数据结构
jdk1.8以前是数组链表
jdk1.8以上为数组链表红黑
二数据结构的物理结构
数据逻辑结构在计算机中的存储格式
有两种类型的数据元素存储结构：
顺序存储器结构：在地址连续存储单元中存储数据要素，该数据间的逻辑关系和物理关系一致
链式存储结构：将数据元素存储在任意存储器单元中。 这个组可以连续，也可以不连续。 那么，我们怎么找到它呢？ 可以将指针存储在数据元素的地址中，然后从指针中找到相应的数据元素
两种结构，各有优缺点，可以相互结合运用
HashMap正好用于这两种数据结构
三数组
HashMap的主干数据结构是数组。 也就是说，key通过散列计算将节点对象存储在数组的相应位置。
四链表
然后，如果多个不同的key经过散列计算得到的值相同，则在数组的相应位置存储多个对象的链表，每个对象的属性除了key、value之外，还有next (下一个节点的地址)。
五红黑树
从jdk1.8开始，如果链表长度超过8 (缺省值)，将转为红黑树的保存方式。
六什关于红黑树
1叉搜索树：
1、左子树的所有节点的值都小于等于他的根节点的值
2、右子树的所有节点的值都在他的根节点的值以上
3、左右子树也一定是二叉排序树
接下来是标准的两股搜索树
2均衡的双叉搜索树
首先是二叉搜索树
通过一定的变换保持两侧的平衡
3红黑树
红黑树是二叉搜索树，类似于平衡二叉搜索树，但不是绝对的平衡。
红黑树，是一种平衡的两股锡克树，平衡并不构成“瘸子”，而是指左腿非常长，或者右腿非常长。 除了两股搜索树的特性之外，具体还具有以下特性。
1 .节点为红色或黑色
2 .根节点为黑色
3 .每片叶子的节点是黑色的空节点(NULL )
4 .每个红色节点的两个子节点是黑色的。
5 .从任意节点到该叶的所有路径中都包含相同的黑色节点。
红黑树的搜索效率高于链表