跟我一起阅读Java源代码之HashMap（三）

上一节我们讲到了如何用散列和链表实现HashMap，其中有一个疑问今天已经有些答案了，为什么要用链表而不是数组

链表的作用有如下两点好处

1. remove操作时效率高，只维护指针的变化即可，无需进行移位操作

2. 重新散列时，原来散落在同一个槽中的元素可能会被散落在不同的地方，对于数组需要进行移位操作，而链表只需维护指针

今天研究下数组长度不够时的处理办法

table为散列数组

1. 首先定义一个不可修改的静态变量存储table的初始大小 DEFAULT_INITIAL_CAPACITY

2. 定义一个全局变量存储table的实际元素长度，size

3. 定义一个全局变量存储临界点，即元素的size>=threshold这个临界点时，扩大table的容量

4. 因为index是根据hash和table的长度计算得到的，所以还需要重新对所有元素进行散列

实现如下：

public class EntryHashMap<K, V> {

	/** 初始容量 */
	static final int DEFAULT_INITIAL_CAPACITY = 16;

	static final float DEFAULT_LOAD_FACTOR = 0.75f;

	/** 下次扩容的临界值 */
	int threshold;

	transient int size;

	final float loadFactor;

	transient Entry[] table;

	public EntryHashMap() {
		this.loadFactor = DEFAULT_LOAD_FACTOR;
		threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
		table = new Entry[DEFAULT_INITIAL_CAPACITY];
	}

	public V put(K key, V value) {
		// 计算出新的hash
		int hash = hash(key.hashCode());
		// 计算出数组小标i
		int i = indexFor(hash, table.length);
		// 遍历table[i]，如果table[i]没有与新加入的key相等的，则新加入
		// 一个value到table[i]中的entry，否则将新的value覆盖旧的value并返回旧的value
		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;
				return oldValue;
			}
		}
		addEntry(hash, key, value, i);
		return null;
	}

	public V get(K key) {
		// 计算出新的hash
		int hash = hash(key.hashCode());
		// 计算出数组小标i
		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))) {
				return e.value;
			}
		}
		return null;
	}

	private void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		// 将新的元素插入链表前端
		table[bucketIndex] = new Entry<>(hash, key, value, e);
		if (size++ >= threshold)
			resize(2 * table.length);
	}

	/**
	 * 扩展散列表的容量
	 * @param newCapacity
	 */
	void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

	/**
	 * 重新进行散列
	 * @param newTable
	 */
	void transfer(Entry[] newTable) {
		Entry[] src = table;
		int newCapacity = newTable.length;
		for (int j = 0; j < src.length; j++) {
			Entry<K, V> e = src[j];
			if (e != null) {
				src[j] = null;
				do {
					Entry<K, V> next = e.next;
					int i = indexFor(e.hash, newCapacity);
					e.next = newTable[i];
					newTable[i] = e;
					e = next;
				} while (e != null);
			}
		}
	}

	/**
	 * 通过hash code 和table的length得到对应的数组下标
	 * 
	 * @param h
	 * @param length
	 * @return
	 */
	static int indexFor(int h, int length) {
		return h & (length - 1);
	}

	/**
	 * 通过一定算法计算出新的hash值
	 * 
	 * @param h
	 * @return
	 */
	static int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	public static void main(String[] args) {
		EntryHashMap<String, String> hashMap = new EntryHashMap<String, String>();
		hashMap.put("key", "value");
		System.out.println(hashMap.get("key"));
	}
}