HashMap 之我见

package com.util;

import java.io.IOException;
import java.io.Serializable;
import java.util.AbstractCollection;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * 本人水平有限，小文的目的是为了说明一些HashMap的实现方法同时分享一些规避错误的使用方法。
 * 更重要的目的是想抛砖引玉，吸引大家对HashMap这个数据结构的讨论，在Java的开发中，通过我使用
 * Jprofiler这个工具的分析，HashMap的实例数是仅次于String的。
 * 所以，在我们关注、纠结String这个对象的使用方法时，也不能忽视了这个重要的数据结构HashMap。
 * 
 * 要了解HashMap你需要了解java的位运算、散列码算法、链表、多线程等知识。
 * 为了更好的说明情况，我展示了一些有删节的代码，并对一些重要的方法写了详细的注释。
 */

/**
 * HashMap就是哈希表（这个表指的是key-value pairs），属于数据结构的一种，各种语言都有HashMap的实现
 * 例如c/c++,c#,java etc...，下面列出c这个过程性语言的HasHap结构体的定义：
 * <pre>
 * 	typedef struct _hash_map_t
 *	{
 *　　　 size_t×			size;
 *　　　 listnode_t*		key;
 *　　　 listnode_t*		value;
 *	}hash_map_t;
 * </pre>
 * 总的说来，Map，总是离不开key-value pairs（键值对）。
 * 
 * 一实现方法：
 * HashMap提供一个散列算法和一个链表数组（也叫哈希表），存储的时候，根据传入的键值的hashCode方法返回值
 * 调用HashMap重新定义的新的散列函数获取键的散列码，根据散列码
 * 调用indexFor方法，计算这个散列码在链表数组中的序列,然后根据该存入数组中对应的序列的位置。这样每次在获取
 * 元素的时候不需要迭代整个链表数组了，而可以直接通过键值的散列码从指定的序列获取一个链表。然后在迭代
 * 该链表，通过键值的比对获取到正确的元素返回。
 * 可能有的同学会有疑问了，如果散列码的序列相同怎么处理呢？不要忘记了链表数组了，该数组中的元素都是链表，
 * 如果键值的散列码相同，则会顺序存入该链表中。
 * 这就是JDK中HashMap的大致实现方法。
 * 
 * 二、性能参数：
 * 有两个参数将会影响HashMap的性能，初始容量和扩容因子（姑且让我这么称呼）。容量是指HashMap中链表数组的长度，
 * 扩容因子指定容器中实际能存储的最大元素数量的百分比，例如，容器长度为16，扩容因子为.75，那么HashMap的
 * 容器（链表数组）中实际能存储的最多元素个数为16×.75=12。超过该长度，容器将自动扩大成原来容器的2倍长度，当然
 * 老容器中的元素都会通过rehash方法逐个拷贝至新的容器中。
 * 
 * 默认的扩容因子的值为.75，一般作为通用的规则，没有特别的需要我们不需要传入这个扩容因子的参数。因为通
 * 过大量的实际应用，一般认为.75是时间和空间消耗的一个最优选择。
 * 数组的扩容是一个很消耗性能的操作，这两个参数直接决定了调用一个扩容操作的频度。
 * 如果存入HashMap中的键值对数目是可预估的，那么选择一个合适的容量和扩容因子就很重要了，这样能最大限度的减少
 * 扩容方法的调用，而且能在空间和时间上做出一个最优选择。
 * 
 * 三、线程安全以及fail-fast机制：
 * 请注意，HashMap不是线程安全的类，在多线程的环境下使用该类是不安全的。如果一定要在多线程的环境下使用，HashMap
 * 也提供<i>fail-fast</i>机制保证读取线程在读取的同时不会读到被其他线程修改过的键值对。
 * 其实现方式大致如下：
 * HashMap中提供了一个实例变量modCount，这是一个线程共享的变量，即任何线程都可以看到该变量被其它线程修改的结果。
 * 任何对hashmap中元素的CUD（增加，修改，删除）操作都会影响该值。
 * 同时HashMap中提供了一个迭代器HashIterator，HashMap的实例在迭代entrySet时，会使用这个迭代器，创建这个迭代器
 * 的时候会把modCount赋值给HashIterator的实例变量expectedModCount，每次调用HashIterator实例的nextEntry方法时
 * 都会检测modCount有没有被其他线程修改过。如果修改过则抛出错误。这只是一种悲观机制，这种机制不对CUD方法进行同步
 * 保留了HashMap的快速存储优势，但是发生了错误之后的通知调用方，由调用方进行决策。
 * 
 */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
		Cloneable, Serializable {
	private static final long	serialVersionUID			= 362498820763181265L;

	/**
	 * 上文中提到的链表数组。数组长度必须是2的n次幂。
	 */
	transient Entry[]			table;
	
	/**
	 * 默认的链表数组长度。
	 */
	static final int			DEFAULT_INITIAL_CAPACITY	= 16;

	/**
	 * 最大的链表数组长度，在32位的机器中最大的正整数为1<<31即2的31幂，注：第32位是符号位。
	 */
	static final int			MAXIMUM_CAPACITY			= 1 << 30;

	/**
	 * 默认的扩容因子，用来计算扩容阀值。
	 **/
	static final float			DEFAULT_LOAD_FACTOR			= 0.75f;

	/**
	 * 这个链表数组中包含的实际链表数量。
	 */
	transient int				size;

	/**
	 * 链表数组扩容阀值，如果链表数组存入的键值对越来越多，达到该值，则链表数组的长度会扩大成原来的2倍。
	 * 扩容之后会重新计算该值。
	 * @serial
	 */
	int							threshold;

	/**
	 * 扩容因子，链表长度×扩容因子=链表数组中允许存放的最多元素数目。
	 * 例如：链表长度为12，扩容因子为3/4（0.75），那么这个HashMap中允许存放的最大元素数目为12×.75=12
	 * 达到12个元素时，会新创建一个新的链表数组，长度为原来链表数组的2倍，将老链表数组中的元素逐个拷贝至
	 * 新数组中。
	 *
	 * @serial
	 */
	final float					loadFactor;

	/**
	 * 修改数，对HashMap的任何CUD修改都会影响该值，同时该变量对所有线程共享。
	 */
	transient volatile int		modCount;

	/**
	 * 使用指定链表数组长度(默认16)和指定扩容因子(默认.75)的构造函数，创建一个空HashMap。
	 * 同时会计算HashMap的扩容阀值。
	 * 其他的构造函数都在预处理了这两个参数之后调用本构造函数。
	 * 
	 * @param  initialCapacity 初始化容量.
	 * @param  loadFactor      扩容因子
	 */
	public HashMap(int initialCapacity, float loadFactor) {
		/*
		 *不小于初始容量的最小2次幂
		 *例如：初始容量是21，那么不小于21的最小2次幂为32，即2的5次幂
		 *这样能保证，log2（容量） 始终是个整数。
		 *
		 *为什么要做这样的操作有待考证。
		 */
		int capacity = 1;
		while (capacity < initialCapacity)
			capacity <<= 1;
		this.loadFactor = loadFactor;
		threshold = (int) (capacity * loadFactor);
		table = new Entry[capacity];
	}

	/**
	 * null键，如果put或者get方法的key参数为null，则默认使用这个键。
	 */
	static final Object	NULL_KEY	= new Object();

	/**
	 * Returns internal representation for key. Use NULL_KEY if key is null.
	 */
	static <T> T maskNull(T key) {
		return key == null ? (T) NULL_KEY : key;
	}

	/**
	 * Returns key represented by specified internal representation.
	 */
	static <T> T unmaskNull(T key) {
		return (key == NULL_KEY ? null : key);
	}

	/**
	 * Whether to prefer the old supplemental hash function, for
	 * compatibility with broken applications that rely on the
	 * internal hashing order.
	 *
	 * Set to true only by hotspot when invoked via
	 * -XX:+UseNewHashFunction or -XX:+AggressiveOpts
	 */
	private static final boolean	useNewHash;
	static {
		useNewHash = false;
	}

	/**
	 * 会根据key值的hashcode，从新计算一次hashcode，返回优化有的hashcode
	 * 这个方法所涉及的原理本人也不是很清楚，期待高手作答。
	 */
	static int hash(int h) {
		if (useNewHash) {
			h ^= (h >>> 20) ^ (h >>> 12);
			return h ^ (h >>> 7) ^ (h >>> 4);
		} else {
			h += ~(h << 9);
			h ^= (h >>> 14);
			h += (h << 4);
			h ^= (h >>> 10);
			return h;
		}
	}

	/**
	 * Returns index for hash code h. 
	 * 这是一个重要的函数，根绝hashcode计算其在链表数组中的序列
	 */
	static int indexFor(int h, int length) {
		return h & (length - 1);
	}


	/**
	 * 根据指定的键，返回其对应的值。
	 * 执行过程如下：
	 * 1.判断键是否为null，
	 * 	如果是，则从指定的null序列中取值，并返回。
	 * 2.根据键的hashcode方法的返回值，调用新的散列方法获取新的hashcode。
	 * 3.根据这个新的hashcode调用indexFor方法，计算这个hashcode在数组中的序列。
	 * 4.如果该序列没有链表，为null，直接返回null。如果有链表，继续执行
	 * 5.迭代该序列上的链表，
	 * 	5.1.判断实体的哈希值是否和键的hash值相等
	 * 	5.2.判断键的引用是否相同或者键的equals方法是否返回true
	 * 6.如果5.1，5.2的条件同时满足，则返回这个链表实体的值。
	 * 	如果遍历完链表条件均不满足则返回null。
	 * 
	 * 看这个方法之间请先看put方法。
	 * effective java中有一条原则，那就是如果要让自定义类型实例作为HashMap的键，
	 * 那么要重写equals方法和hashCode方法。
	 * 这个原则就在这里得到体现。
	 * 例如有自定义类型定义如下：
	 * 	<pre>
	 *     class Key{
	 *     		int a=0,b=0;
	 *     		Key(int a, int b){
	 *     			this.a = a;
	 *     			this.b = b;
	 *     		}
	 *     }
	 *     
	 *     Key k1 = new Key(1,2);
	 *     //调用HashMap的put方法
	 *     HashMap.put(k1,"我是k1(1,2)")
	 *     让后在k1对象的作用域之外，我们想取出这个键值对，调用HashMap的get方法。
	 *     HashMap.get(new Key(1,2));
	 *  </pre>
	 *  我们期待得到字符串"我是k1(1,2)"，但是很不幸，我们得到的是null，因为自定义类型中没有重写hashCode方法和equals方法
	 *  尽管对象中的所有变量都相等，我们也期待这两个对象是相同的。两个对象的hashCode肯定是不相同的，equals方法也不可能返
	 *  回true。HashMap中的条件也就不成立了。
	 */
	public V get(Object key) {
		if (key == null)
			return getForNullKey();
		int hash = hash(key.hashCode());
		int index = indexFor(hash, table.length);
		for (Entry<K, V> e = table[index]; e != null; e = e.next) {
			Object k;
			if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
				return e.value;
		}
		return null;
	}
	
	/**
	 * 传入的参数是键(key)和值(value)，把传入的键和值组成键值对，然后存入HashMap中，如果已经存在这个键，那么
	 * 这个键对应的值将会被替换。执行过程如下：
	 * 1.判断key是否为null，如果是null则存入指定的NULL链表。
	 * 2.重新计算键值的hashcode。
	 * 3.根据这个新的hashcode，与链表数组的长度进行“与”运算，计算这个hashcode在数组中的序列。
	 * 4.判断这个序列上是否已经存在链表，如果存在执行5，如果不存在执行6～9。
	 * 5.迭代这个链表，判断键是否已经存在该链表中，
	 * 	如果已经重复则替换原来的键值对，调用recordAccess方法，并返回原来的键值(value)。表示已经替换掉老的键值对。
	 * 	如果不存在重复键值对则执行6～9。
	 * 6.改变修改modCount变量，通知其他线程，这个HashMap已经被修改了。这时候如果其他线程正在迭代这个Hashap
	 * 	将会抛出ConcurrentModificationException异常。
	 * 7.给该链表新增一个实体对象，作为该链表的第一个元素，将这个元素的next引用指向为原来的第一个元素。
	 * 8.HashMap中的实体数加1。
	 * 9.返回null引用，表示已经新增成功。
	 * 
	 * 整个hashmap的put方法就是这8个过程，其中很复杂的是新的哈希算法的使用。这个hash算法优化了对象的hashcode()方法
	 * 的不足。
	 * 而且可以通过返回值判断键值对是添加成功了还是替换了原来已经存在的键值对。替换老的元素将会调用的recordAccess方法
	 * HashMap中并没有提供实现。
	 */
	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;
	}

	/**
	 * 因为HashMap是允许null键。调用put(K key, V value)方法的key如果是null则调用该方法。
	 * 这个方法和put方法基本过程一样，只是他是根据创建HashMap实例时的一个成员变量NULL_KEY的
	 * hashcode()方法返回值来计算新的hashcode，而不是key的hashcode()的返回值。
	 */
	private V putForNullKey(V value) {
		int hash = hash(NULL_KEY.hashCode());
		int i = indexFor(hash, table.length);

		for (Entry<K, V> e = table[i]; e != null; e = e.next) {
			if (e.key == NULL_KEY) {
				V oldValue = e.value;
				e.value = value;
				e.recordAccess(this);
				return oldValue;
			}
		}

		modCount++;
		addEntry(hash, (K) NULL_KEY, value, i);
		return null;
	}
	
	/**
	 * 传入newCapacity参数，将链表数组扩容至指定大小。如果当前的容量已经达到HashMap定义的最大容量
	 * 那么不再进行扩容，而是把扩容阀值赋值为最大的正整数，保证不再会有后续调用，即size永远不能大于
	 * 最大的正整数。
	 * 执行过程如下：
	 * 1.将当前的链表数组赋值给临时变量。
	 * 2.检查老的链表数组的长度，如果长度已经达到最大容量则不再进行扩容，直接返回。
	 * 3.根据传入的新参数，创建新的链表数组。
	 * 4.将当前的链表数组中的链表逐个拷贝至新的链表数组中进行扩容操作。
	 * 5.计算扩容阀值，计算下一次的扩容点。
	 * 6.返回。
	 * 
	 * 这个方法除了参数检查之外，还调用了另外一个迁移方法transfer。
	 */
	void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}

		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

	/** 
	 * 将当前链表数组中的所有链表，逐个拷贝至新的链表数组中。
	 * 如果是一个足够大的链表数组，可以看到这个方法的性能是很低的。
	 * 所以在创建HashMap实例的时候就要充分估计到HashMap的容量。
	 * 防止该方法的调用频度过高。
	 */
	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);
			}
		}
	}

	/**
	 * 一个该类型的对象表示一个键值对，这是一个单向链表。
	 * 在调用put方法的过程中，如果碰到相同的序列值，则会在该序列的链表中新增一个键值对。
	 * 注意这个链表重写了从Object对象哪里继承来的equals方法和hashcode方法
	 */
	static class Entry<K, V> implements Map.Entry<K, V> {
		final K		key;
		V			value;
		final int	hash;
		Entry<K, V>	next;

		/**
		 * 创建一个新的实体，所需要的参数为
		 * h：通过新的散列算法计算的的key的hashcode方法返回值，本质也是一个散列码
		 * k：键
		 * v：值
		 * n：因为这是一个单向链表，所以创建一个链表元素的时候需要指定下一个元素的引用。
		 * 	  这样才会成为一个实体串。
		 */
		Entry(int h, K k, V v, Entry<K, V> n) {
			hash = h;
			key = k;
			value = v;
			next = n;
		}

		public K getKey() {
			return HashMap.<K> 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();
		}

		/**
		 * 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) {
		}
	}

	/**
	 * 
	 * 为这个指定的键，创建一个新的实体（链表元素），作为这个链表的第一个实体，这个实体
	 * 的next引用指向原来位于这个序列的实体。HashMap中实际存在的实体数目自加1。
	 * 如果实际存在的实体数目超过扩容阀值，则HashMap扩容成原来的2倍，并重新计算扩容阀值。
	 * 
	 */
	void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
		if (size++ >= threshold)
			resize(2 * table.length);
	}

	/**
	 * HashMap内部迭代器，实现了Faid-Fast机制，请看nextEntry方法。
	 */
	private abstract class HashIterator<E> implements Iterator<E> {
		Entry<K, V>	next;				// next entry to return
		int			expectedModCount;	// For fast-fail 
		int			index;				// current slot 
		Entry<K, V>	current;			// current entry

		HashIterator() {
			expectedModCount = modCount;
			Entry[] t = table;
			int i = t.length;
			Entry<K, V> n = null;
			if (size != 0) { // advance to first entry
				while (i > 0 && (n = t[--i]) == null)
					;
			}
			next = n;
			index = i;
		}

		public boolean hasNext() {
			return next != null;
		}

		Entry<K, V> nextEntry() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();
			Entry<K, V> e = next;
			if (e == null)
				throw new NoSuchElementException();

			Entry<K, V> n = e.next;
			Entry[] t = table;
			int i = index;
			while (n == null && i > 0)
				n = t[--i];
			index = i;
			next = n;
			return current = e;
		}

		public void remove() {
			//...
		}

	}
}