HashMap大家肯定非常的熟悉，HashMap底层其实就是一个数组，只不过数组的每一项都是一条链，也是面试中经常喜欢问到的知识点，"请说下HashMap的工作原理"，ememem.....其实面试官主要是想考察我们知其然还要知其所以然，所以我们不能一直停留在会用api，还要带着问题去研究源码。比如，为什么HashMap的键(key)和值(value)可以为null，而HashTable键和值确却都不能为null？如果两个键的hashcode相同，会发生什么情况？以及如何取到相应的值？
为什么说要带着问题看源码呢？因为这样目的性更强效率更高，漫无目的的看源码会使你陷入其中而不能自拔，带着问题看，点到为止。下面就进入正题，首先先来一张自己画的HashMap结构草图，大家将就着看吧，有助于理解
hashmap数据结构图.png
简单的说明下，HashMap底层其实就是一个table数组，只不过数组的每一项是由一条链组成的，而这每一条链表都是由若干个节点组成，每一个节点就是一个Entry对象，每一个Entry对象中存储的是我们的key对象和value对象以及下一个节点next（链表中如果不止一个节点的话，那么前一个节点的next就会指向下一个节点），由上图可知，假如有一条很长很长的链表分布在数组的某一项上面，如果我们想取某一个value值的话，就需要遍历数组i位置的这条链表，所以如果这些链表都能均匀的分布到数组的每一项上，而不是像刚才那样的话，我们取值的速度就会快很多。其实这些在HashMap内部都做了很好的优化处理，接下来我们就一起来探究HashMap源码，看看是如何优化的。
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
可以看到HashMap继承自AbstractMap抽象类，实现了Map接口中的方法
接着看下HashMap的一些成员变量声明
//默认的初始容量(必须是2的整数次幂)，jdk版本不同，有的是16
static final int DEFAULT_INITIAL_CAPACITY = 4;
//最大容量(2的30次方)，如果配置的容量大于此值的话就会用此值替换
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子(0.75是基于时间和空间的一种折中结果)，在扩容时起到关键作用
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空table数组（HashMap的底层其实就是一个链式数组）
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
//存储数据的HashMapEntry数组(静态内部类HashMapEntry实现了Map.Entry<K,V>接口)
//table数组中存储的就是一个个Entry链，Entry中存储的就是一个个key-value键值对数据
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
//键值对的数量
transient int size;
//HashMap的阈值，用于判断是否需要扩容(threshold = 容量*加载因子)
int threshold;
//加载因子实际大小
final float loadFactor = DEFAULT_LOAD_FACTOR;
//HashMap修改的次数
transient int modCount;
通常我们用到HashMap的时候需要去new HashMap()；那么我们就从HashMap的构造方法开始查看
//传入容量值、加载因子
public HashMap(int initialCapacity, float loadFactor) {
//容量值不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果设置的容量值大于HashMap允许的最大容量，纠正并将HashMap允许的最大值赋值给他
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
} else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
//同理如果小于HashMap的默认初始容量大小的话，就将默认值赋值给他
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
//加载因子不能小于0
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Android-Note: We always use the default load factor of 0.75f.
// This might appear wrong but it's just awkward design. We always call
// inflateTable() when table == EMPTY_TABLE. That method will take "threshold"
// to mean "capacity" and then replace it with the real threshold (i.e, multiplied with
// the load factor).
//在部分版本上这个阈值等于容量*加载因子
threshold = initialCapacity;
init();
}
//一个参的构造方法，加载因子用HashMap默认的
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//无参的构造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//将子map传进来，如果m为null的话会报空指针错误
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
//创建链表数组
inflateTable(threshold);
//将m中的key-value键值对都添加到HashMap数组中
putAllForCreate(m);
}
这里要特别说明的是，HashMap链表数组中存储的是键值对(key对象和value对象)，而不是只存储value或者key
接下来分析下HashMap是如何存取的
存
public V put(K key, V value) {
//先判断当前链表数组是否为空数组，是则调用inflateTable方法创建一个数组
if (table == EMPTY_TABLE) {
//此方法中通过table = new HashMapEntry[capacity]创建一个数组
inflateTable(threshold);
}
//如果key是null的话，会调用putForNullKey方法，将值存放到table数组的第0项位置处，即第一个桶中
if (key == null)
return putForNullKey(value);
//根据key的hashcode计算出hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//通过hash值计算出此条键值对在桶中的位置
int i = indexFor(hash, table.length);
//HashMapEntry是单链表结构，e.next查找下一个节点数据
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//遍历，如果key相同，那么就将此key的新value值覆盖旧value值，并直接返回旧value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//走到这一步说明添加到数组中的键值对的key不相同，那么就将此键值对数据添加到数组的i位置
addEntry(hash, key, value, i);
return null;
}
通过对key==null的处理，我们看下putForNullKey(value)方法
//从此方法中我们可以得到两点关键信息
private V putForNullKey(V value) {
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
//1、由下面第二点注释可知，key为null的键值对数据是都存储在table[0]位置的
//2、程序能够进入这个if (e.key == null)判断中，说明table[0]位置已经存在了key为null的键值对数据
//所以，遍历table[0]如果此位置已经有key为null的value数据了，那么就将新value值覆盖旧value值，并将旧value值返回
//同时还能得出HashMap的key是唯一的，相同的key对应的键值对会被覆盖
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//2、如果key为null的话，并且之前table[0]位置还没有存储key为null的键值对数据时，会将此键值对添加到table[0]位置
addEntry(0, null, value, 0);
return null;
}
接下来我们再看下如果我们在存储时key为null和key不为null两种情况下是如何将这个键值对存储到链表数组中的
//key为null的情况，并且是第一次存储时
//由上面分析已经知道key=null时位于table[0]位置，所以bucketIndex为0，他的hash值也为0
addEntry(0, null, value, 0);
//要存储的key不为null的情况
addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
//首先在put存储key-value对象时，要判断当前数组中存储的key-value对象数量是否达到了HashMap的阈值，
//超过阈值则需要对HashMap进行扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//对HashMap进行扩容，重新调整他的容量
resize(2 * table.length);
//key为null的话那么hash值为0；
//key不为null的话，由于扩容了，所以需要重新根据key的hashcode值去计算hash值
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
//通过hash值计算出此条key-value对象在table数组中的位置索引
//因为进行了扩容，所以需要重新确定bucketIndex
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
HashMap的扩容
接着我们看下resize方法
void resize(int newCapacity) {
//旧HashMap
HashMapEntry[] oldTable = table;
//旧HashMap的容量
int oldCapacity = oldTable.length;
//在扩容前需要进行判断，
//如果旧HashMap的容量已经达到最大要求值，则不能再扩容，直接返回，同时将阈值设置为Integer.MAX_VALUE
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//根据扩容要求的容量大小new一个新的HashMap
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
//下面会介绍
transfer(newTable);
//并将新HashMap赋值给旧HashMap
table = newTable;
//阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
看下这个transfer方法
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
//主要操作就是循环遍历旧HashMap，取出一个个key-value对象并存储到扩容之后的新HashMap中
//由此可见扩容是耗性能的，所以如果我们知道要存储的数量大致数量的话，在new这个HashMap的时候就给他一个合适的容量，
//这样也就避免了扩容，降低了性能的损耗
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
上面我们分析了HashMap是如何进行扩容的，以及扩容需要注意和优化的知识点，接下来继续看createEntry方法
void createEntry(int hash, K key, V value, int bucketIndex) {
//将table数组的bucketIndex位置的值赋给e链表
HashMapEntry<K,V> e = table[bucketIndex];
//1、将key-value键值对数据插入到新new的Entry链表中
//2、再将这个存储了新键值对的HashMapEntry存储到table数组的bucketIndex处
//3、设置e指向下一个节点(新插入的键值对都是存储在链表的头部的)
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
//put一条键值对数据之后，键值对数量就+1
size++;
}
取
public V get(Object key) {
//取key为null的value值，上面分析已经知道，key为null时，key-value是存储在table[0]位置
//getForNullKey()方法就是循环遍历table[0]位置找到key为null时对应的value值
if (key == null)
return getForNullKey();
//key不为null时
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
下面把getForNullKey()方法和getEntry(key)方法也贴出来分析下
//这个方法在上面取值方法中已经简单分析过了
private V getForNullKey() {
if (size == 0) {
return null;
}
for (HashMapEntry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//日式走到这个方法时，key是不为null的，不明白这里为什么还要对key是否为null进行判断？？
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//根据key的hashcode计算出hash值，再根据hash值就可以计算出在table数组中的哪一个位置
//得到table在这个位置处的HashMapEntry链表，循环遍历链表中的节点
for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
到此，对于HashMap如何存储、扩容、以及取值等进行了详细的分析，基于jdk版本的不同，可能源码也不相同，例如，最新的HashMap源码中是通过树来进行存储的，我也是分析完之后发现并不是最新的源码，所以，以后有时间再对最新的HashMap源码进行分析吧，如有分析不对的地方，还望各位老铁指正
