JDK1.8之前的HashMap
在JDK1.8之前，HashMap通过散列表(哈希表)实现，并且散列表冲突解决方案是链地址法(拉链法)，也可理解为数组+链表实现。
在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
什么是散列表？
一块连续的存储空间中，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
重温数据结构_散列表/哈希表的查找
向HashMap存储元素：
向HashMap中存储某元素时候，首先hash算法根据元素的key值得到一个hash值，这个hash值就可以确定元素在数组中的位置。如果此位置没有元素，直接存；如果已经存在元素，就要与它们的key进行比较，有以下两种情况：1.key相同的，覆盖旧值；2.key都不同，形成一个以新元素为头部的链表。
从HashMap获取元素：
先根据key的hash算法得到hash值，找到该元素在数组中的位置；再通过key的equals方法，在链表中找到对应的元素，也就找到了key对应的value。
JDK1.8的HashMap
HashMap通过数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，并且再次之后都用红黑树来存储冲突的元素。
为什么JDK1.8HashMap要做如此改变？
我们都知道在链表中查找节点时，会花费O（n）的查找时间。为了防止拉链过长，导致严重影响HashMap的性能，当链表长度超过阈值（8）时，不再采用单链表形式存储，而是采用红黑树存储，利用红黑树快速增删改查的特点提高HashMap的性能。
JDK1.8 HashMap源码分析
重要的字段
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K, V>[] table;
/**
* The number of key-value mappings contained in this map.
* 包含在map中键-值对的数量
*/
transient int size;
/**
* hashmap被结构化改变的次数
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
* 扩容的阈值，当size大于这个值时，table数组进行扩容
*/
int threshold;
/**
* The load factor for the hash table.
*
*/
float loadFactor;
对这些重要字段的解释：
- table：Node[] table的初始化长度length默认值是16；
- loadFactor ：负载因子默认值是0.75；
- threshold ：是HashMap所能容纳的最大数量的Node(键值对)个数。
负载因子的定义公式：threshold = length * loadFactor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
当size超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
- size：包含在map中键-值对的实际数量。注意和table的长度length、容纳最大键值对数量threshold的区别。
- modCount：主要用来记录HashMap内部结构发生变化的次数。需要注意的是内部结构发生变化真正意义是元素的key从来没有被put过。
如何确定key对应哈希桶数组索引位置？
通过这个Java方法运算来获取hash码值：
static final int hash(Object key) {
int h;
//取key的hashCode值、高位运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
通过hash方法得到的hash码值，还不是数组的下标编号，还差一步，这一步就是hash码值对数组长度进行取模运算，具体代码如下图红框。
下图是得到key在数组具体位置索引号的过程：
### 重要方法分析
#### 静态内部类Node
Node是HashMap的一个静态内部类，实现了Map.Entry接口，表示一个映射条目或者说是键值对。
static class Node<K,V> implements Map.Entry<K,V> {
//根据hash方法计算出来的值，作为定位数组位置的索引
final int hash;
final K key;
V value;
Node<K,V> next;//该Node指向的下一个Node
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
HashMap的put方法实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
