java.util.HashMap源码初探 (一)

对于一个存储类的分析，无非从两点入手：存储用的数据结构，存储的运行机制。

数据结构：

数组

[java]
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;

/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;
Entry

链表格式。

也即，HashMap中采用的是“链接法”来处理碰撞问题的。

运行机制：

put、get

put方法

[java]
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}
get方法

[java]
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry 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;
}

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry 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;
}
可以看出，重要的一句代码为：

[java]
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

这句代码的作用是判断两个Key对象是否“相同”，这里的相同的意思是指两个Key完全可以不分彼此，可以作为同一个Key使用。
在put方法中，如果两个Key的hashCode相同，且equals符合，这里是把原有的的value替换成新的value。

测试代码：

[java]
package test.junit;

import java.util.HashMap;

import junit.framework.TestCase;

/**
* HashMap中判断两个Key是否相同：先判断hashCode，在判断是否equals
* e.hash == hash && ((k = e.key) == key || key.equals(k))
* @author xuefeng
*
*/
public class HashMapTest extends TestCase {

/**
* v1和v4的hashCode相同，但是equals不符合，所以v1和v4会组成一个链表。
*/
public void testKey1() {
HashMap map = new HashMap();
Key k1 = new Key(1);
Key k4 = new Key(4);
Value v1 = new Value(1);
Value v4 = new Value(4);

map.put(k1, v1);
map.put(k4, v4);

assertEquals(v1, map.get(k1));
assertEquals(v4, map.get(k4));
}

/**
* v1和v4的hashCode相同，而且equals也符合，所以v1会被v4替换掉，k1和k4指向同一个v4。
*/
public void testKey2() {
HashMap map = new HashMap();
Key2 k1 = new Key2(1);
Key2 k4 = new Key2