简介
HashMap是Map经常使用的一个实现类,也是我们经常用到的一个集合，所以很有必要去了解一下。JDK8相对JDK7优化了不少，结构也改变了，所以这里就分开来学习了。
因为我英语不是特别好，所以有些源码的文档注释是机翻的，所以有些文档注释读起来怪怪的，只能理解一下大概意思。
JDK7
参数和变量
/**
* 默认的初始容量，必须是2的幂，默认16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 这是HashMap的最大容量，值为1<<30。要是传入更高的值，就会使用这个最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* HashMap默认的负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; /**
* 当表未膨胀时使用的空表实例
*/
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
*这个表根据需要调整长度大小，长度必须为2的幂
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
/**
* 键值对的数量
*/
transient int size;
/**
* 下一个要调整大小的值，值为容量*负载系数
* 如果table == EMPTY_TABLE,则值为初始容量
* 膨胀时将会创建表格
* @serial
*/
int threshold;
/**
* 哈希表的负载因子
* @serial
*/
final float loadFactor;
/**
* 已对HashMap进行结构修改的次数结构修改是指更改HashMap中的映射数或
* 以其他方式修改其内部结构（例如，重新哈希）的修改。 此字段用于使HashMap的Collection-view上
* 的迭代器快速失败。（请参见ConcurrentModificationException）。
*/
transient int modCount;
/**
* 映射容量的默认阈值，高于该阈值时，字符串键将使用替代哈希。
* 备用哈希可减少由于字符串键的哈希码计算能力较弱而导致的冲突发生率。
* <p/>
* 可以通过定义系统属性来覆盖这个值
*/
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
/**
* 与此实例相关联的随机化值，该值应用于键的哈希码，以使哈希冲突更难找到。 如果为0，则禁用备用哈希。
*/
transient int hashSeed = 0;
private transient Set<Map.Entry<K,V>> entrySet = null;
// 序列化默认版本号
private static final long serialVersionUID = 362498820763181265L;构造器
/**
* 使用默认的容量16和负载因子0.75创建HashMap
*/
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 使用指定容量和默认的负载因子创建HashMap
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 使用指定容量和指定的负载因子创建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;
threshold = initialCapacity;
init();
}
/**
* 创建一个大于Map键值对数量的HashMap，然后将键值对加入到HashMap
* 使用默认的负载因子0.75，和足以包含Map键值对数量的容量
*/
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);
putAllForCreate(m);
}从构造方法来看，HashMap(int initialCapacity, float loadFactor)这个方法才是主体。接下来就来分析一下这个构造方法。
public HashMap(int initialCapacity, float loadFactor) {
// 容量小于0，抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 容量大于最大值1<<30，使用最大值当做容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 负载因子小于等于0或者非数字就抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
// 空方法，用来初始化HashMap，有些类里就会有其实现
init();
}数据结构
构造方法看完了，现在来看看HashMap的数据结构。JDK7的HashMap是以数组为主，链表为辅的结构。大概结构如下。
每个链表被称为哈希表的桶，每个节点都存储了一对键值对。
这里就看出，每个节点就是哈希表的最小组成单位了，现在就来看一下这个节点类。JDK7时的节点类叫Entry。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* 构造器
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
// get和set方法
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 重写equals
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
// 重写hashCode方法
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
// 重写toString方法
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* 在存在key下put，就会用该方法覆盖value值
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* 删除键值对时就会用这个方法
*/
void recordRemoval(HashMap<K,V> m) {
}
}由此可以看出每个Entry都存储了四个值，一对键值对，一个hash，和一个next值。next指向链表的下一个节点，而hash则用来判断该节点放在数组哪一个位置。
put
创建了哈希表之后，就可以用put方法来存放键值对，现在就来看看put方法的源码。
/**
* 将指定值与指定的键相连，如果指定的键原来有值，就会覆盖掉旧的值
* 返回与key关联的先前值；如果没有key的映射关系，则返回null 。
* 返回null可能还表明该映射先前将null与key关联。
*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}put方法有很多门道，现在我们就来一步步解析。
第一步
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}首先就是判断这个哈希表是不是一个空表。如果是就会调用inflateTable(threshold);这个方法，不是就进行下一步。我们去看看这个方法。
private void inflateTable(int toSize) {
// 计算出传入比传入容量大的最小的二次幂
int capacity = roundUpToPowerOf2(toSize);
// 重新计算阈值 threshold = 容量 * 负载因子
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 用最小的2次幂来创建一个新的数组
table = new Entry[capacity];
// 初始化哈希掩码值，将初始化推迟到我们真正需要它之前。
initHashSeedAsNeeded(capacity);
}这个方法就是用来创建数组的，通过roundUpToPowerOf2方法来确定最小的能大于需要长度toSize的二次幂，是有点绕，那现在去看看这个方法。
private static int roundUpToPowerOf2(int number) {
// 1.如果这个需要的长度大于最大值，就用最大值来创建数组
// 2.需要的长度小于1就用1当数组的长度，大于1就用highestOneBit方法来确定长度。
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 这个方法就是用来确定最小的二次幂
public static int highestOneBit(int i) {
// HD, Figure 3-1
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}寻找到最小的二次幂之后，重新计算阈值，然后用最小的2次幂来创建一个新的数组，最后用initHashSeedAsNeeded来初始化哈希掩码值。
第二步
if (key == null)
return putForNullKey(value);判断传入的key是不是null值，如果是就返回putForNullKey(value)，不然就下一步。现在来看看这个方法。
private V putForNullKey(V value) {
/**
* 遍历table[0]的链表，若有key==null，就用新的value覆盖原来的
* 然后返回被覆盖的value，所以table[0]就只会有一个元素
*/
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
/**
* 要是没有key==null的键，就调用addEntry方法，将空键和值放入table[0]
* 第一次table[0]是没有元素的，所以才能到这里添加空键和值
*/
addEntry(0, null, value, 0);
return null;
}第三步*
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}这步是最重要的一步，找到插入的位置然后将键值对插入到hashmap中。
首先就是调用hash方法来计算传入的key的哈希值。
/**
* 检索对象哈希码，并将补充哈希函数应用于结果哈希，以防止质量差的哈希函数。
* 这很关键，只有HashMap使用2的幂的哈希表，不然哈希表在低位无差异时会遇到冲突。
* 注意：空键始终映射到哈希0，因此索引为0。
*/
final int hash(Object k) {
int h = hashSeed;
// 若哈希值不为0而且不是String类型，就返回一个哈希值
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
// 异或
h ^= k.hashCode();
// 此函数可确保在每个位位置仅相差恒定倍数的hashCode具有一定数量的冲突（在默认的加载因子下约为8）。
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}得到哈希值之后，就会调用indexFor方法来计算出应该插入的位置。
/**
* 返回计算出来的索引
*/
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "长度必须为2的非零次幂";
// h & (length-1)表示hash值与数组长度求余，使用位移运算可以提高效率
// 为什么必须是2的非零次幂，之后还会提到
return h & (length-1);
}计算出具体插入的位置之后就开始插入了，这里就是用了一个for循环遍历。
// 遍历table[i]这个桶里是否存在这个key值，若有就将原来的value覆盖，并返回原来的value
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果哈希值相同，并且key值也相同，就进行替换
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值就将这对键值对加入到桶中
addEntry(hash, key, value, i);
// 第一次加入到桶就返回null值
return null;至此put的流程就结束了，到这里其实还是有问题。用indexFor这个方法来求数组的位置，刚刚也分析了这个方法，就是异或求余，那么就会有以下的问题，hash差为一定的倍数的时候，求余出来的下标就会是一样的，这个问题就是经常提到的哈希冲突。
为了解决哈希冲突这个问题，就引进了链表，也就是之前说的加入到桶中，这就是为什么哈希表底层是用数组和链表构成的了。下面讲讲大概是怎么用到链表的。
图中只是为了演示大概解决的过程，实现可以参考下面的createEntry方法和扩容中的transfer方法。由于哈希的计算会使数据尽量平均，而且扩容的时候又会重新计算下标，在数组长度较小的时候哈希冲突的发生的概率是很小的。
假设键值对3计算出来的i是3，就会被放到数组的第四个位置，直接放入。
假设键值对4计算出来的i是2，就会放到数组的第三个位置，但是这个位置已经有键值对1了，这种情况就会用到链表，头插到该链表。
但是如果是这种情况，就无法通过数组来寻找到键值对4了，所以还会变化一下指针的指向，最后就会变成这样。
addEntry
在上面put的第三步不难看到，在一个桶里只要有key相同，就覆盖，没有就使用addEntry这个方法加入到桶里。不难看出这个方法发生的情况，数组指定位置没有该元素或者是发生哈希冲突时就会用到这个方法，现在来看看这个方法。
/**
* 将具有指定键，值和哈希码的Entry添加到指定存储桶
* 如果有必要，该方法也会负责调整表的大小
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果当前数组长度大于阈值，并且该桶不是空的就执行下面语句
if ((size >= threshold) && (null != table[bucketIndex])) {
// 扩容到原来长度的两倍
resize(2 * table.length);
// key等于空，hash赋值为0，不然用hash方法获取哈希
hash = (null != key) ? hash(key) : 0;
// 因为扩容了，所以需要重新计算存储位置
bucketIndex = indexFor(hash, table.length);
}
// 创建Entry加入到桶里
createEntry(hash, key, value, bucketIndex);
}
/**
* 与addEntry类似，不同之处在于，在创建条目作为Map构造或“伪构造”（克隆，反序列化）的一部分时使用此版本。
* 此版本无需担心调整表的大小。
* 子类重写此方法，以更改HashMap（Map），克隆和readObject的行为。
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 这条语句就说明了哈希表链表的插入是头插的
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}扩容
刚刚看到addEntry中用resize方法来扩容，现在就来看看这个方法是怎么扩容的。先看看这个方法的源码。
/**
* 将此映射的内容重新映射到容量更大的新数组中。
* 当此映射中的键数达到其阈值时，将自动调用此方法。
* 如果当前容量为MAXIMUM_CAPACITY，则此方法不会调整地图的大小，而是将阈值设置为Integer.MAX_VALUE。
* 这具有防止将来通话的效果。
*
* @param 新容量必须是2的幂，而且是大于当前容量。
* 除非当前容量是MAXIMUM_CAPACITY，这种情况就无关紧要。
*/
void resize(int newCapacity) {
// 获取旧的数组和size的大小，判断是不是大于MAXIMUM_CAPACITY。
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 创建新的数组
Entry[] newTable = new Entry[newCapacity];
// 数据迁移，将原来数组的键值对放入新数组
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
// 重新设置阈值，等于新长度*负载因子或者MAXIMUM_CAPACITY + 1
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}resize方法是挺好理解的了，只有这个迁移函数有点讲究。
/**
* 将所有桶从当前表转移到newTable
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历数组
for (Entry<K,V> e : table) {
// 遍历桶
while(null != e) {
// 保存e的下一个节点，因为之后链表会断开
Entry<K,V> next = e.next;
// 重新计算e的hash和下标
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 后面这三句可以参考以下图示。
// 这条语句是挺奇怪的，之后也会导致一些问题出现，之后在说
e.next = newTable[i];
// 节点放到桶里
newTable[i] = e;
// 继续处理原来链表中的下一个节点
e = next;
}
}
}下面例子简化了长度，和一些细节，因为这样转移是很小几率的，只是为了展示转移方法的大概实现。
transfer方法和之前的createEntry方法，表明了1.7的哈希表为什么是头插的。因为头插，哈希表还会出现一些问题，之后还会提到。
get
get方法就没有put需要考虑到这么多情况了了，所以简单很多。
/**
* 返回指定键所映射到的null如果此映射不包含键的映射关系，则返回null 。
* 更正式地讲，如果此映射包含从键k到值v的映射，
* 使得(key==null ? k==null : key.equals(k)) ，则此方法返回v
* 否则返回null 。（最多可以有一个这样的映射。）
* 返回值null不一定表示该映射不包含该键的映射。 映射也可能将键显式映射为null 。
* containsKey操作可用于区分这两种情况
*/
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}第一步
if (key == null)
return getForNullKey();首先就是判断key值是不是为null，如果是null就调用getForNullKey。
/**
* get以查找空键。 空键映射到索引0。
* 为了在两个最常用的操作（获取和放置）中提高性能，此空情况被拆分为单独的方法，但在其他条件中并入了条件。
*/
private V getForNullKey() {
// 要是数组没有值就返回null
if (size == 0) {
return null;
}
// 遍历table[0]的桶，寻找key==null的value值，并返回
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
// 桶里没有就返回null
return null;
}第二步
Entry<K,V> entry = getEntry(key);
// entry为null，就返回null，不然就返回value
return null == entry ? null : entry.getValue();这两句也挺好理解的，用getEntry方法来获取键值对，然后返回value。
/**
* 返回与HashMap中的指定键关联的条目。 如果HashMap不包含该键的映射，则返回null
*/
final Entry<K,V> getEntry(Object key) {
// 数组为空返回null
if (size == 0) {
return null;
}
// 计算key的哈希值
int hash = (key == null) ? 0 : hash(key);
// 先通过哈希计算下标，然后遍历下标所在的桶，找到就返回entry，没找到就返回null
for (Entry<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;
}JDK8
JDK8优化了不少，但与JDK7在很多部分是一样的，所以我着重去分析一下不一样的地方。
参数和变量
// 相同的参数或者变量
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
transient int size;
transient int modCount;
final float loadFactor;
int threshold;
// JDK7独有的
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
transient int hashSeed = 0;
private transient Set<Map.Entry<K,V>> entrySet = null;
// JDK8独有的
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64; /**
* 该表在首次使用时初始化，并根据需要调整大小。
* 分配时，长度始终是2的幂。（在某些操作中，我们还允许长度为零，以允许使用当前不需要的引导机制。）
*/
transient Node<K,V>[] table;
/**
* 保存缓存的entrySet（）。 注意，AbstractMap字段用于keySet（）和values（）
*/
transient Set<Map.Entry<K,V>> entrySet;
// 链表的树化阈值，即链表长度大于8就会有可能转换成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 链表的还原阈值，即红黑树的节点小于6就换转换成链表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树形化阈值，数组长度大于64才会转换成红黑树
static final int MIN_TREEIFY_CAPACITY = 64;构造器
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // 其他字段默认
}
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;
// 上面与JDK7的一样，不一样的就是这句和省略了init初始化方法
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 与JDK7的实现有些不一样，但作用是一样的
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}可以看出只有两个比较特殊的地方，那就是tableSizeFor和putMapEntries这两个方法了。
/**
* 返回大于指定值的最小二次幂，作用类似highestOneBit方法
* 用来代替JDK7中的roundUpToPowerOf2方法
*/
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;
// 可认为将JDK7中roundUpToPowerOf2和highestOneBit方法合并了
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* 实现Map.putAll和Map构造函数。
* 将map中的元素加入到HashMap中去。
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
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);
}
}
}数据结构
JDK8的底层进行了一些优化，主体依旧是数组，链表为辅，但是链表过长会导致hashmap的查询效率变低 因为链表的查询操作的时间复杂度为O(n)，所以在JDK8中引入了红黑树。 当链表达到树化阈值的时候，就会转变为红黑树 因为红黑树的查询操作的时间复杂度为O(log(n))，所以可以提高查询桶里节点的效率