前言
前面分别分析了常用的 ArrayList 和 LinkedList 的源码，前面讲了 ArrayList 内部是使用数组实现的，LinkedList 内部是使用双向链表实现的，而作为我们也经常使用的 HashMap，内部是使用数组+单链表实现的，可以通过数组的寻址快的特性定位哈希桶的位置，然后利用链表插入和删除效率高的特性操控元素，当超过单链表的节点超过 8 个的时候，转成红黑树，具体的实现往下看。
HashMap 简介
还是从 Api 权威介绍开始：
image
HashMap 的继承实现关系相对比较简单，继承于 AbstractMap 实现了 Map 接口、Cloneable接口、Serializable接口。
HashMap 是基于哈希表的的实现了 Map 接口，这个实现提供了所有可选的 map 的操作。并且允许键值对均为 null，(HashMap 除了允许 null 和线程不同步以外，和 HashTable 大致上是相同的。这个类不保证map内部元素的顺序，不能保证顺序随着时间变化而不变，意思就是可能随着时间变化，顺序也会发生变化。
HashMap 的一些特点：
- 允许key 为 null ，value 为 null
- key 不可以重复，value 可以重复
- 内部是以数组+单链表实现的，JDK8 以后加入了红黑树
- 内部键值对的存储是无序的，而且顺序会在扩容时改变
- 初始容量为 16，负载因子为 0.75，也就是当容量达到 容量*负载因子 的时候会扩容，一次扩容增加一倍。
- 内部的键值对要重写 key 对象重写 hashCode 方法、equals 方法。
- 线程不安全的，如果想要线程安全，有三种方法
- Hashtable 不允许key 为 null，内部使用个 Synchronized 关键字实现线程安全
- ConcurrentHashMap java 并发包下的一个线程安全的 HashMap
- SynchronizedMap 使用 Collections.synchronizedMap(new HashMap<>()); 来获得一个线程安全的 HashMap,SynchronizedMap内部也是使用的 Synchronized 实现线程安全的
下面从源码的角度来分析下 HashMap。
HashMap 源码分析
一些变量和常量
public class HashMap<K, V> extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {
// 默认初始容量：16，必须是 2 的整数次方 ， 1 << 4 相当于 1* 2的四次方 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量 2 的 30 次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表树化边界值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换链表的阀值 ，小于 6 的时候，红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 容器可以树化的最小容量，
static final int MIN_TREEIFY_CAPACITY = 64;
// 序列化 id
private static final long serialVersionUID = 362498820763181265L;
// 加载因子，可以作为决定扩容的一个因子
final float loadFactor;
// 哈希数组，也叫做哈希桶
transient Node<K, V>[] table;
//缓存的键值对集合 ， keySet() 和 values() 声明在 AbstractMap 中
transient Set<Map.Entry<K, V>> entrySet;
// 目前 hashmap 的大小
transient int size;
// 当前 HashMap 修改的次数，这个变量用来保证 fail-fast 机制
transient int modCount;
// 扩容边界值，threshold = 容量(table.length) * 负载因子(loadFactor)
int threshold;
}
构造方法
// 创建一个有初始容量和自定义负载因子的 HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 根据初始容量和负载因子计算阈值
this.threshold = tableSizeFor(initialCapacity);
}
// 创建一个有初始容量的 HashMap
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// 构造一个空的 HashMap
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 根据传入的 Map 创建一个新的 HashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
在第四个构造方法里面调用了 putMapEntries ：
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 拿到传入 Map 的大小
int s = m.size();
if (s > 0) {
// 如果 table==null 说明未创建哈希桶
if (table == null) { // pre-size
// 因为传入了 s 个键值对，所以需要的容量就是 s / loadFactor ，为了不触发扩容，多加了 1，
float ft = ((float) s / loadFactor) + 1.0F;
// 如果 ft 小于最大容量，使用 ft ，否则使用最大容量。
int t = ((ft < (float) MAXIMUM_CAPACITY) ?
(int) ft : MAXIMUM_CAPACITY);
// 如果容量大于扩容阈值 threshold ，使用tableSizeFor(t)重新计算扩容阈值 threshold
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold)
// 如果已经创建了哈希桶，并且需要的容量大于目前的扩容阈值 threshold ，resize()扩容
resize();
// 循环 传入的 map，调用 putVal 方法循环插入新值。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
这里看到了新方法：hash() 和 putVal()，等下我们在 常用方法中再去看 。
前面讲了内部是用单链表实现的，来看下单链表的节点具体包含的信息：
//单链表的一个节点，实现了Map.Entry 接口
static class Node<K, V> implements Map.Entry<K, V> {
// 我们传入的key 的 hash 值
final int hash;
// 我们传入的key
final K key;
// 我们传入的value
V value;
// 当前节点的后置节点
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
hash 值是确定在哈希桶中的位置的，如果 hash 值和 key 相等，说明是 key 值重复，会执行覆盖操作。如果是没有相同的 key ，直接创建新的链表节点，并把最后一个链表节点指向新创建的节点。
value 就是我们设置的 value 值。
next 就是指向单链表的下个节点的。
可以看出，我们传入的键值对基本都是存储在这个 Node 节点里面的(未树化的情况下，树化的话，存储在树节点)。
常用方法
put、 putVal
先看 put
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
这里和上面的第四个构造函数一样，都是通过 hash() 方法计算出了 key 的 hash 值。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
如果是 null 直接返回 0；
如果不是 null，h = key.hashCode()，就是调用我们传入的 key 对象的 hashCode() 方法，通过 hashCode 方法计算出来 key 对象的 int 类型的散列值，所以我们在把对象作为 key 的时候，一定要重写 hashCode 方法。
这里的 hash 方法等可以参照知乎上的回答
https://www.zhihu.com/question/20733617
接着看 putVal 这个方法:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//哈希桶 tab
Node<K, V>[] tab;
// 链表的头结点
Node<K, V> p;
int n, i;
// 把当前哈希桶赋值给 tab,如果为空,或者不为空,但是当前哈希桶的长度为 0
// 执行 resize() 创建哈希桶,并且把长度赋值给 n
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 现根据 当前 哈希桶长度- 1 和 传来的 hash 值进行与运算,得到哈希桶下标,然后从哈希桶中根据坐标取出节点,赋值给 p
// 如果节点 p 的值为 null.说明当前哈希桶的位置不存在链表节点,不存在 哈希碰撞,则创建一个新的节点,直接放到哈希桶中.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 这里是发生了哈希碰撞,说明 p 已经成功被赋值且不为 null.
else {
// 存在相同 key 的节点.
Node<K, V> e;
// 头结点 p 的 key 值
K k;
// 如果头结点 p 的 hash值和传来的相等并且 (头节点的 key 和传来的 key 的地址相等 或者 key值不为 null并且但是和传来的 key 值相等
// 说明是 key 已存在,并且相同.如果 onlyIfAbsent 为 false ,会覆盖 .如果为true ,则不覆盖
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// p 属于红黑树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
//
else {
// 开启个无限循环
for (int binCount = 0; ; ++binCount) {
// 如果当前哈希桶位置的头节点的后置节点为 null,也就是不存在后置节点,
if ((e = p.next) == null) {
// 新建一个 Node节点,然后让头节点的后置节点指向新创建的 Node 节点.
p.next = newNode(hash, key, value, null);
// 如果 binCount >= 7 ,执行 treeifyBin 进行树化.
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 终止循环
break;
}
// 这个时候执行过了 e = p.next ,说明是 e 是 头节点 p 的后置节点.
// 如果 e 的 hash值和传来的相等并且 (e 节点的 key 和传来的 key 的地址相等 或者 key值不为 null并且但是和传来的 key 值相等
// 说明在链表中找到了同hash、key的节点，那么直接退出循环
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
// p 指向下一个节点.继续下次循环
p = e;
}
}
// 如果当前 e 节点不为 null ,说明存在 key 相同的节点.那么直接覆盖原节点.
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果onlyIfAbsent 或者 找到的节点的 值为 null ,则覆盖原节点的 value值.
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 返回旧的 value 值.
return oldValue;
}
}
// 操作数 +1;
++modCount;
// 如果新增后的大小超过了阈值.执行 resize() 扩容.
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
首先在刚开始的时候，先判断当前哈希桶有没有创建，如果没创建，执行 resize() 创建哈希桶
由于 resize() 方法很重要，先来看下：
扩容关键方法 resize
final Node<K, V>[] resize() {
// 哈希桶大小
Node<K, V>[] oldTab = table;
// 老的容量.如果没创建 哈希桶,返回0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 老的扩容边界值
int oldThr = threshold;
// 新的容量,新的扩容边界值.
int newCap, newThr = 0;
//如果老的容量大于 0 .说明已经创建了 哈希桶
if (oldCap > 0) {
// 如果超过了最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
// 扩容边界值就是 Integer 的最大值
threshold = Integer.MAX_VALUE;
// 返回老的哈希桶,不再扩容
return oldTab;
//新容量 = 老容量*2 小于最大容量,并且老容量大于等于默认的初始容量
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 计算新的扩容边界值 *2
newThr = oldThr << 1; // double threshold
// 如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的情况,直接使用旧的扩容边界值作为新的容量,
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 容量为 0,容量未初始化,设置默认容量和扩容边界值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的扩容边界值为0,对应的是表是空的,但是有扩容边界值的情况.
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) {
for (int j = 0; j < oldCap; ++j) {
Node<K, V> e;
// 取出旧哈希桶中的节点(是一个链表中的头节点) 赋值给 e ,并且不为null
if ((e = oldTab[j]) != null) {
// 原来桶中的头节点置为 null
oldTab[j] = null;
// 如果没有下个节点,就是将这个位置没发生哈希碰撞.
if (e.next == null)
// 根据原节点的 hash 值和新哈希桶的长度 -1 计算出新 哈希桶中的位置,把 e 放进去
newTab[e.hash & (newCap - 1)] = e;
// 处理红黑树及诶单
else if (e instanceof TreeNode)
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
//这里处理的是发生过哈希碰撞,并且单链表长度不满 8 个的情况,先将其分组,再进行映射.
else { // preserve order
//低位链表的头结点、尾节点
Node<K, V> loHead = null, loTail = null;
//高位链表的头结点、尾节点
Node<K, V> hiHead = null, hiTail = null;
//临时节点 存放e的下一个节点
Node<K, V> next;
//
do {
//取出下个节点
next = e.next;
// 等于 0 是低位.,扩容后哈希桶位置不变.
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
// 不等于 0 是高位.扩容后位置会变化
} else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 低位的头结点和尾节点. 哈希桶坐标和原坐标一样
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位的头结点和尾节点.扩容后的 哈希桶坐标 = 原坐标一样 + 扩容的大小(原坐标的大小)
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
主要分为以下几步：
- 旧容量大于 0， 如果超过了最大值 MAXIMUM_CAPACITY，不再进行扩容，返回。没有超过最大值的话扩容为 2 倍。
- 旧容量小于等于 0，如果旧的扩容边界值大于 0 ，把旧的扩容边界值赋值给新的扩容边界值
- 旧容量小于等于 0，并且旧的扩容边界值小于等于 0 ，也就是没指定，就初始化默认的容量和扩容边界值
- 如果新的扩容边界值等于 0，根据新容量和新负载因子计算新的扩容边界值
- 然后根据新的容量进行创建一个新的哈希桶，并进行遍历
- 取出头节点，如果头节点后置节点为 null ，表明单链表只有一个头节点，没有发生哈希碰撞，直接放入新数组。
- 如果头节点是属于 树节点，调用 split 去处理，这里不再详细分析。
- 否则就说明是此位置的单链表发生了哈希碰撞，通过定义loHead、loTail、hiHead、hiTail来讲一个链表拆分成两个独立的链表。注意：如果e的hash值与老表的容量进行与运算为0,则扩容后的索引位置跟老表的索引位置一样。所以loHead-->loTail组成的链表在新Map中的索引位置和老Map中是一样的。如果e的hash值与老表的容量进行与运算为1,则扩容后的索引位置为:老表的索引位置＋oldCap，最后将loHead、loTail、hiHead、hiTail组成的两条链表重新定位到新的Map中即可
resize 方法介绍完了，继续来看 putVal 方法：
接下来就通过 hash 值和哈希桶长度 -1 做 取模运算，得到哈希桶的坐标。从哈希桶中取出这个位置的 节点赋值给 p。
没有发生 hash 碰撞
如果头节点 p 为 null ，说明没有发生哈希碰撞，直接放入头节点，就结束了。
发生了 hash 碰撞
如果头节点 p 不为 null ，说明当前哈希桶位置已经有值，就发生了 hash 碰撞了。
-
先判断当前头节点的 key 是否相等，这个会根据 hash 值、key 是否为 null，不为 null 的时候，调用 key 的equals 方法进行比较 key 是否相等。如果为 null ，或者 key 相等，待会就会执行覆盖。这个地方也说明了，key 是可以为 null 的。也验证了 key 是不能重复的，重复就会覆盖(只有onlyIfAbsent 为 false 的时候会覆盖)。
-
如果头节点属于红黑树节点，进行红黑树相关处理
-
如果不是，意思就是发生了hash 碰撞，需要遍历单链表的节点解决问题。在循环中判断：
-
如果取到的节点的 next 为 null ，说明没有后置节点，直接新建节点，并把当前节点的后置节点指向它。如果达到树化的值，就会去树化。否则跳出循环，插入结束。
-
取到的节点的 next 不为 null，如果在单链表中找到了与之 key 值相等的，也跳出循环，去执行覆盖。没找到相等的继续循环，找下一个，一直会在找到的节点的 next 为 null 或者 key 值相等的时候结束循环。
-
循环结束，如果当前 e 节点不为 null ,说明存在 key 相同的节点.那么直接覆盖原节点.
-
-
最后增加操作数，判断是否需要扩容，如果需要，执行 resize 扩容。
到这里， put 方法已经讲完了，前面讲的过程中在 putVal 方法中有一个参数，onlyIfAbsent 这个参数意思是如果为 true ，在key 值相同的时候，不会覆盖原值。我们调用 put 能覆盖，是因为在 put 方法调用 putVal 的时候传入的是 false，
如果不想在 key 重复的时候覆盖，可以使用 putIfAbsent 方法。
remove 方法
public V remove(Object key) {
Node<K, V> e;
// 计算散列码
// 根据 key 调用 removeNode
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
final Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K, V>[] tab;
Node<K, V> p;
int n, index;
// 如果哈希桶不为 null,并且长度大于 0,并且 哈希桶位置的头节点不为 null
if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {
Node<K, V> node = null, e;
K k;
V v;
// 头节点就是要移除的,赋值给 node
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 头节点不是要移除的,并且有后置节点
else if ((e = p.next) != null) {
// 树节点,红黑树处理
if (p instanceof TreeNode)
node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
// 单链表处理
else {
do {
// 循环,一直找到 key 值相等的节点跳出循环,否则最后跳出循环
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 如果找到了目标删除节点,执行删除操作,并返回删除的目标节点,否则返回 null
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
此外还有个 remove(Object key, Object value) 方法，和上面的不同的是也会比对 value 是否相等，这里不再展开。
replace 方法
@Override
public V replace(K key, V value) {
Node<K, V> e;
// 调用 getNode 通过 key 找到节点,并且不为 null,覆盖原节点值.
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
这里 replace 的核心还是这个 getNode 方法，就是通过 key 找到 node 节点。下面讲解。
get 方法
public V get(Object key) {
Node<K, V> e;
// 利用 hash 扰乱 key 的散列值
// 调用 getNode 找 key 相等的节点
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K, V> getNode(int hash, Object key) {
// 哈希桶
Node<K, V>[] tab;
// first 头节点和要找的节点
Node<K, V> first, e;
//哈希桶长度
int n;
K k;
// 如果哈希桶不为 null,并且长度大于 0,并且 哈希桶位置的头节点不为 null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 如果头节点满足,就返回头节点
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果头节点的后置节点不为 null
if ((e = first.next) != null) {
// 如果属于红黑树,去红黑树中去查
if (first instanceof TreeNode)
return ((TreeNode<K, V>) first).getTreeNode(hash, key);
// 不属于红黑树,在单链表中查
do {
// 一直找到 key 值相等的节点.如果没找到并且最后一个节点的后置节点为 null ,说明没有key 值相等的,退出循环,返回 null
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get 方法大概就是这样，还是先计算 hash 值，然后调用 getNode 找节点，找到说明存在，返回节点，最后返回节点的 value 值。
没找到说明不存在，则返回 null；
遍历
//迭代器遍历
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
key.key;
key.value;
}
// entrySet 遍历
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
// 在for-each循环中遍历keys或values。
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//遍历map中的键
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
System.out.println("value = " + map.get(key));
}
//遍历map中的值
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
常见的一些问题
1、底层数据结构？
采用数组+单链表+红黑树来实现的，
数据中存储的是单链表的头节点或者是红黑树节点。当单链表长度大于 8 的时候，进行树化，当树的长度小于 6 的时候，转化成单链表。
2、什么是 Hash 冲突？如何解决 Hash冲突？
hash 冲突是在拿到 HashMap 的 key 以后调用 hash 方法去计算哈希值，然后拿这个哈希值和哈希桶的长度 -1 取模运算，得到要把这个 Entry 放入哈希桶的位置，如果这个时候哈希桶的这个位置已经有值了，那么就产生了 hash 冲突。
解决办法就是哈希桶的位置已经有值得情况下去比对当前哈希桶存的链表。
- 如果头节点的 key 和传入的 key 相等，执行覆盖
- 如果是红黑树，交给红黑树处理
- 遍历单链表中的节点，找到相同的 key ，进行覆盖。没找到，插入到最后节点，超过 8，进行树化，提高访问速度。
取模用与操作（hash & （arrayLength-1））会比较快，所以数组的大小永远是2的N次方， 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。
3、为什么在树化前会优先考虑扩容，而不是直接树化？
这个主要是从效率和空间上来衡量的，
链表占用空间小，但是查询效率低，
红黑树占用空间大，但是查询效率高
在空间和效率上做了一个平衡。
当 hashmap 的 哈希桶长度大于容量*负载因子的时候，就会扩大哈希桶的容量。一次性扩大两倍，永远是 2 的 n 次方，取模的时候速度比较快，扩容的时候会重新安排所有元素的位置，尽量能够保证均匀的分布在不同的哈希桶中。
总结
前面分析了 HashMap 的源码，相信对 HashMap 的内部工作机制有了更一步认识，对于树化这一块，后面再抽时间去仔细的分析一下。
HashMap 特点：
-
允许key 为 null ，value 为 null
-
key 不可以重复，value 可以重复
-
内部是以数组+单链表实现的，JDK8 以后加入了红黑树
-
内部键值对的存储是无序的，而且顺序会在扩容时改变
-
初始容量为 16，负载因子为 0.75，也就是当容量达到 容量*负载因子 的时候会扩容，一次扩容增加一倍。
-
内部的键值对要重写 key 对象重写 hashCode 方法、equals 方法。
-
线程不安全的，如果想要线程安全，有三种方法
- Hashtable 不允许key 为 null，内部使用个 Synchronized 关键字实现线程安全
- ConcurrentHashMap java 并发包下的一个线程安全的 HashMap
- SynchronizedMap 使用 Collections.synchronizedMap(new HashMap<>()); 来获得一个线程安全的 HashMap,SynchronizedMap内部也是使用的 Synchronized 实现线程安全的
有错误的话，麻烦大家一起交流，这篇到这里就结束了。后面有新的认识再进行补充吧。
image
网友评论