先决条件：
主要数据结构：
数据结构具有用于实现数据存储的数组和链表，但基本上是两个极端。
数组存储器区间连续，存储器的消耗量大，因此区域复杂且大。 但序列二分搜索时间复杂度小，为o(1)； 数组的特点是寻址容易，插入和删除困难
链表存储区间离散，占用内存相对较松，空间复杂度小，但时间复杂度达到o(n )。链表的特点是寻址困难，易于插入和删除。
在哈希表中，可以综合两者的特性，创建容易寻址、也容易插入删除的数据结构吗？ 答案是肯定的。 这就是我们提到的哈希表。 散列表(Hash table )便于检索数据，同时很少占用内容空间，使用方便。
散列表有几种不同的实现方法，我接下来要说明的是最常用的方法——拉链法。 可以理解为“链表的数组”。 图：
二叉树：对一个相对平衡的二叉树进行插入、搜索和删除操作，平均复杂度均为o(logn )。
HashMap的数据结构：HashMap是用数组链表红黑树(JDK1.8中添加红黑树部分)实现的散列表和红黑树。
结构：首先，每个元素都是链表，有可能无法准确表示的数组。 添加元素" key-value "时，首先计算元素key的散列值，以确定其插入数组的位置。 但是，由于可能存在相同散列值的元素已经位于数组中的同一位置，因此添加到相同散列值的元素之后，并且可能位于数组中的同一位置。如果链表长度过长，链表将转换为红黑树，从而大大提高了搜索效率
如果链表数组的容量超过初始容量0.75，则重新散列会将链表数组放大两倍，并将原始链表数组的移动到新数组中
参考：
33559 www.cn blogs.com/holy shengjie/p/6500463.html
3359 blog.csdn.net/tuke _ tuke/article/details/51588156