HashMap实现原理

? ? ? ? JDK1.7的时候HashMap的底层是数组加链表，JDK1.8之后HashMap是由数组、链表、红黑树组成的，引入红黑树是为了当链表的长度过长时会把链表转变成红黑树，以提高查询效率。

? ? ? ? 首先，HashMap中存放的是无序不重复的key-value，HashMap获取到传过来的key,通过hash算法获得对应的hash值，获取到hash值之后调用indexFor方法，通过获取到的hash值以及数组的长度算出数组的下标（把哈希值和数组容量转换为二进制，再再数组容量范围内与哈希值进行再一次运算，同为1则1，不然则为0，得出数组的下标值，这样可以保证计算出的数组下标不会大于当前数组容量）。然后把传过来的key和value存到该数组下标当中，如果该数组下标下已经有值了，则使用链表，JDK7是把新元素添加到头部节点JDK8添加到尾部节点。