HashMap主要用来存放键值对，它基于哈希表的Map接口实现，是常用的java集合之一，是非线程安全的。

 

HashMap可以存储null的key和value，但null作为键只能存在一个，作为值则可有多个。

 

jdk1.7 底层使用数组+链表的方式实现，每次插入使用的是头插法。

数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。

jdk1.8 底层使用数组+链表+红黑树的方式实现，每次使用的是尾插法。

引入红黑树的目的是避免单条链表长度过长而影响查询效率

jdk8解决冲突：当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

 

HashMap默认的初始大小为16，之后每次扩容会变成原来的2倍。、

 

jdk1.8之前，HashMap底层是数组和链表结合在一起使用也就是链表散列。这样结合了链表在增删方面的高效和数组在寻址方面的优势。

hashmap结构：数组+链表，数组默认长度是16，注意hashtable数组的默认长度是11（可以自动变长。构造HashMap的时候也可以指定长度），数组中每个元素存储的是一个链表的头节点，链表的节点由key、value和next组成，next指向下一个节点。

     HashMap通过key的hashCode经过hash方法处理过后（减少碰撞）得到hash值，接着hash(key) & (len-1)，也就是元素的key的hash值对数组长度进行位运算得到存放位置索引值，然后判断该位置是否有元素，如果没有则直接添加，如果有则先判断元素的hash值以及key是否相同，如果相等直接替换，如果不相等则进行“拉链”， 链表中如果有相同则不添加，如果没有则添加到链表尾部。

    这就是所谓的“拉链法”，将数组和链表结合，数组的每一格就是一个链表。遇到hash冲突时将冲突的值加到链表中即可。

     jdk8之后解决hash冲突问题有了较大的变化。增加了红黑树。

    按照“拉链”的判断方法将元素添加到链表尾部时，会立即判断当前链表长度是否达到阈值（默认为8），达到阈值首先会调用 treeifyBin() 方法。这个方法根据hashMap数组来决定是否转化为红黑树，只有当数组长度大于或等于64的情况下，才会执行树化操作，减少搜索时间；如果小于64就会先对数组扩容调用 resize() 方法，调用这个方法会对hashMap中的元素进行重新散列hash。