HashMap深度解析(一)

       本文来自：高爽|Coder，原文地址：http://blog.csdn.net/ghsau/article/details/16843543，转载请注明。
       HashMap可以说是Java中最常用的集合类框架之一，是Java语言中非常典型的数据结构，我们总会在不经意间用到它，很大程度上方便了我们日常开发。在很多Java的笔试题中也会被问到，最常见的，“HashMap和HashTable有什么区别？”，这也不是三言两语能说清楚的，这种笔试题就是考察你来笔试之前有没有复习功课，随便来个快餐式的复习就能给出简单的答案。
       HashMap计划写两篇文章，一篇是HashMap工作原理，也就是本文，另一篇是多线程下的HashMap会引发的问题。这一年文章写的有点少，工作上很忙，自己业余时间也做点东西，就把博客的时间占用了，以前是力保一周一篇文章，有点给自己任务的意思，搞的自己很累，文章质量也不高，有时候写技术文章也是需要灵感的，为了举一个例子可能要绞尽脑汁，为了一段代码可能要验证好多次，现在想通了，有灵感再写，需要一定的积累，才能把自己了解的知识点总结归纳成文章。
       言归正传，了解HashMap之前，我们需要知道Object类的两个方法hashCode和equals，我们先来看一下这两个方法的默认实现：

/** JNI，调用底层其它语言实现 */public native int hashCode();

/** 默认同==，直接比较对象 */
public boolean equals(Object obj) {
	return (this == obj);
}

public boolean equals(Object anObject) {	if (this == anObject) {		return true;	}	if (anObject instanceof String) {		String anotherString = (String) anObject;		int n = value.length;		if (n == anotherString.value.length) {			char v1[] = value;			char v2[] = anotherString.value;			int i = 0;			// 逐个判断字符是否相等			while (n-- != 0) {				if (v1[i] != v2[i])						return false;				i++;			}			return true;		}	}	return false;}

• 自反性：对于任何非空引用值 x，x.equals(x) 都应返回 true。 
• 对称性：对于任何非空引用值 x 和 y，当且仅当 y.equals(x) 返回 true 时，x.equals(y) 才应返回 true。 
• 传递性：对于任何非空引用值 x、y 和 z，如果 x.equals(y) 返回 true，并且 y.equals(z) 返回 true，那么 x.equals(z) 应返回 true。 
• 一致性：对于任何非空引用值 x 和 y，多次调用 x.equals(y) 始终返回 true 或始终返回 false，前提是对象上 equals 比较中所用的信息没有被修改。 
• 对于任何非空引用值 x，x.equals(null) 都应返回 false。 

java.lang.Object  |--java.util.AbstractMap      |--java.util.HashMap

public V put(K key, V value) {	// 处理key为null，HashMap允许key和value为null	if (key == null)		return putForNullKey(value);	// 得到key的哈希码	int hash = hash(key);	// 通过哈希码计算出bucketIndex	int i = indexFor(hash, table.length);	// 取出bucketIndex位置上的元素，并循环单链表，判断key是否已存在	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;		}	}	// key不存在时，加入新元素	modCount++;	addEntry(hash, key, value, i);	return null;}