概念
HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null键和null值，因为key不允许重复，因此只能有一个键为null，HashMap不能保证放入元素的顺序，它是无序的，和放入的顺序并不能相同。HashMap是线程不安全的。
注：有序存储键值对数据时，可以使用 LinkedHashMap；要保证线程安全时，可以使用 ConcurrentHashMap。
实现机制
HashMap由数组和链表来实现对数据的存储。HashMap采用Entry数组来存储键值对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。
- 数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：查找容易，插入和删除困难。
- 链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O(N)。链表的特点是：查找困难，插入和删除容易。
注：HashMap 里面实现一个静态内部类 Entry，其重要的属性有 hash，key，value，next。
HashMap 存储规则：每个元素存储的是一个链表的头结点。那么一个长度16的数组中，元素是按照什么规则存放到数组中呢。是通过元素的 key 的哈希值（key 的 hashcode 进行二次 hash）对数组长度 - 1的位运算得到存储位置的下标。比如哈希值8（8 & (16 - 1) = 8）、12（12 & (16 - 1) = 12）、40（40 & (16 - 1) = 8）、140（140 & (16 - 1) = 12），所以8和40存储在数组下标为8的位置；12和140存储在数组下标为12的位置。
HashMap 链式数据结构：Entry 类中有一个 next 属性，指向下一个 Entry。比如第一个键值对A进来，通过计算其 key 的 hash 得到的index = 0，记做：Entry[0] = A；此时又有一个键值对B进来，通过计算得到的index也等于0，此时 HashMap 会使得Entry[0] = B，B.next = A；若这时又进来一个键值对C，同样的index等于0，此时 HashMap 会使得Entry[0] = C，C.next = B；index = 0的位置存储了A、B、C三个键值对，它们之间通过 next 这个属性链接在一起，所以数组中存储的是最后插入的元素，先插入的元素终会被放到Entry链的尾部，这里你也就明白为什么 HashMap 是无序的了吧。
扩容机制
添加元素时，会判断当前元素个数，当大于等于阈值（数组的长度 * 加载因子的值）时，就会自动扩容。扩容就是重新计算容量，但是
Java中数组是无法自动扩容的，所以需要新的数组代替已有的容量小的数组。
比如长度为16的数组，加载因子为0.75，则阈值为 16 * 0.75 = 12，也就是说当元素个数达到12，在添加第13个元素时会进行扩容。即 16 * 2 = 32，那么扩容后的容量是32。这里先抛出一个问题，为什么每次扩容都在原有容量乘以2，继续往下看。
注：HashMap 使用的是懒加载，构造完 HashMap 对象后，只要不进行 put 方法插入元素之前，HashMap 并不会去初始化或者扩容。
问题：为什么容量大小为2的n次幂效率最好？
| & 1111 | 8 | 9 | 8 | 9 |
|---|---|---|---|---|
| hashcode值 | 1 0 0 0 | 1 0 0 1 | 1 0 0 0 | 1 0 0 1 |
| 数组长度 - 1 | 1 1 1 1 | 1 1 1 1 | 1 1 1 0 | 1 1 1 0 |
| 结果 | 1 0 0 0 | 1 0 0 1 | 1 0 0 0 | 1 0 0 0 |
如上表，左边两组是数组长度为16(2的4次幂)，右边两组是数组长度为15。两组的 hashcode 均为8 和 9，然而与 1110 做位运算时，产生相同的结果，也是会存储到数组的同一个位置上，这就产生了碰撞，8 和 9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，降低了查询的效率。我们还可以发现，当数组长度为15的时候，hashcode 的值会与14（1110）进行位运算，最后一位永远是0，那 0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素，浪费空间。数组可使用的位置比数组长度小很多，这样会增加碰撞的几率，减慢查询的效率。
数组长度为2的n次幂的时候，不同的
key算得的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了，所以在存储大容量数据时，最好预先指定容量大小为2的n次幂（其实不指定为2的n次幂的话，HashMap也会以大于且最接近指定值大小的2的n次幂进行初始化），也解释了上面问题，为什么HashMap每次扩容都在原有容量上乘以2。
扩容是一个特别耗性能的操作，所以在使用 HashMap 的时候，估算 map 的大小，初始化的时候给一个大致的数值，避免 map 进行频繁的扩容。那么这个数值多少才是最合适的值呢，下面看一个例子。
例：假如有1000个元素需要存储到 HashMap 中，那么根据上面提到的容量大小为2的n次幂效率最好，那么 new HashMap(1024) 是比较合适的，但是上面也提到了，当存储元素达到阈值时，HashMap 会进行扩容，那么1024 * 0.75 < 1000，所以为了不进行扩展，需要size * 0.75 > 1000，那么可以得出 new HashMap(2048) 才是最合适的。
重写 hashcode 和 equals 方法
疑问：为什么要重写 hashcode 和 equals 方法？
根据上面介绍，我们知道想查找某个元素，就需要先获取其所在位置，那么首先计算 key 的 hashcode，找到其在数组中对应的位置，然后通过 key 的 equals 方法在对应位置的链表中找到元素。因此 hashcode 与 equals 方法对于找到对应元素是两个关键方法。
重写 equals 方法需要满足三个条件：
- 自反性：a.equals(a) == true。
- 对称性：a.equals(b) == true时，b.equals(a) 也为 true。
- 传递性：a.equals(b) == true时，且b.equals(c) == true，那么 a.equals(c) 也要为 true。
JDK 1.8 优化
以上都是基于
JDK 1.7进行分析的，JDK 1.8在HashMap实现方式上做了一些优化。数据结构的存储由数组+链表的方式，变化为数组+链表+红黑树的存储方式，当链表长度超过阈值（8）时，将链表转换为红黑树。性能上有了提升。
