Java8之前是数组+链表
Java8之后是数组+链表+红黑树
HashMap是一个存储key-value键值对的集合，每一个键值对也叫做entry，这些entry分散存储在一个数组中，这个数组也是HashMap的主干，这个数组每个元素的初始值都是null。
数组（键值对entry组成的数组主干）+ 链表（元素太多时为解决哈希冲突数组的一个元素上多个entry组成的链表）+ 红黑树（当链表的元素个数达到8链表存储改为红黑树存储）
无序。
线程不安全。
默认初始长度是16。并且每次自动扩展或是手动初始化时，长度必须是2的幂。
put方法原理：
比如HashMap.put("apple",0)，这时需要利用哈希函数来确定entry的插入位置index，哈希函数算法：index=HashCode（apple） & （Length - 1）。
因为HashMap长度有限，当插入的entry越来越多时，再完美的哈希函数也难免会出现index冲突的情况（哈希冲突），这时就需要用到链表。
HashMap数组的每一个元素上不只有一个entry对象，也是一个链表的头结点。
每一个entry对象通过next指针指向它的下一个entry节点，新来的entry节点插入链表时是头插法插入到链表头结点（也就是数组那个位置）。
之所以把新来的节点插入到头结点是因为HashMap作者认为新来的被查找的可能性更大，这就是HashMap的底层原理。
get方法原理：
比如HashMap.get("apple")，根据key做哈希映射获得index，由于会有哈希冲突的情况，同一个index位置下可能有多个entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。
什么是hashcode？
在Object类中有一个方法:
public native int hashCode();该方法用native修饰，所以是一个本地方法，所谓本地方法就是非java代码，这个代码通常用c或c++写成，在java中可以去调用它。
调用这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的对象地址和内容有关。
元素如何通过hashcode定位到要存储在数组的哪里？
为了实现一个尽量均匀分布的Hash函数，我们通过利用Key的HashCode值来做某种运算。
比如把Key的HashCode值和HashMap长度做取模运算，取模运算的方式固然简单，但是效率很低，因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高。
所以为了实现高效的Hash算法，HashMap的发明者采用了位运算的方式。
这样做不但效果上等同于取模，而且还大大提高了性能。
index= HashCode（Key） & （Length - 1）
数组是有序的，为什么HashMap是无序的？
在做put插入操作时，插入数组位置index不是根据hashcode值决定插入位置，而是hashcode值与HashMap长度减一进行位运算得到的。
index= HashCode（Key） & （Length - 1）
为什么HashMap默认长度是16或者2的幂？
例如计算某key的hashcode，结果为十进制的3029737，二进制的1011100011101011101001，
假设HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111，
进行与运算：index=1011100011101011101001 & 1111 = 1001 ，二进制1001十进制9，所以index=9。
可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。
假设key的hashcode是101110001110101110 1111，HashMap长度是10，Length-1的结果为二进制的1001，
进行与运算：index=101110001110101110 1111 & 1001 = 1001 ，这样的hashcode值并没有产生什么影响，显然不符合Hash算法均匀分布的原则。
反观长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。