JCF之HashMap剖析 - JAVA - 编程开发网

HashMap
HashMap继承了模板类AbstractMap。其内部数据结构域Hashtable相同：
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* 长度必须是2的幂。原因后文会提高。
*/
transient Entry[] table;
Entry实现代码：
[java]
static class Entry implements Map.Entry {
final K key;/此处用final修饰
V value;
final int hash;
Entry next;

Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}

public K getKey() {
return HashMap.unmaskNull(key);
}

public V getValue() {
return value;
}

public V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}

public 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 int hashCode() {
return (key==NULL_KEY 0 : key.hashCode()) ^
(value==null 0 : value.hashCode());
}

public String toString() {
return getKey() + "=" + getValue();
}
}
这是HashMap的一个内部类，它实现了Map类中的一个Entry接口，可以看出，HashMap与Hashtable的内部数据结构形式是相同的。
static final int DEFAULT_INITIAL_CAPACITY = 16;//HashMap的默认大小为16，而Hashtable的为11
下面两个函数是Hashtable中所没有的：
[java]
//如果key为null，则将其设为NULL_KEY，而NULL_KEY 为一个Object对象
static T maskNull(T key) {
return key == null (T)NULL_KEY : key;
}
//如果key为NULL_KEY，则将其设为null
static T unmaskNull(T key) {
return (key == NULL_KEY null : key);
}
static final Object NULL_KEY = new Object();
这两个函数处理key为null的情况，如果为Null，则设置key为一个Object对象，这个对象是静态的，
且为final.,这表示如果有多个HashMap实例，那么所有的null key都会被设置成NULL_KEY。
这两个函数的存在意味着HashMap中是允许Null key 的。
下面来看看HashMap 的put方法，整体思路与Hashtable是相同的，但实现有些不同：
[java]
public V put(K key, V value) {
//处理key为null的情况，处理方式前面已经提到过
K k = maskNull(key);
//这是一个很大的不同:hash算法的不同
int hash = hash(k);
int i = indexFor(hash, table.length);//根据Hash值得到索引
for (Entry e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
//如果是同一个键，则用新值替代旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, k, value, i);
return null;
}

static int indexFor(int h, int length) {
//hash值与HashMap长度进行“与”运算，与Hashtable中的模运算不同
return h & (length-1);
}
//鉴于HashMap的长度是2的指数，为了提高Hash质量，设计了这个补充Hash函数
//( The shift distances in this function were chosen as the result
// of an automated search over the entire four-dimensional search space.
static int hash(Object x) {
//先得到x的hashCode
int h = x.hashCode();
//h+(h左移9位之后取反的结果)
h += ~(h << 9);
//h异或（h进行无符号右移14位之后的结果）
h ^= (h >>> 14);

JCF之HashMap剖析(一)