Java集合(七)--基于jdk1.8的HashMap源码

一、背景：

HashMap在开发中经常用，面试源码方面也会经常问到，今天总结一下，包括在后面有相关面试题。

本文不会对红黑树代码由太多深入研究，特别是删除方面太复杂，面试也不会问到，知道红黑树基本实现原理就可以了。

源码基于jdk1.8，我们都知道1.8版本的HashMap有很大改变，通过数组+链表+红黑树实现。

二、图例：

关于链表和红黑树相关内容，可以参考：

三、源码：

1、基本结构：

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;
}

继承了AbstractMap，实现Cloneable和Serializable接口，可以实现clone、序列化以及反序列化。

2、成员变量：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量16，容量一定是2的次幂

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;	// 解除树形化阈值，也就是当链表的节点个数小于等于这个值时，会将红黑树转换成普通的链表

// 树形化的另一条件Map数组的长度阈值64。当数组的长度小于这个值时，就算树形化阈达标，链表也不会转化为红黑树，而是优先扩容数组resize()
static final int MIN_TREEIFY_CAPACITY = 64;

transient Node[] table;	// 保存元素的内部数组

transient Set> entrySet;	// 保存Entry的set

transient int size;	// 当前存储的键值对的数量

transient int modCount;	// 集合被修改的次数，用于迭代器的快速失败

int threshold;	// 阈值=Capacity*loadFactor

final float loadFactor;	// 加载因子

3、构造方法：

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)	// 初始容量<0，抛出异常
		throw new IllegalArgumentException("Illegal initial capacity: " +
										   initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)	// 初始容量 > MAXIMUM_CAPACITY，赋值为MAXIMUM_CAPACITY
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))	// 初始容量<0，或者不是数字，抛出异常
		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
	this.loadFactor = loadFactor;
	this.threshold = tableSizeFor(initialCapacity);	// 初始容量，返回的是initialCapacity的最小二次幂
}

5、tableSizeFor()：

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;
}

.>>>无符号右移，高位补0，最终返回最小二次幂，例如：cap=13，返回16，cap=17，返回32，因为容量要求为2的次幂。

6、Node：

static class Node implements Map.Entry {
	final int hash;	//key的hash值
	final K key;
	V value;
	Node next;	//next node	

	Node(int hash, K key, V value, Node next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}

	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;
	}
}

Node为HashMap的内部类，就是单向链表，比较简单。

TreeNode为红黑树的实现，看看就行，容易看的脑阔疼。

7、put()：

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);	// 调用putVal()
}

// onlyIfAbsent为false，可以update oldValue，为true，不会update
// evict为false，处于创建模式，HashMap中不起作用，在LinkedHashMap有作用
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node[] tab; Node p; int n, i;
	if ((tab = table) == null || (n = tab.length) == 0)	// 如果当前数组为null，或者数组的length为0，进行扩容(有初始化的作用)
		n = (tab = resize()).length;
	if ((p = tab[i = (n - 1) & hash]) == null)	// (n-1)&hash就是寻址，找到key对应的下标，对应位置如果没有数据，直接生成一个新的节点
		tab[i] = newNode(hash, key, value, null);
	else {	// 否则对应下标有值
		Node e; K k;
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))	// key对应位置的首节点和key相同，直接覆盖value
			e = p;
		else if (p instanceof TreeNode)	// 如果首节点是红黑树
			e = ((TreeNode)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) //如果>=8-1，尝试进行树形化
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;	//
			}
		}
		if (e != null) { // 覆盖oldValue
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;	// 修改次数+1
	if (++size > threshold)	// 如果元素个数大于阈值，进行扩容
		resize();
	afterNodeInsertion(evict);
	return null;
}

添加/修改流程：

1、判断数据是否为空，如果为null，通过resize()进行初始化

2、如果key对应位置为null，直接生成节点，假如数组对应位置

3、否则就是可以对应位置有值

　　3.1).变量p为key对应位置节点，如果直接和key相等，也就是这个node只是一个节点，不是链表或者红黑树，直接通过变量e保存p

