HashMap的底层结构以JDK1.8为一个分界线，JDK1.8之前和JDK1.8及之后的底层结构稍有不同，下面分别以JDK1.7和JDK1.8为例来介绍HashMap的底层实现。

JDK1.7中HashMap

底层结构

HashMap底层是一个数组table，数组中的每一项都是一个Entry，Entry是一个K-V对，我们所存入的键值对全都存放在Entry中。数组table的每个位置我们常称为一个桶，每个桶可能会对应多个Entry，多个Entry以链表的形式连接，此结构我们称为数组+链表结构。如下图所示：

数组中每个位置上可能有0个、1个或多个Entry元素，这个取决于根据hash映射结果算出来的键值对在数组中的下标，若多个键值对下标相同，那么以链表的形式组织。JDK1.7使用的hash映射方法如下所示。

hash映射

计算Entry在数组中的下标时分两步：

1.计算key的哈希值；

	final int hash(Object k) {int h = 0;h ^= k.hashCode();h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4)