HashMap是java开发中很长用的类，之前对HashMap的理解仅仅停留在日常的使用上，今天尝试从源码去理解下HashMap。首先来看一下源码中HashMap的定义：
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
可以看到HashMap实现了Map接口，这个接口也是java集合框架的一个基础接口。说一下不重要的小插曲，其实HashMap继承了AbstractMap这个类，就不必要再写实现Map接口了，因为在AbstractMap已经实现了Map接口，这么做的原因可能是为了更加明确表明HashMap是一个Map，具备Map的一些最基本的特征。关于这方面的一些思考和讨论，可以在这里看到一些大神的回复。其实上面这个不必要写的“implements Map”也从侧面证明了Map才是HashMap最重要的特征，那么我们下面就来看看HashMap是如何实现Map的2个最基本的方法：put和get。先来看get方法和相关的2个方法：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<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;
}
int hash = (key == null) ? 0 : hash(key);
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;
}
可以看到，get方法的核心就是这个getEntry方法，即通过key来获取到对应的Entry。那么，这个Entry究竟又是个什么类呢？
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
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;
}
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;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
/**
* This method is invoked whenever the value in an entry is
* overwritten by an invocation of put(k,v) for a key k that's already
* in the HashMap.
*/
void recordAccess(HashMap<K,V> m) {
}
/**
* This method is invoked whenever the entry is
* removed from the table.
*/
void recordRemoval(HashMap<K,V> m) {
}
}
从源码中可以看到，这里的Entry其实是一个HashMap的一个内部类，实现了Map.Entry这个接口。Entry是HashMap存储数据的基本类型，一个Entry是一个键值对。
知道了Entry，再来看回到HashMap的get方法，这里首先用一个hash方法来求出了key的hash值，然后从求出Entry.key的hash值和hash相等的Entry，注意，这里并不是只有这一个条件，还有一个安全性校验“key.equals(k)”，这一步必不可少，因为求hash的过程是一个散列的过程，是一个把无限的空间映射到有限（size）个槽的过程，那么这个过程就可能会出现hash碰撞，就是2个不一样的key，但是它们的hash值是相等的，这一步安全性的校验也是保证了在这种情况发生时依然可以取到正确的值。那么可能有人要问了，既然最后都要用equals方法来做安全性校验，为什么不直接使用equals方法来逐个比较，这样还不需要求出key的hash值了？其实这就是个效率和代价的问题，Object的equals方法代码相对比较大，效率低，而这个int的hash值比较代价就很小，而且如果hash算法设计合理，可以说在绝大多数的情况下，不同的key会对应到不同的hash值。顺便说一下，对于String的switch运算也运用了类似的先求hash值来提高效率，然后用equals方法做安全性校验。
hash的实现方法可以有很多种，HashMap中的hash方法这里一定要介绍一下，这个hash方法其实和HashMap的大小是关联的，理解这个有助于我们后面会讲的如何高效使用HashMap。
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
如果觉得这个方法理解起来比较繁琐，没关系，我们只要知道这里的hash值是通过“位运算”来计算求出来即可。“位运算”应该是效率最高的一种运算，这样可以保证对key求hash的过程代价很小，这点其实很重要，如果求hash的过程比直接equals并没有更加高效，就没必要绕着一圈来求hash值了，直接用equals比较key就好了。
简单总结下：
- HashMap中存储的基本结构是Entry（键值对）。
- HashMap根据key来获取value的时候，首先对key求hash，然后根据hash值来过滤出符合条件Entry，然后用equals方法进行安全性校验，以应对hash碰撞的情况。
- 可以把HashMap看作一组木桶，put方法就是把1个Entry扔进其中1个木桶的过程，通过Entry.key求hash值来决定扔进哪一个木桶。
最后，放一个简单的HashMap的存储的示意图：
HashMap存储结构
网友评论