Java容器HashMap解读

在JDK里面比较复杂的数据结构估计也就Map的相关类,基本上是阿里面试必问题目.本文总结下HashMap相关的实现.包含了内部数据结构,哈希冲突以及线程安全方面的内容.

首先,来点理论知识,请注意图中的文字.

直接寻址表

如图是一个典型的直接寻址表.执行起来很快,只需要O(1)时间.然而直接寻址表存在着一个明显的问题:如果域U很大在一个典型的计算机的可用内存容量限制下,要在机器中存储大小为|U|的一张表T就有点不实际,甚至有点不可能.当实际要存储的关键字集合K相对U来说可能很小的时候,分配给T的空间就白白浪费了.为了解决这个问题就衍生出一个数据结构散列表.当实际要存储的关键字集合K相对U来说可能很小的时候,散列表需要的存储空间比直接寻址表少的多.

散列表

如上图,在直接寻址方式下,具有关键字的元素被存放在槽k中.在散列的方式下被存放到h(k)中,即利用散列函数h,根据关键字k计算出槽的位置.那么问题又来了,两个关键字可能映射到同一个槽上,即发生碰撞(也叫哈希冲突).最理想的方法就是就是完全避免碰撞,要做到这点就要选择合适的散列函数,使h尽可能的随机,从而避免或者至少最小化碰撞.然而关键字U域大于T的大小的时候,碰撞时不可避免的.所以我们一方面可以精心设计散列函数避免碰撞.一方面仍然要有解决碰撞的方法.最简单的方法就是链接法.结构如下图所示.

碰撞链接法

那么到这里应该知道,HashMap的结构了吧.它就是散列表.好吧,我们可以看下源码.

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;

	Node(int hash, K key, V value, Node<K,V> 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;
	}
}

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
int threshold;

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor;

上述代码介绍了几个重要变量和一个结构体.Node是一个典型的链表节点实现.table是一个数组,类型就是Node,也就是说table就是上文所介绍的存放槽的寻址表格.类型为Node也就是定位到table的某个位置,即定位到了一整个hash冲突的单向链表.loadFactor为装载因子,结合上面的图例,可定义为给定一个能存放n个元素的具有m个槽位的散列表T,定义T的装载因子为n/m,即一个链中平均存储的元素个数.threshold为阀值,也就是标记元素的上限数,一旦达到则扩充table的大小.接下来看看put和get方法方法.

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

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)
		n = (tab = resize()).length;
	
	if ((p = tab[i = (n - 1) & hash]) == null)//槽位上是否已经存在数据了
		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))))//判断不是hash冲突,即key相等,hash相等
			e = p;
		else if (p instanceof TreeNode)//判断是不是TreeMap的节点类型
			e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
		else {//hash冲突的处理
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {//与现有的元素存在hash冲突,即加入链表的末端
					p.next = newNode(hash, key, value, null);
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))//判断不是hash冲突,即key相等,hash相等
					break;
				p = e;
			}
		}
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	if (++size > threshold)//到达阀值,则resize散列表
		resize();
	afterNodeInsertion(evict);
	return null;
}

public V get(Object key) {
	Node<K,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> 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<K,V>)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;
}

put方法主要也是检测hash冲突的存在,决定元素放的位置.我们可以看到每次新增元素都会判断阀值,以确认是否需要resize(),所以在给定元素大小的情况下new HashMap()不给定初始化容量的方式是不可取,这样会导致其resize()消耗计算资源.对于get很简单,也就是直接寻址,然后再遍历链表.时间复杂度取决于链表的大小.避免hash冲突还是很有必要的.

至此,HashMap的结构算是很清晰,还有一个问题就是线程安全方面.它是非线程安全的,经常有人拿它与Hashtable对比.Hashtable也是implements了Map接口.它的主要方法都加入了synchronized.也就是意味着他的方法在多线程情况下不可以重入,那么来个假设.多个线程往不同的槽位写入数据的时候是不可并行的,因为方法锁住了,特别重量级的一个选手.所以就有了CocurrentHashMap,它的实现几乎跟HashMap一致.只不过是加入了线程安全机制,那么我们通过其put方法来看看是如何做到的.

final V putVal(K key, V value, boolean onlyIfAbsent) {
	if (key == null || value == null) throw new NullPointerException();
	int hash = spread(key.hashCode());
	int binCount = 0;
	for (Node<K,V>[] tab = table;;) {
		Node<K,V> f; int n, i, fh;
		if (tab == null || (n = tab.length) == 0)
			tab = initTable();
		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
			if (casTabAt(tab, i, null,
						 new Node<K,V>(hash, key, value, null)))
				break;                   // no lock when adding to empty bin
		}
		else if ((fh = f.hash) == MOVED)
			tab = helpTransfer(tab, f);
		else {
			V oldVal = null;
			synchronized (f) {//同步块
				if (tabAt(tab, i) == f) {
					if (fh >= 0) {
						binCount = 1;
						for (Node<K,V> e = f;; ++binCount) {
							K ek;
							if (e.hash == hash &&
								((ek = e.key) == key ||
								 (ek != null && key.equals(ek)))) {
								oldVal = e.val;
								if (!onlyIfAbsent)
									e.val = value;
								break;
							}
							Node<K,V> pred = e;
							if ((e = e.next) == null) {
								pred.next = new Node<K,V>(hash, key,
														  value, null);
								break;
							}
						}
					}
					else if (f instanceof TreeBin) {
						Node<K,V> p;
						binCount = 2;
						if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
													   value)) != null) {
							oldVal = p.val;
							if (!onlyIfAbsent)
								p.val = value;
						}
					}
				}
			}
			if (binCount != 0) {
				if (binCount >= TREEIFY_THRESHOLD)
					treeifyBin(tab, i);
				if (oldVal != null)
					return oldVal;
				break;
			}
		}
	}
	addCount(1L, binCount);
	return null;
}

上述代码的synchronized 是加在一个对象上,也就是table的某个位置,即寻址表的槽位,多个线程同时修改不同槽位上链表的数据是不需要等待的,只有在hash冲突的时候需要进入同步方法块.所以CocurrentHashMap的并发程度高了不止一个档次,却又是线程安全的.OK,到此为止,有兴趣的可以看更多的源码,基础思想就是这样.掌握本文你就可以和面试官多20分钟的谈资.

PS:前半部分理论可参阅我8年都不曾看完的<<算法导论>>第2版,第11章.



留个爪印