　　3.2).如果p instanceof 为红黑树，添加到红黑树

　　3.3).如果p为链表，循环链表是否有对应key，true先保存下来，false，key对应节点添加到尾部，并判断链表长度是否 > TREEIFY_THRESHOLD - 1 = 7，true，尝试进行树形化

final void treeifyBin(Node[] tab, int hash) {
	int n, index; Node e;
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)	//判断数组长度与MIN_TREEIFY_CAPACITY，不大于64的情况下，进行扩容，而不是树形化
		resize();
	else if ((e = tab[index = (n - 1) & hash]) != null) {	//树形化的具体步骤
		TreeNode hd = null, tl = null;
		//省略后面代码
	}
}

4、覆盖oldValue

5、判断是否扩容

resize()：
final Node[] resize() {
	Node[] oldTab = table;
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	int oldThr = threshold;
	int newCap, newThr = 0;
	if (oldCap > 0) {	
		if (oldCap >= MAXIMUM_CAPACITY) {// oldCapacity > MAXIMUM_CAPACITY，赋值Integer.MAX_VALUE，直接返回
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				 oldCap >= DEFAULT_INITIAL_CAPACITY)	// 否则扩容为oldThreshold的2倍
			newThr = oldThr << 1; // double threshold
	}
	else if (oldThr > 0) // oldCap = 0，oldThr > 0，将oldThr赋值给newCap
		newCap = oldThr;
	else {               // oldCap = 0，oldThr = 0，进行初始化
		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[] newTab = (Node[])new Node[newCap];	// 生成一个新的数组
	table = newTab;
	if (oldTab != null) {
		for (int j = 0; j < oldCap; ++j) {
			Node e;
			if ((e = oldTab[j]) != null) {	// 如果对应下标有值
				oldTab[j] = null;	// oldTab对应下标设置为null，便于GC
				if (e.next == null)	// 如果对应下标位置只是数组，赋值到新数组
					newTab[e.hash & (newCap - 1)] = e;
				else if (e instanceof TreeNode)	// 如果对应下标位置为红黑树
					((TreeNode)e).split(this, newTab, j, oldCap);
				else { //如果对应下标位置为链表
					Node loHead = null, loTail = null;	// 需要存放到原来的位置
					Node hiHead = null, hiTail = null;	// 需要存放到原来的位置 + oldCap
					Node next;
					do {
						next = e.next;
						if ((e.hash & oldCap) == 0) {	// hash对应oldCap的bit为0
							if (loTail == null)
								loHead = e;
							else
								loTail.next = e;
							loTail = e;
						}
						else {	//hash对应oldCap的bit为1
							if (hiTail == null)
								hiHead = e;
							else
								hiTail.next = e;
							hiTail = e;
						}
					} while ((e = next) != null);
					if (loTail != null) {	// hash对应oldCap的bit为0的key放到原位
						loTail.next = null;
						newTab[j] = loHead;
					}
					if (hiTail != null) {	// hash对应oldCap的bit为1的key放到原位 + oldCap
						hiTail.next = null;
						newTab[j + oldCap] = hiHead;
					}
				}
			}
		}
	}
	return newTab;
}

resize()在jdk1.8和之前版本的区别：

举例：oldCapacity=8，之前hash等于3，11，19，27的key，index都是3

jdk1.7：需要重新对地址重新寻址，扩容之后Capacity=16，index分别为3，11，3，11，但是有一点是会把之前index的数据先添加到链表的尾部，再把链表添加到对应数组位置，所以会导致同一位置的数据发生倒置，代码如下

int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;

jdk1.8：不需要进行重新hash，上述四个key，通过hash&oldCapacity分别得到：0，8，0，8，结果为0的，保存到原index，其他保存在原index + oldCapacity，而且hash冲突的数据扩容之后不会倒置。

总结：是否rehash、hash冲突的数据顺序是两个版本的主要区别。

PS：原数组如果存在null，扩容之后null仍然存在。

8、remove()：

public V remove(Object key) {
	Node e;
	return (e = removeNode(hash(key), key, null, false, true)) == null ?
		null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
						   boolean matchValue, boolean movable) {
	Node[] tab; Node p; int n, index;
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(p = tab[index = (n - 1) & hash]) != null) {	//hash对应位置的数据不为null
		Node node = null, e; K k; V v;
		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)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);
			}
		}
		if (node != null && (!matchValue || (v = node.value) == value ||
							 (value != null && value.equals(v)))) {				//对应这三种情况，分别删除
			if (node instanceof TreeNode)
				((TreeNode)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;
}

9、get()：

public V get(Object key) {
	Node e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
	Node[] tab; Node 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)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;
}

