简介
HashMap是Java面试中经常出现的问题，自然也需要对它的源码进行了解和掌握。
实现方式
在JDK1.7及以前，HashMap的实现方式是数组+链表，但是在JDK1.8之后对HashMap的底层进行了一些优化，变成数组+链表/红黑树的结构，在节点数小于等于6时，以数组+单向链表存储，节点数大于等于8时，则以数组+红黑树的方式存储。这样做的目的主要也是为了提高查询效率。
关于红黑树，可以查看这篇文章 ：关于红黑树
源码
继承关系
首先先看一下HashMap的继承关系，它继承自AbstractMap，实现Map、Cloneable、Serializable接口。
这里需要说明的是AbstractMap这个类，它是提供了Map的基本实现的抽象类，即在Java中为了实现Map所写的一个便利类，也就是说如果我们需要Map的一个具体类，只要实现AbstractMap未实现的部分即可，自然也可以重写已实现的方法。
默认常量
//默认初始容量为16，也就是2^4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，为2^30 (int的取值范围在-2^31~2^31-1)
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载系数
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//转为红黑树的临界值，在节点数大于等于8时转为红黑树
static final int TREEIFY_THRESHOLD = 8;
//转为链表的临界值，在节点数小于等于6时转为单向链表
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树的最小长度为64
static final int MIN_TREEIFY_CAPACITY = 64;
字段
//Node是Map.Entry接口的实现类，存储数据的Node数组长度是2的幂，每一个Node的本质都是一个单向列表
transient Node<K,V>[] table;
//键值对集合，是不可重复的
transient Set<Map.Entry<K,V>> entrySet;
//HashMap的大小，也就是保存的键值对数量
transient int size;
//HashMap被改变的次数
transient int modCount;
//HashMap下次扩容的大小(容量*负载系数)
int threshold;
//负载系数的常量，前面说到默认为0.75
final float loadFactor;
transient字段说明：
- 一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。
- transient关键字只能修饰变量，不能修饰方法和类。（本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。）
- 实现Serializable时，被transient关键字修饰的变量不再能被序列化，但若是实现Externalizable接口，由于是在writeExternal方法中进行手工指定所要序列化的变量，这与是否被transient修饰无关，则可以被序列化。
Node[]的实现
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//Node的本质就是一个单向列表
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// get、set、hashCode、equals和toString方法
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
构造方法
无参构造
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
指定初始容量和负载系数的构造方法
public HashMap(int initialCapacity, float loadFactor) {
//初始容量小于0的话会抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量大于最大容量则设为最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载系数小于等于0或不是一个数的时候则抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//进行初始化
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
仅指定初始容量
public HashMap(int initialCapacity) {
//添加默认负载系数调用上面的双参数构造方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
使用Map集合构造
//将Map中的键值对全部放入HashMap中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
红黑树的实现
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);
}
......
}