HashMap的源码解读

最近看到几篇精彩的文章:

存取之美 —— HashMap原理、源码、实践

Hash碰撞与拒绝服务攻击

这些文章让我收获良多, 但是有些地方说的不够详细, 在此写下本人对上述文章的总结和理解, 希望可以给需要的朋友带来一些帮助.

1. 概述

HashMap在底层采用数组+链表的形式存储键值对.

在HashMap中定义了一个内部类Entry<K, V>, 该内部类是对key-value的抽象. Entry类包含4个成员: key, value, hash, next. key和value的意义很清晰, hash表示key的hash值, next是指向下一个Entry对象的引用.

HashMap内部维护了一个Entry<K, V>[] table, 数组table中的Entry元素是一个Entry链表的头结点(理解这一点很重要). 

2. put/get方法

向HashMap中添加键值对时, 程序会根据key的hashCode值计算出hash值, 然后对hash值取模, 模数是table.length. 假如取模的结果为index, 则取出table[index]. table[index]可能为null, 也可能是一个Entry对象. 如果为null, 则直接存储. 否则计算key.equals(table[index].key), 如果为false, 就取出table[index].next, 继续调用key的equals方法, 直到equals方法返回true, 或者比较完链表中所有Entry对象.

public V put(K key, V value) {
	if (key == null)
		return putForNullKey(value);
	// 对hashCode值进行二次hash得到最终的hash值
	int hash = hash(key.hashCode());
	// 根据hash值定位数组中的索引位置
	int i = indexFor(hash, table.length);
	// 遍历table[i]位置处的链表
	for (Entry<K, V> e = table[i]; e != null; e = e.next) {
		Object k;
		// 如果hash值相同且equals返回true, 则替换原来的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++;
	// 如果之前函数没有return, 将该键值对插入table[i]链表中
	addEntry(hash, key, value, i);
	return null;
}

理解了put方法, 那么get方法就会很容易理解:

public V get(Object key) {
	if (key == null)
		return getForNullKey();
	int hash = hash(key.hashCode());
	// 首先根据hash值计算index, 然后取出index处的链表的头结点. 遍历链表.
	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.equals(k)))
			return e.value;
	}
	return null;
}

  

3. HashMap的容量和索引位置确定

前面没有叙述HashMap的容量问题, 是因为容量是与索引位置计算紧密相关的.

理解HashMap的容量就需要关注成员变量size, loadFactor, threshold.

size表示HashMap中实际包含的键值对个数.

loadFactor表示负载因子, loadFactor的值越大, 则对table数组的利用率越大, 相当于节省内存空间. 但是loadFactor的值增大, 同时也会导致hash冲突的概率增加, 从而使得程序效率降低. loadFactor的取值应该兼顾内存空间和效率, 默认值为0.75.

threshold表示极限容量, 计算公式为threshold = (int)(capacity * loadFactor);  当size达到threshold时, 就需要对table数组扩容.

HashMap的容量大小就是table.length. 由于java中取模是一个效率低下的操作, 所以出于性能的考虑, HashMap的容量被设计为2的N次方. 如此hash%table.length就可以转换为hash&(table.length-1). 与运算的效率比取模运算高效很多.

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

	// 计算大于initialCapacity的最小的2的N次方数
	int capacity = 1;
	while (capacity < initialCapacity)
		capacity <<= 1;

	this.loadFactor = loadFactor;
	// 求出极限容量
	threshold = (int) (capacity * loadFactor);
	// table的容量被设计为2的N次方
	table = new Entry[capacity];
	init();
}

如果使用无参的构造函数创建HashMap, 则容量默认为16, 负载因子默认为0.75.

indexFor函数用于确定索引位置:

static int indexFor(int h, int length) {
	// 当length为2的N次方时相当于h%table.length, 但效率要高效很多
	return h & (length - 1);
}

 

4. rehash

前面提到过, 当size达到threshold时, 就需要对table数组扩容. 调用put函数向HashMap中插入一个键值对时会调用到addEntry(hash, key, value, i)方法:

void addEntry(int hash, K key, V value, int bucketIndex) {
	// 取出索引处的Entry对象
	Entry<K, V> e = table[bucketIndex];
	// 更新索引处链表的头结点, 并使新的头结点的next属性指向原来的头结点
	table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
	// 当size大于threshold时扩容数组, 容量增加至原来的2倍. 保证table的容量始终是2的N次方
	if (size++ >= threshold)
		resize(2 * table.length);
}

resize用于扩容数组. 数组的length增加大了, 那么HashMap中已有的键值对就必须重新进行hash, 这就是rehash. 如果不进行rehash, 就会使得put和get时table数组的length不同, 从而导致get方法无法取出原先put存入的键值对.

void resize(int newCapacity) {
	Entry[] oldTable = table;
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}

	Entry[] newTable = new Entry[newCapacity];
	transfer(newTable);
	table = newTable;
	threshold = (int) (newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
	Entry[] src = table;
	int newCapacity = newTable.length;
	// 对已有的键值对进行rehash
	for (int j = 0; j < src.length; j++) {
		// 得到j处的链表的头结点
		Entry<K, V> e = src[j];
		// 遍历链表
		if (e != null) {
			src[j] = null;
			do {
				// 进行rehash
				Entry<K, V> next = e.next;
				int i = indexFor(e.hash, newCapacity);
				e.next = newTable[i];
				newTable[i] = e;
				e = next;
			} while (e != null);
		}
	}
}

从源码可以看出, rehash对性能的影响是非常大的, 因此我们应该尽量避免rehash的发生. 这就要求我们预估需要存入HashMap的键值对的数量, 根据数量在创建HashMap对象时指定合适的容量和负载因子.

5. hash碰撞和HashMap的退化

hash碰撞在HashMap中的表现为: 不同的key, 计算出相同的index. 如果对所有的key调用indexFor方法的返回值都是相同的, 那么HashMap就退化为链表, 这对性能的影响也是非常大的. 几个月前的闹得沸沸扬扬的hash碰撞攻击就是基于这样的原理.

常用的web框架都会将请求中的参数保存在HashMap(或HashTable)中, 如果客户端根据Web应用框架采用的Hash函数来通过某种Hash攻击的方式获得大量的碰撞, 那么HashMap就会退化为链表, 服务器有可能处理一次请求要花上十几分钟甚至几个小时的时间...

6. 线程安全

HashMap是线程不安全的, 如果遍历HashMap的过程中修改了HashMap, 那么就会抛出java.util.ConcurrentModificationException异常:

final Entry<K, V> nextEntry() {
	if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	Entry<K, V> e = next;
	if (e == null)
		throw new NoSuchElementException();

	if ((next = e.next) == null) {
		Entry[] t = table;
		while (index < t.length && (next = t[index++]) == null)
			;
	}
	current = e;
	return e;
}

modCount是HashMap的成员变量, 用于表示HashMap的状态. expectedModCount是遍历初始时modCount的值. 如果在遍历过程中改变了modCount的值就会导致modCount和expectedModCount不相等, 从而抛出异常. put, clear, remove等方法都会导致modCount的值改变.

 

评论

3 楼 peakmuma 2014-07-30  

讲的很好！

2 楼 heipacker 2013-10-12  

这个也不错！

1 楼 draem0507 2013-06-18  

nice