完全解析HashMap

[acidsweet]

HashMap是广大程序员使用的最多、面试被问最多的一个容器了：

• 日常使用我们只知道它是键值对就行
• 面试八股文的时候我们一般纠结在它怎么hash、怎么解决hash冲突、怎么扩容；一些变态的八股可能会关注链表什么时候转化成红黑数又什么时候退化成链表

我个人也经常面试别人的时候会用hashmap切入去问容器、线程安全、锁等方面内容，但是其实hashmap真正的源码并没有特别认真的通读过；这个文章就是从HashMap源码入手，详细解析一下HashMap(android-30)的实现；

声明

我们首先看一下HashMap的声明：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

我们先从interface开始解析：

1. Serializable

public interface Serializable {
}

这里有篇文章说的很好 → https://blog.csdn.net/weixin_44209555/article/details/107837108
我在这里主要提炼一下主要观点：

• Serializable首先是一个标记接口(Marker Interface)，这说明它没有任何方法，关于标记接口的作用可见 → https://zhuanlan.zhihu.com/p/42756607
• Serializable主要是标识这个类是可以被序列化\反序列化的，特别是序列化的时候会在ObjectOutputStream.writeObject()里校验
  
• serialVersionUID的作用主要是反序列化的时候检查文本里的Class和Java代码里的是不是同一个，这个可以在ObjectStreamClass.initNonProxy()里看到校验的过程，如果不一致会抛出异常
  

2. Cloneable

public interface Cloneable {
}

这里也引用一篇文章 → https://www.jianshu.com/p/ea8f7b1fbbb1
提炼的重点：

• 很明显，Cloneable也是一个Marker Interface
• 使得对象可被克隆，需要对象implements Cloneable，这时候调用Object.clone()才可以克隆
  
• 深拷贝和浅拷贝：需要注意internalClone是一个native的浅拷贝快速实现，需要实现深拷贝需要自己Override Clone

3. Map<K,V>

• Map就是一个标准的模板接口了(Template Interface)，它定义了Map这个数据结构应该具有的方法，这里就不一一说明
• 需要注意内部的一个接口：Entry，如果说Map是代表键值对集合，那么Map.Entry就是代表键值对本身

接口在这里就全说完了，那么我们这里可以对HashMap实现的接口做定义：
HashMap是一个可以(反)序列化、可以克隆的Map

4. AbstractMap<K,V>

public abstract class AbstractMap<K,V> implements Map<K,V>

• 可以看到AbstractMap是一个实现了Map的虚基类，它里面已经提供了Map部分方法的实现了，它的目的在jdk的注释里已经写的很清楚

This class provides a skeletal implementation of the Map interface, to minimize the effort required to implement this interface.

• AbstractMap提供了一个基本的Map的实现，它减轻了其他实现类的工作
• 整个Map继承树基本如下
  

实现

1. 成员

// 常亮
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
// 变量
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

首先，我们看一下HashMap里的成员：

• 常量
  • serialVersionUID：(反)序列化需要
  • DEFAULT_INITIAL_CAPACITY：初始容量，这里就回答了面试的时候经常被问的hashmap初始容量是多少
  • MAXIMUM_CAPACITY：最大容量，需要注意的是即使最终数据量超过MAXIMUM_CAPACITY时，resize的时候并不会出错，它会强制将threshold提升到Integer.MAX_VALUE
  • DEFAULT_LOAD_FACTOR：默认负载因子值
  • TREEIFY_THRESHOLD\UNTREEIFY_THRESHOLD：这就是链表变成红黑树以及红黑树退化成链表的阈值要求了；所以默认情况下，当链表长度超过8个就会进化成红黑树，而当红黑树节点少于6个的时候就会退化成链表
  • MIN_TREEIFY_CAPACITY：前面已经定义了TREEIFY_THRESHOLD约定了当单个节点下链表长度大于8时会转成红黑树，而MIN_TREEIFY_CAPACITY是又添加了一条约束：只有当整个map里节点数量超过64个时才会允许树化，这里主要是萎了防止hashmap使用初期就进行树化而不是直接resize
• 变量
  • table：Node的数组，对应hash表的线性表；这里有个小的细节是transient关键字，它表示这个变量不会被(反)序列化 → https://blog.csdn.net/qq_44543508/article/details/103232007
  • entrySet：将HashMap里的内容用Set<Map.Entry<K,V>>方式呈现，主要使用场景是HashMap的构造函数和putAll方法里；等于是批量将另一个map内容put进来的需要
  • modCount：