最近准备开始系统的看一下jdk实现的源码和了解一些设计模式，先从最经典的容器类入手，看了之后不得不说数学基础是真的重要，如果再给我一次机会我一定更认真地学数学。本篇文章会分析HashMap。首先，在本篇文章开始之前我们要知道什么是哈希表，链表，红黑树，可以参考我以前的博文进行了解。
源码分析
首先HashMap是通过哈希表实现的，哈希函数为取余，哈希冲突解决方法为链地址法，也就是说HashMap的底层是一个数组+链表（红黑树）的结构（数组中的每个元素可能形成一个链表，链表长度大于8时链表化为红黑树），如图就是一个hashmap
下面来具体看一下hashmap时如何实现的。
HashMap的属性
首先看hashmap的属性
//哈希表数组
transient Node<K,V>[] table;
//键值对的个数
transient int size;
//哈希表数组默认初始大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
//哈希表数组的最大元素个数
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认负载因子，扩容时有用，也可以自己构造时指定，默认0.75f
final float loadFactor;
//当前HashMap所能容纳键值对数量的最大值，超过这个值，则需扩容，threshold = capacity * loadFactor
int threshold;
//遍历的entrySet
transient Set<Map.Entry<K,V>> entrySet;
//用于判断是否在遍历的时候进行改变，若是，抛出ConcurrentModificationException
transient int modCount;
//链表的节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
//Entry
final class EntrySet extends AbstractSet<Map.Entry<K,V>>{...}
复制代码- table就是hashMap中的哈希表，当把一个key，value存进hashmap中时，通过hash算法定位到table的下标，将key，value封装为Node存进数组中，当出现哈希冲突时，采用链的方式进行冲突解决。
- threshold，当前HashMap所能容纳键值对数量的最大值，超过这个值，则需扩容，threshold = capacity * loadFactor
- loadFactor，负载因子，同样的table，负载因子大时存放的节点更多，查找的效率变慢；负载因子小时存放的节点少，查找更快。所以负载因子用来维持时间和空间的关系。
- size，键值对的个数
- 这里并没有capacity容量这个成员变量，因为我们没有必要去保存它的容量，我们看完增删的逻辑就知道为什么没有容量这个变量
构造函数
hashmap提供了四种构造函数
//无参构造函数，所有的属性都为默认属性
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//传入初始容量，负载因子为默认0.75
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//传入初始容量和负载因子
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);
}
//通过map构造一个新map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
复制代码用户传入初始化大小时是如何计算threshold呢？
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码这里就是返回大于或等于 cap 的最小2的幂，如cap为31，返回32；cap为7，返回8；cap为9，返回16
查找
查找的逻辑为先计算到数组的下标，然后对链表或红黑树进行遍历查找
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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;
}
复制代码这里是怎么定位到下标的呢？
first = tab[(n - 1) & hash]
复制代码即直接通过(n-1)&hash就找到table中元素的下标，n=table.length，hash为算出来的key的哈希值。而table的大小始终是2的n次方，(n – 1) & hash 等价于对 length 取余。可以尝试当n=16时，hash=55，这时对hash%n操作得到的结果为7，(n-1)&hash结果也是7。而至于为什么不采用取余操作而使用这种方式，众所周知位运算的速度比取余操作速度快。
这里顺带有个问题就是为什么hashmap中对key计算哈希值时要重新规定哈希函数呢？
这个问题的意思就是为什么hashmap中要自己实现hash(K key)函数。
- 计算余数时，如果n比较小，hash只有低4位参与了计算，高位的计算可以认为是无效的。这样导致了计算结果只与低位信息有关，高位数据没发挥作用。为了处理这个缺陷，我们可以上图中的hash高4位数据与低4位数据进行异或运算，即 hash ^ (hash >>> 4)。通过这种方式，让高位数据与低位数据进行异或，以此加大低位信息的随机性，变相的让高位数据参与到计算中。
- 可以减少哈希冲突
遍历
遍历hashmap有大致三种方法
//1.采用foreach迭代entries
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())
}
//2.使用foreach迭代keys和values
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//迭代key
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
//迭代value
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
//3.使用Iterator迭代
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, Integer> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
复制代码而foreach我们知道它只是一种语法糖，事实上在进行反编译后发现foreach实际上就是等价于使用iterator进行迭代的。所以下面直接看迭代器时如何迭代的。
下面来看一下有关迭代器遍历的代码：
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
}
/**
* 迭代器
*/
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
// 寻找第一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
// 寻找下一个包含链表节点引用的桶
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//省略部分代码
}
复制代码遍历所有的键值对时，首先要获取键集合EntrySet对象（对key和value进行遍历相似），然后再通过 EntrySet 的迭代器EntryIterator进行遍历。EntryIterator 类继承自HashIterator类，核心逻辑也封装在 HashIterator 类中。HashIterator 的逻辑并不复杂，在初始化时，HashIterator 先从桶数组中找到包含链表节点引用的桶。然后对这个桶指向的链表进行遍历。遍历完成后，再继续寻找下一个包含链表节点引用的桶，找到继续遍历。找不到，则结束遍历。如图：
打印顺序为：54，29，16，43，31，46，60，74，88，77，90
如果链表转为红黑树的话采用的是哪种遍历方式？
可以看到，在遍历的代码中并没有对红黑树单独进行遍历，这时因为这里我们的红黑树中有一个成员变量指向原链表中的下一个节点，所以，转为红黑树的遍历顺序就是next的顺序。
增加
//新增方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//hash函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* 增加操作的具体实现
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果是第一次添加会初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//该下标没有元素，直接插入（没有产生哈希冲突）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果键的值以及节点hash等于链表中的第一个键值对节点时，则将e指向该键值对
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) {
//链表中不包含要插入的键值对节点时，则将该节点接在链表的最后
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度大于或等于树化阈值，则进行树化操作
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//加入的节点和原来的节点是同一个节点（这里哈希值和equals方法都相同才判定为同一个节点）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判断要插入的键值对是否存在 HashMap 中
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//当键值对数量超过扩容阈值时扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
复制代码总的来说，大概流程如下：
- 是否需要对table初始化
- 查看这个节点的key是否已经存在，若存在并且或原来value为null，替换
- 这个节点不存在就插入，插入的三种情况
- 没冲突，直接插入
- 冲突，链表插入，考虑树化
- 冲突，红黑树节点插入
- 判断键值对数量是否大于阈值，大于的话则进行扩容操作
扩容
再增加的时候会进行扩容，扩容的条件为++size > threshold,下面具体来看扩容的实现
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//table已经完成初始化
if (oldCap > 0) {
//达到最大，不能继续扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//变为原来容量的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//table未完成初始化但阈值已经设置完成，即使用HashMap(int)或HashMap(int,float)构造时会发生这种情况
else if (oldThr > 0) // initial capacity was placed in threshold
//设置阈值为新容量
newCap = oldThr;
//table未初始化，阈值未初始化，即使用HashMap()构造时发生这种情况
else {
//设置初始值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//计算出新阈值
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;
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;
//下面这个循环的目的就是把原来是链表的那些节点继续保持链表
do {
next = e.next;
//(e.hash & oldCap) == 0为true判断的是扩容后在原下标，false为要放进新的下标。
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//将链表放进新table中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
复制代码好的，扩容的逻辑就是上文这样，总结一下，扩容主要做了三件事
- 计算新哈希表table的容量newCap和新阈值newThr
- 根据新newCap得到新的哈希表table
- 将键值对节点重新映射到新的哈希表里。如果节点是TreeNode类型，则需要拆分红黑树。如果是普通节点，则节点按原顺序进行分组。
链表和红黑树的转化
前文说到当链表长度大于8时要将链表转为红黑树，红黑树长度小于6时要将红黑树转为链表。具体的就是转化分为三个操作：
- 链表的树化
- 树的链表化
- 拆分
链表树化
static final int TREEIFY_THRESHOLD = 8;
/**
* 当table数组容量小于该值时，优先进行扩容，而不是树化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
/**
* 将普通节点链表转换成树形节点链表
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//table数组容量小于 MIN_TREEIFY_CAPACITY，优先进行扩容而不是树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//hd为头节点，tl为尾节点
TreeNode<K,V> hd = null, tl = null;
do {
//将普通节点替换成树形节点
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null); //将普通链表转成由树形节点链表
if ((tab[index] = hd) != null)
//将树形链表转换成红黑树
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
复制代码看了链表变为红黑树的源码，我们可以得出以下结论：
链表变为红黑树的条件：
- 链表长度大于8：官方文档说是因为按照泊松分布的计算公式计算出了链表中元素个数为8时的概率已经非常小，根据概率统计而选择的8为分界点
- 哈希表table的容量大于64：当table容量较小时应该优先考虑扩容，因为如果容量小数据多会产生大量哈希碰撞，性能下降
链表如何变为红黑树：
因为一开始hashmap设计时并没有考虑到对节点进行大小比较，而红黑树是一种有序树，所以要求每个节点要可比较（实现comparable接口或提供比较器）。所以在树化的过程会经历以下过程：
- 首先比较键与键之间hash的大小，如果hash相同，继续往下比较
- 检测键类是否实现了Comparable接口，如果实现调用compareTo方法进行比较
- 如果仍未比较出大小，通过tieBreakOrder方法比较
通过以上方法比较完之后就能进行排序变为红黑树了
拆分
拆分就是扩容的时候，红黑树节点要映射到新的哈希表中的对应位置，这个过程叫树的拆分。当然，如果将全部红黑树中的节点重新计算下标插入到新哈希表，由链->树这样也可以，但这样效率很低，所以hashmap的设计多了一个拆分。
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 红黑树节点仍然保留了next引用，故仍可以按链表方式遍历红黑树。
* 下面的循环是对红黑树节点进行分组，与上面类似
*/
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//如果loHead不为空，且链表长度小于等于6，则将红黑树转成链表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
/*
* hiHead == null 时，表明扩容后，
* 所有节点仍在原位置，树结构不变，无需重新树化
*/
if (hiHead != null)
loHead.treeify(tab);
}
}
//与上面类似
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
复制代码红黑树的拆分和扩容时对节点的重映射相似
红黑树的链表化
当删除节点时可能造成红黑树的个数小于6个，这时要将红黑树再转化为链表。
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//遍历TreeNode链表，并用Node替换
for (Node<K,V> q = this; q != null; q = q.next) {
//替换节点类型
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
复制代码因为红黑树中的节点有prev节点，这个节点指向的原链表形态时当前节点的下一个节点，所以在链化的时候就很方便了。
为什么链化为6，树化为8？
以下为我个人观点
- 首先，红黑树的查询O(logn)比链表O(n)快；但红黑树添加删除节点时会维持红黑树的特性而进行相应旋转，变色操作，链表在添加删除时只需要改变当前节点的next指针即可。
- 当链表和红黑树的节点个数小于等于6时，查询速度的差异小于删除添加的差异，所以选择添加删除更方便的链表
- 当链表和红黑树的节点个数大于8时，删除添加的速度差异小于查询速度的差异，所以选择查询更快的红黑树
删除
删除大概分为三部
- 确定哈希表的下标
- 遍历下标的链表到相应的节点
- 删除
当然，和前面一样，删除链表节点可能会变为删除红黑树节点，有可能删除红黑树节点后会进行红黑树的链表化。下面来看一下实现代码：
//暴露给使用者的删除方法
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
/**
* 删除的具体实现
*
* @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;
//确定哈希表的下标
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 {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//以上步骤都是找到待删除节点node，接下来删除node，并修复链表或红黑树
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;
}
复制代码其中，关于红黑树的维护这里就不具体讲解了，因为我实在觉得红黑树的维护思想不难，但是很麻烦，解读的话也差不多和平常红黑树维护的思路相同，就是左旋转，右旋转，变色。红黑树链表化前文也分析过了。
其他关于hashMap
modCount属性
我们在使用迭代器进行迭代时，当我们改变hashmap的状态时，会抛出ConcurrentModificationException异常。
抛出这个异常的原因
抛出这个异常的原因就是在遍历hashmap的时候，hashmap的数据改变了。我们在分析迭代器遍历的时候有这么一段代码：
abstract class HashIterator {
//其他代码
final Node<K,V> nextNode() {
//其他代码
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//其他代码
}
}
复制代码可以看到，这个异常抛出的条件是modeCount!=expectedModCount的时候，而modCount之前说过时hashmap的一个属性，每当进行put，remove操作的时候都会对modCount进行++操作，而exceptedModeCount是一开始遍历时候的modCount。所以说，这个异常抛出的时候代表遍历的时候表发生了改变。这也就是java中的fail-fast机制。这个机制主要是针对多线程环境下的线程安全问题，但事实上hashmap还是线程不安全的。
如何解决这个问题？
我们想做的无非就是在遍历的时候删除元素
- 可以使用iterator提供的remove方法进行删除
- 直接改用ConcurrentHashMap
序列化
我们看到哈希表table使用了transient修饰，这个关键词代表这个属性不会被序列化。
为什么table不能被序列化？
我们知道确定hashmap使用的哈希函数会用到key的hashCode，而key的哈希code方法可能没有被重写，这样这个方法就会调用Object的hashCode方法，而Object的hashCode方法是本地native方法，那么会造成的问题就是同一个hashmap可能在不同虚拟机下反序列话时造成每个键的hash值不一样，就会造成键值对对应的位置出错。
如何解决hashmap序列化问题？
可能我需要将hashmap传送到其他计算机上，那么hashmap自己实现了writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectInputStream s)方法。他们作用是该类在序列化时会自动调用这两个方法，没有这两个方法就调用defaultWriteObject()和defaultReadObject()。而hashmap实现了，所以看一下他们是如何进行序列化的，下面只分析写，读就对是相应数据的读就行了。
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<K,V>[] tab;
if (size > 0 && (tab = table) != null) {
for (Node<K, V> e : tab) {
for (; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
复制代码可以看到，hashmap实现序列化的方式就是将hashmap拆解为属性和节点，直接把属性和节点序列化即可
总结
那么hashmap的分析就到此结束，本来是想把有关Map的常用实现类都写在一篇的，但真正查看hashmap源码的时候才发现一些实现真的要考虑很多问题和细节，写在一篇里太多太杂。通过这次彻底的源码分析我也是感受到了代码的设计，编写艺术，在一开始查看源码的时候我都觉得这些编写人员是不是有一点设计过度，但后来又对每个细节进行思考，包括查了很多篇网上的博客，我才真的觉得设计人员的厉害之处，虽然他们的代码量很多很长，注释也非常多，但每一行代码都有自己的很关键的作用，每一行代码都必不可少，考虑的也非常全面，包括对每一个细节的考虑。总的来说，这次源码的分析不仅让我知道了hashmap的实现细节；还教会了我怎样去设计一个完美，通用的代码；还有就是数学的重要性。
下一篇会通过分析ConccurrentHashMap，然后再简单的看其他容器时如何实现的，最后祝我自己期末不挂科。
转载于:https://juejin.im/post/5d0258f4e51d4550723b13e3