hashMap是基于哈希表的Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是他不保证顺序的恒久不变。
在java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针(引用)，所有的数据结构都可以用这两个基本结构来构造的，HashMap 也不例外。HashMap实际上是一个 “链表散列” 的数据结构，即数组和链表的结合体。
HashMap底层就是一个数组结构，数组的每一项又是一个链表，当新建一个HashMap 的时候，就会初始化一个数组。
代码语言：javascript复制transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
} 可以看出，Entry就是数组中的元素，每个Map.Entry其实就是一个 key-value对，它持有一个指向下一个元素的引用，这就构成了链表。
对于HashMap，HashSet来说，他们采用hash 算法来决定 Map中 key的存储，并通过hash算法来增加key 集合 的大小。 hash表中可以存储元素的位置被称为 “桶(bucket)”，在通常情况下，单个“桶”里存储一个元素，此时有最好的性能；hash 算法可以根据 hashCode 值计算出"桶"的存储位置（hashCode()的具体解释请看我篇博客），接着从桶中取出元素。但hash 表的状态是 open的：在发生 “hash” 冲突的情况下，单个桶 会存储多个元素，这些元素以链表形式存储，如下图。
其中的参数
- Capacity(容量)：Capacity 就是 bucket的大小，指的也就是HashMap集合初始化的时候自身的容量。可以在构造方法中指定；如果不指定的话，总容量默认值为16.需要注意的是初始容量必须是2的幂次方。
- loadfactor(负载因子)：Load factor就是bucket填满程度的最大比例。负责因子可以通过构造方法中指定，当 HashMap的总容量到达一定值的时候，HashMap会实施扩容，，默认值为0.75.也就是说，比如你现在有一个 HashMap 的初始容量为10，那么扩容的阈值就是0.75*10=7.5，也就是说，在你打算存入第8个值得时候，HashMap 会先执行扩容。
- threshold: 扩容阈值，即扩容阈值=HashMap 总容量*负载因子，当前 HashMao 的容量大于或等于扩容阈值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。
- size(尺寸)：当前 hash 表中记录的数量
- initial capacity(初始化容量)：创建hash表时桶的数量，可以在构造器中指定初始化容量。
我们先看看它的 put 方法
- 对key的hashCode() 做hash,然后在计算index
- 如果没有冲突，则则直接放到bucket(桶)里，
- 如果冲突了，以链表的形式存在buckets后
- 如果冲突添加后导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树
- 如果节点已经存在就替换 old value（保证key的唯一性）
- 如果bucket满了（超过 负载因子），就要resize（扩容）
public V put(K key, V value) {
//对key的hashCode() 做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//计算index,并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断如果节点存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//该链为树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//该链为链表
else {
for (int binCount = 0; ; binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//写入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
modCount;
//超过 load factor*current capacity(负载因子*hashmap容量)，resize
if ( size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
接着来看它的get()方法
代码语言：javascript复制bucket里的第一个节点，直接命中 如果有冲突，则通过 key.equals(k) 去查找对应的 entry
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//未命中
if ((e = first.next) != null) {
//在树中找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//在链表中找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}在获取 HashMap 的元素时，基本分两步：
- 首先根据hashCode()做hash,然后确定 bucket 的 index
- 如果bucket 的节点的key 不是我们需要的，则通过key.equals()在链中找。在Java8 之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是 O(1) O(n).因此，当碰撞很厉害的时候，n很大，O(n)的速度显示是影响速度的。因此在Java8中，利用红黑树替换链表，这样复杂符就变成了了 O(1) O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题。
接下来对一些问题进行总结：
1. 什么时候会使用HashMap？他有什么特点？ 是基于Map接口的实现，存储键值对时，它可以接收null的键值，是非同步的，HashMap存储着Entry(hash, key, value, next)对象。 2. 你知道HashMap的工作原理吗？ 通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过
Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。 3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？ 通过对key的hashCode()进行hashing，并计算下标((n-1) & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点 4. 你知道hash的实现吗？为什么要这样实现？ 在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。 5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？ 如果超过了负载因子(默认0.75)，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法
