HashMap的必知点
- HashMap是无序且不安全的数据结构。
- 存储结构是数组 链表 红黑树 (阈值为8 如果链表长度>=8则会把链表变成红黑树 )，数组中存储元素Entry，存储元素的位置被称为桶，每个bucket有且仅有一个元素并指定索引，以实现快速访问。
- HashMap 是以key–value对的形式存储的，key值是唯一的（可以为null），一个key只能对应着一个value，但是value是可以重复的。
- HashMap 如果再次添加相同的key值，它会覆盖key值所对应的内容，这也是与HashSet不同的一点，Set通过add添加相同的对象，不会再添加到Set中去。
- HashMap 提供了get方法，通过key值取对应的value值，但是HashSet只能通过迭代器Iterator来遍历数据，找对象。
HashMap的新特性
- jdk8中添加了红黑树，当链表长度大于等于8的时候链表会变成红黑树
- 链表新节点插入链表的顺序不同（jdk7是插入头结点，jdk8因为要把链表变为红 黑树所以采用插入尾节点）
- resize的逻辑修改（jdk7会出现死循环，jdk8不会）
HashMap为什么引入红黑树
为了解决jdk1.8以前hash冲突所导致的链化严重的问题，因为链表结构的查询效率是非常低的（O(n)），树结构的查询效率会高一些。
重写hashCode()和equals()方法
HashMap可以提供快速访问能力，即通过key可以查询到相应的value,通过哈希函数可以决定键值对的位置，在理想状况下（不出现hash冲突），查询的时间复杂度为O(1),当出现hash冲突时，使用开散列表解决冲突，对应一个特定hash值的位置存储的是一个链表头，指向hash到同一个位置的多个键值对组成的链表。
HashMap的数据存储
HashMap的数据是存在Node[] table数组(哈希桶)中的，它是一个Entry数组，Entry是HashMap的一个静态内部类。Entry封装了hash（定位数组索引位置）、key、value，next是指向链表的下一个Node节点。
Map及Map.Entry
Map.Entry是Map的一个内部接口。
Map.Entry的常用方法：
- keySet()方法返回值是Map中key值的集合
- entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry。
HashMap的put方法
HashMap put方法存储流程
引用美团技术团队的图片：
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； ②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③； ③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； ④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； ⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可； ⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
HashMap解决hash冲突（碰撞）
不同的对象具有不同的hash值，当两个不同的对象计算出的hash值相同时便产生了hash冲突,HashMap使用数组 链表(链地址法)解决hash冲突。
代码语言：javascript复制map.put("key1","value1");
map.put("key 2","value 2");
...
map.put("hashCode n","value n");调用map的put方法进行数据存储时，首先根据key计算其hashCode,然后进行取模运算和高位运算来确定value的存储位置，在后期的调用put方法时不同的key计算得到的位置可能是一样的，这时会产生hash碰撞。
HashMap扩容
HashMap的容量与扩容机制
在HashMap其中一个构造函数中，可以指定HashMap的初始容量和负载因子，这两个变量关系到HashMap的扩容。
- 负载因子是一个和扩容机制有关的值，阈值(threshold) = 负载因子(loadFactor) x 容量(capacity) ，负载因子是0.75这是时间和空间的权衡。负载因子越大，Hash冲突的可能性就更大，负载因子越小，相同的数据，HashMap扩容的次数就越多，需要的空间就越大。
- 阈值则指定了HashMap的最大容量（容纳key-value的极限值）。
扩容条件
比如说当前的默认容器容量是16，负载因子是0.75,16*0.75=12，也就是说，容器中超过12个元素的时候就会进行扩容操作。HashMap以2的整数次幂扩容。
明确参数
- bin:bucket，数组中存储Entry位置
- MAXIMUM_CAPACITY：最大容量（2的30次幂，1073741824）
- DEFAULT_LOAD_FACTOR：负载因子（默认0.75）
- TREEIFY_THRESHOLD: 链表转红黑树阈值
- DEFAULT_INITIAL_CAPACITY：默认初始容量（2的4次幂16）
1.This map usually acts as a binned (bucketed) hash table 2.static final int MAXIMUM_CAPACITY = 1 << 30; 3.static final float DEFAULT_LOAD_FACTOR = 0.75f; 4.static final int UNTREEIFY_THRESHOLD = 6; 5.static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
resize源码：
代码语言：javascript复制 final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果当前长度大于最大容器长度（2的30次幂 1073741824则直接返回该对象，1073741824是极限长容量
//static final int MAXIMUM_CAPACITY = 1 << 30;
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果当前长度小于最大容量且小于默认容量16，对原数据进行2倍扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//计算resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 把每个bucket都移动到扩容后的buckets中
for (int j = 0; j < oldCap; j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//省略移动bucket部分代码
...
}
return newTab;
}参考文献：
美团技术网站：Java 8系列之重新认识HashMap