也没啥好说的，也是三种情况下(数组、红黑树、链表)的搜索。

10、遍历：

public static void main(String[] args) throws IOException {
	HashMap map = new HashMap(4);
	map.put(1, "a");
	map.put(2, "b");
	map.put(3, "c");
	map.put(4, "d");
	map.keySet().forEach((key) -> {
		System.out.println(key + " " + map.get(key));
	});
	map.values().forEach((value) -> {
		System.out.println(value);
	});
	Set> entry = map.entrySet();
	entry.forEach((entry1) -> {
		System.out.println(entry1.getKey() + " " + entry1.getValue());
	});
	Iterator> iterator = map.entrySet().iterator();
	while(iterator.hasNext()){
		Map.Entry mapEntry = iterator.next();
		System.out.println(mapEntry.getKey() + " " + mapEntry.getValue());
	}
}

如果只是获取key/value，可以使用keySet()和values()。

否则建议使用后两种。

四、面试题：

1、为什么HashMap的Capacity要保持2的次幂？

1).因为HashMap寻址通过(length - 1) & hash，如果length不是2的次幂，例如10，通过前面的表达式，很多位置永远不可能被使用，例如0001，0100等。

也就不能通过(length - 1) & hash来实现取模，位运算的效率是远远高于取余%运算的。包括resize()操作等，这些实现都需要修改。

2).如果不是这样计算下标位置的方法不能通过(length - 1) & hash实现，因为[]table有些位置永远不可能被占用，从而造成浪费。所以HashMap通过tableSizeFor()来保证Capacity一定是2的次幂。

2、jdk1.8和之前版本对于HashMap实现的区别？

1、取消了成员变量Capacity，保存到threshold。

2、链表和红黑树的转化，有两个条件，链表到红黑树的查询效率：从O(N)变成O(logn)。

3、扩容resize()实现不同。

4、hash()实现不同。

3、HashMap的Node[]序列化

和其他集合的实现相同，都是通过重写writeObject()和readObject()实现自定义序列化，把Node[]通过transient修饰。

4、HashMap的table为什么是transient的

因为HashMap是基于HashCode的，HashCode作为Object的方法，是native的。

这意味着HashCode和底层实现相关，不同的虚拟机可能有不同的HashCode算法。再进一步说得明白些就是，可能同一个Key在虚拟机A上的HashCode=1，在虚拟机B上的HashCode=2，在虚拟机C上的HashCode=3。

所以自己通过writeObject()达到序列化的目的。

5、hashmap和hashtable区别：

1、HashMap的初始容量为16，扩容为2倍，Hashtable初始容量为11，扩容为2倍+1，两者的填充因子默认都是0.75。

2、HashMap和Hashtable的底层实现都是数组+链表结构实现。

3、两者计算hash的方法不同。

4、hashtable的key和value都不能为null，而hashmap都可以。

5、hashtable线程安全，hashmap线程不安全。

6、HashMap的key和value能为null吗？

key和value都可以为null，但是只能保存一个。key为null的元素保存在数组的下标0位置。

发生扩容null照样存在。

HashMap map = new HashMap(4);
map.put(null, null);
map.put(null, null);
map.put(2, "b");
map.put(3, "c");
map.put(4, "d");
map.put(5, "d");
Set> entry = map.entrySet();
entry.forEach((entry1) -> {
	System.out.println(entry1.getKey() + " " + entry1.getValue());
});
输出结果：
null null
2 b
3 c
4 d
5 d

内容参考：一文搞定HashMap的实现原理和面试 - 掘金