java.util.HashMap源码初探

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

数据结构：

数组

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

Entry

链表格式。

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

运行机制：

put、get

put方法

    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<K,V> 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方法

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

可以看出，重要的一句代码为：

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

这句代码的作用是判断两个Key对象是否“相同”，这里的相同的意思是指两个Key完全可以不分彼此，可以作为同一个Key使用。

在put方法中，如果两个Key的hashCode相同，且equals符合，这里是把原有的的value替换成新的value。

测试代码：

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<Key, Value> map = new HashMap<Key, Value>();
		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<Key2, Value> map = new HashMap<Key2, Value>();
		Key2 k1 = new Key2(1);
		Key2 k4 = new Key2(4);
		Value v1 = new Value(1);
		Value v4 = new Value(4);
		
		map.put(k1, v1);
		map.put(k4, v4); // 这里会替换掉v1
		
//		assertEquals(v1, map.get(k1));
		assertEquals(v4, map.get(k1));
		assertEquals(v4, map.get(k4));
	}
}

class Key {
	public int m;
	
	public Key(int m) {
		this.m = m;
	}
	
	@Override
	public int hashCode() {
		return m%3;
	}
}

class Value {
	public int m;
	
	public Value(int m) {
		this.m = m;
	}
}

class Key2 {
	public int m;
	
	public Key2(int m) {
		this.m = m;
	}
	
	@Override
	public int hashCode() {
		return m%3;
	}
	
	@Override
	public boolean equals(Object obj) {
		if(obj == null || !(obj instanceof Key2)) return false;
		
		Key2 other = (Key2)obj;
		
		return this.hashCode() == other.hashCode();
	}
}