HashMap是Java新Collection Framework中用來代替HashTable的一個實現(xiàn)，HashMap和HashTable的區(qū)別是： HashMap是未經(jīng)同步的，而且允許null值。HashTable繼承Dictionary，而且使用了Enumeration，所以被建議不要使用。
HashMap的聲明如下：
public class HashMap extends AbstractMap implements Map, Cloneable,Serializable
有關(guān)AbstractMap：http://blog.csdn.net/treeroot/archive/2004/09/20/110343.aspx
有關(guān)Map：http://blog.csdn.net/treeroot/archive/2004/09/20/110331.aspx
有關(guān)Cloneable：http://blog.csdn.net/treeroot/archive/2004/09/07/96936.aspx
這個類比較復雜，這里只是重點分析了幾個方法，特別是后面涉及到很多內(nèi)部類都沒有解釋
不過都比較簡單。

static final int DEFAULT_INITIAL_CAPACITY = 16; 默認初始化大小

static final int MAXIMUM_CAPACITY = 1 << 30; 最大初始化大小

static final float DEFAULT_LOAD_FACTOR = 0.75f; 默認加載因子

transient Entry[] table; 一個Entry類型的數(shù)組，數(shù)組的長度為2的指數(shù)。

transient int size; 映射的個數(shù)

int threshold; 下一次擴容時的值

final float loadFactor; 加載因子

transient volatile int modCount; 修改次數(shù)

public HashMap(int initialCapacity, float loadFactor) {
　　 if (initialCapacity < 0)
　　　　 throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
　　 if (initialCapacity > MAXIMUM_CAPACITY)
　　　　 initialCapacity = MAXIMUM_CAPACITY;
　　 if (loadFactor <= 0 || Float.isNaN(loadFactor))
　　　　 throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
　　 int capacity = 1;
　　 while (capacity < initialCapacity)
　　　　 capacity <<= 1;
　　 this.loadFactor = loadFactor;
　　 threshold = (int)(capacity * loadFactor);
　　 table = new Entry[capacity];
　　 init();
}

public HashMap(int initialCapacity) {
　　 this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
　　 this.loadFactor = DEFAULT_LOAD_FACTOR;
　　 threshold = (int)(DEFAULT_INITIAL_CAPACITY);
　　　　　　注意：這里應該是一個失誤！ 應該是：threshold =(int)(DEFAULT_INITIAL_CAPACITY * loadFactor);
　　 table = new Entry[DEFAULT_INITIAL_CAPACITY];
　　　init();
}

public HashMap(Map m) {
　　 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　DEFAULT_LOAD_FACTOR);
　　 putAllForCreate(m);
}

void init() {}

static final Object NULL_KEY = new Object();

static Object maskNull(Object key){
　　 return (key == null ? NULL_KEY : key);
}

static Object unmaskNull(Object key) {
　　 return (key == NULL_KEY ? null : key);
}

static int hash(Object x) {
　　 int h = x.hashCode();
　　 h += ~(h << 9);
　　 h ^= (h >>> 14);
　　 h += (h << 4);
　　 h ^= (h >>> 10);
return h;
}
在HashTable中沒有這個方法，也就是說HashTable中是直接用對象的hashCode值，但是HashMap做了改進 用這個算法來獲得哈希值。

static boolean eq(Object x, Object y) {
　 　return x == y || x.equals(y);
}

static int indexFor(int h, int length) {
　　 return h & (length-1);
}
根據(jù)哈希值和數(shù)組的長度來返回該hash值在數(shù)組中的位置，只是簡單的與關(guān)系。

public int size() {
　　 return size;
}

public boolean isEmpty() {
　　return size == 0;
}

public Object get(Object key) {
　　 Object k = maskNull(key);
　　 int hash = hash(k);
　　 int i = indexFor(hash, table.length);
　　 Entry e = table[i];
　　 while (true) {
　　　　 if (e == null) return e;
　　　　 if (e.hash == hash && eq(k, e.key)) return e.value;
　　　　 e = e.next;
　　 }
}
這個方法是獲取數(shù)據(jù)的方法，首先獲得哈希值，這里把null值掩飾了，并且hash值經(jīng)過函數(shù)hash()修正。 然后計算該哈希值在數(shù)組中的索引值。如果該索引處的引用為null，表示HashMap中不存在這個映射。 否則的話遍歷整個鏈表，這里找到了就返回,如果沒有找到就遍歷到鏈表末尾，返回null。這里的比較是這樣的：e.hash==hash && eq(k,e.key) 也就是說如果hash不同就肯定認為不相等，eq就被短路了，只有在 hash相同的情況下才調(diào)用equals方法。現(xiàn)在我們該明白Object中說的如果兩個對象equals返回true，他們的 hashCode應該相同的道理了吧。假如兩個對象調(diào)用equals返回true，但是hashCode不一樣，那么在HashMap 里就認為他們不相等。

public boolean containsKey(Object key) {
　　 Object k = maskNull(key);
　　 int hash = hash(k);
　　 int i = indexFor(hash, table.length);
　　 Entry e = table[i];
　　 while (e != null) {
　　　　 if (e.hash == hash && eq(k, e.key)) return true;
　　　　 e = e.next;
　　 }
　　return false;
}
這個方法比上面的簡單，先找到哈希位置，再遍歷整個鏈表，如果找到就返回true。

public Object put(Object key, Object value) {
　　 Object k = maskNull(key);
　　 int hash = hash(k);
　　 int i = indexFor(hash, table.length);
　　 for (Entry e = table[i]; e != null; e = e.next) {
　　　　 if (e.hash == hash && eq(k, e.key)) {
　　　　　　 Object oldValue = e.value;
　　　　　　 e.value = value;
　　　　　　 e.recordAccess(this);
　　　　　　 return oldValue;
　　　　 }
　　 }
　　 modCount++;
　　 addEntry(hash, k, value, i);
　　 return null;
}
首先獲得hash索引位置，如果該位置的引用為null，那么直接插入一個映射，返回null。如果此處的引用不是null，必須遍歷鏈表，如果找到一個相同的key，那么就更新該value，同時返回原來的value值。如果遍歷完了沒有找到，說明該key值不存在，還是插入一個映射。如果hash值足夠離散的話，也就是說該索引沒有被使用的話，那么不不用遍歷鏈表了。相反，如果hash值不離散，極端的說如果是常數(shù)的話，所有的映射都會在這一個鏈表上，效率會極其低下。這里舉一個最簡單的例子，寫兩
個不同的類作為key插入到HashMap中，效率會遠遠不同。
class Good{
　　int i;
　　public Good(int i){
　　　this.i=i;
　　}
　　public boolean equals(Object o){
　　　return (o instanceof Good) && (this.i==((Good)o).i)
　　}
　　public int hashCode(){
　　　return i;
　　}
}
class Bad{
　　int i;
　　public Good(int i){
　　　　this.i=i;
　　}
　　public boolean equals(Object o){
　　　　return (o instanceof Good) && (this.i==((Good)o).i)
　　}
　　public int hashCode(){
　　　return 0;
　　}
}
執(zhí)行代碼：
Map m1=new HashMap();
Map m2=new HashMap();
for(int i=0;i<100;i++){
　　m1.put(new Good(i),new Integer(i)); //這里效率非常高
}
for(int i=0;i<100;i++){
　　m2.put(new Bad(i),new Integer(i)); //這里幾乎要崩潰
}
上面的是兩個非常極端的例子，執(zhí)行一下就知道差別有多大。

private void putForCreate(Object key, Object value) {
　　 Object k = maskNull(key);
　　 int hash = hash(k);
　　 int i = indexFor(hash, table.length);
　　 for (Entry e = table[i]; e != null; e = e.next) {
　　　　 if (e.hash == hash && eq(k, e.key)) {
　　　　　　　 e.value = value;
　　　　　　　 return;
　　　　 }
　　 }
　　 createEntry(hash, k, value, i);
}

void putAllForCreate(Map m) {
　　 for (Iterator i = m.entrySet().iterator(); i.hasNext(); ) {
　　　　 Map.Entry e = (Map.Entry) i.next();
　　　　 putForCreate(e.getKey(), e.getValue());
　　 }
}
上面的兩個方法是被構(gòu)造函數(shù)和clone方法調(diào)用的。

void resize(int newCapacity) {
　　 Entry[] oldTable = table;
　　 int oldCapacity = oldTable.length;
　　 if (size < threshold || oldCapacity > newCapacity)
　　　　 return;
　　 Entry[] newTable = new Entry[newCapacity];
　　 transfer(newTable);
　　 table = newTable;
　　 threshold = (int)(newCapacity * loadFactor);
}
這個方法在需要的時候重新分配空間，相當于ArrayList的ensureCapacity方法，不過這個更加復雜。

void transfer(Entry[] newTable) {
　　 Entry[] src = table;
　　 int newCapacity = newTable.length;
　　 for (int j = 0; j < src.length; j++) {
　　　　 Entry e = src[j];
　　　　 if (e != null) {
　　　　　　 src[j] = null;
　　　　　　 do {
　　　　　　　　　 Entry next = e.next;
　　　　　　　　　 int i = indexFor(e.hash, newCapacity);
　　　　　　　　　 e.next = newTable[i];
　　　　　　　　　 newTable[i] = e;
　　　　　　　　　 e = next;
　　　　　　 } while (e != null);
　　　　 }
　　 }
}
遍歷原來的數(shù)組，如果該Entry不是null的話，說明有映射，然后遍歷這個鏈表，把所有的映射插入到新的數(shù)組中，注意這里要從新計算索引位置。

public void putAll(Map t) {
　　 int n = t.size();
　　 if (n == 0)
　　　　 return;
　　 if (n >= threshold) {
　　　　 n = (int)(n / loadFactor + 1);
　　　　 if (n > MAXIMUM_CAPACITY)
　　　　　　 n = MAXIMUM_CAPACITY;
　　　　 int capacity = table.length;
　　　　 while (capacity < n) capacity <<= 1;
　　　　　　 resize(capacity);
　　 }
　　 for (Iterator i = t.entrySet().iterator(); i.hasNext(); ) {
　　　　 Map.Entry e = (Map.Entry) i.next();
　　　　 put(e.getKey(), e.getValue());
　　 }
}
這個方法先確定是否需要擴大空間，然后循環(huán)調(diào)用put方法。

public Object remove(Object key) {
　　 Entry e = removeEntryForKey(key);
　　 return (e == null ? e : e.value);
}

Entry removeEntryForKey(Object key) {
　　 Object k = maskNull(key);
　　 int hash = hash(k);
　　 int i = indexFor(hash, table.length);
　　 Entry prev = table[i];
　　 Entry e = prev;
　　 while (e != null) { 　如果e==null表示不存在
　　　　 Entry next = e.next;
　　　　 if (e.hash == hash && eq(k, e.key)) {
　　　　　　 modCount++;
　　　　　　 size--;
　　　　　　 if (prev == e)
　　　 　　　　　table[i] = next; 鏈表的第一個元素就是要刪除的，這里最好加一句 e.next=null.
　　　　　　 else
　　　　　　　　 prev.next = next; 存在擔不是鏈表的第一個元素， 這里最好加一句 e.next=null.
　　　　　　 e.recordRemoval(this);
　　　　　　 return e;
　　　　 }
　　　　 prev = e;
　　　　 e = next;
　　 }
　　return e;　　　這里其實就是return null;
}
這個方法其實也不復雜，也是遍歷鏈表，這里建議加一句e.next=null,可以改為
if(prev==e)
　　table[i]=next;
else
　　prev.next=next;
e.next=null; 這一句是多加的，可以提高效率。
這里簡單說明我的看法：
因為e是被刪除的節(jié)點，刪除它其實就是指向它的指針指向它的后面一個節(jié)點。所以e可以作為GC回收的對象。
可以e還有一個next指針指向我們的數(shù)據(jù)，如果e沒有被回收。而且此時e.next指向的節(jié)點也變?yōu)闆]用的了，但是
卻有一個它的引用(e.next),所以雖然e的下一個節(jié)點沒用了，但是卻不能作為GC回收的對象，除非e先被回收。
雖然不一定會引起很大的問題，但是至少會影響GC的回收效率。就像數(shù)據(jù)庫中的外鍵引用一樣，刪除起來很麻煩呀。

Entry removeMapping(Object o) {
　　 if (!(o instanceof Map.Entry))
　　　　 return null;
　　 Map.Entry entry = (Map.Entry)o;
　　 Object k = maskNull(entry.getKey());
　　 int hash = hash(k);
　　 int i = indexFor(hash, table.length);
　　 Entry prev = table[i];
　　 Entry e = prev;
　　 while (e != null) {
　　　　 Entry next = e.next;
　 　　　if (e.hash == hash && e.equals(entry)) {
　　　　　　 modCount++;
　　　　　　 size--;
　　　 　　　if (prev == e)
　　　　　　　　 table[i] = next;
　　　　　　 else
　　　　　　　　 prev.next = next;
　　　　　　 e.recordRemoval(this);
　　　　　　 return e;
　　　　　 }
　　　　　 prev = e;
　　　　　 e = next;
　　 }
　　 return e;
}
這個方法和上面的一樣。

public void clear() {
　　 modCount++;
　　 Entry tab[] = table;
　　 for (int i = 0; i < tab.length; i++)
　　　　 tab[i] = null;
　　 size = 0;
}
同樣可以改進

public boolean containsValue(Object value) {
　　 if (value == null)
　　　　 return containsNullValue();
　　 Entry tab[] = table;
　　 for (int i = 0; i < tab.length ; i++)
　　　　 for (Entry e = tab[i] ; e != null ; e = e.next)
　　　　　　 if (value.equals(e.value)) return true;
　　 return false;
}

private boolean containsNullValue() {
　　 Entry tab[] = table;
　　 for (int i = 0; i < tab.length ; i++)
　　　　 for (Entry e = tab[i] ; e != null ; e = e.next)
　　　　　　 if (e.value == null) return true;
　　 return false;
}

public Object clone() {
　　 HashMap result = null;
　　 try {
　　　　 result = (HashMap)super.clone();
　　 }
　　 catch (CloneNotSupportedException e) { // assert false; }
　　 result.table = new Entry[table.length];
　　 result.entrySet = null;
　　 result.modCount = 0;
　　 result.size = 0;
　　 result.init();
　　 result.putAllForCreate(this);
　　 return result;
}

static class Entry implements Map.Entry {
　　 final Object key;
　　 Object value;
　　 final int hash;
　　 Entry next;
　　 Entry(int h, Object k, Object v, Entry n) {
　　　　 value = v;
　　　　 next = n;
　　　　 key = k;
　　　　 hash = h;
　　 }
　　 public Object getKey() {
　　　　 return unmaskNull(key);
　　 }
　　　public Object getValue() {
　　　　 return value;
　　 }
　　　public Object setValue(Object newValue) {
　　　　　 Object 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();
　　　 }
　　　 void recordAccess(HashMap m) { }
　　　 void recordRemoval(HashMap m) { }
}
一個靜態(tài)內(nèi)部類

void addEntry(int hash, Object key, Object value, int bucketIndex) {
　　　 table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);
　　　 if (size++ >= threshold)
　　　　　 resize(2 * table.length);
}
注意這個方法，插入連表的頭。
可以寫成這樣更好理解：
Entry oldHead=table[bucketIndex];
Entry newHead = new Entry(hash,key,value,oldHead);
table[bucketIndex]=newHead;

void createEntry(int hash, Object key, Object value, int bucketIndex) {
　　 table[bucketIndex] = new Entry(hash, key, value, table[bucketIndex]);
　　 size++;
}

private abstract class HashIterator implements Iterator {
　　 Entry next;
　　 int expectedModCount;
　　 int index;
　　 Entry current;
　　 HashIterator() {
　　　　 expectedModCount = modCount;
　　　　 Entry[] t = table;
　　　　 int i = t.length;
　　　　 Entry n = null;
　　　　 if (size != 0) {
　　　　　　 while (i > 0 && (n = t[--i]) == null) ;
　　　　 }
　　　　 next = n;
　　　　 index = i;
　　 }
　　 public boolean hasNext() {
　　　　 return next != null;
　　 }
　　 Entry nextEntry() {
　　　　 if (modCount != expectedModCount)
　　　　　　 throw new ConcurrentModificationException();
　　　　 Entry e = next;
　　　　if (e == null)
　　　　　　 throw new NoSuchElementException();
　　　　 Entry 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() {
　　　　 if (current == null)
　　　　　　 throw new IllegalStateException();
　　　　 if (modCount != expectedModCount)
　　　　　　 throw new ConcurrentModificationException();
　　　　 Object k = current.key;
　　　　 current = null;
　　　　 HashMap.this.removeEntryForKey(k);
　　　　 expectedModCount = modCount;
　　 }
}

private class ValueIterator extends HashIterator {
　　 public Object next() {
　　　　 return nextEntry().value;
　　 }
}

private class KeyIterator extends HashIterator {
　　 public Object next() {
　　　　 return nextEntry().getKey();
　　 }
}

private class EntryIterator extends HashIterator {
　　 public Object next() {
　　　　 return nextEntry();
　　 }
}

Iterator newKeyIterator() {
　　 return new KeyIterator();
}

Iterator newValueIterator() {
　　 return new ValueIterator();
}

Iterator newEntryIterator() { 　
　 　return new EntryIterator();
}

private transient Set entrySet = null;

public Set keySet() {
　　 Set ks = keySet;
　　 return (ks != null ? ks : (keySet = new KeySet()));
}

private class KeySet extends AbstractSet {
　　 public Iterator iterator() {
　　　　 return newKeyIterator();
　　 }
　　 public int size() {
　　　　 return size;
　　 }
　　 public boolean contains(Object o) {
　　　　 return containsKey(o);
　　 }
　　 public boolean remove(Object o) {
　　　　 return HashMap.this.removeEntryForKey(o) != null;
　　 }
　　 public void clear() {
　　　　 HashMap.this.clear();
　　 }
}

public Collection values() {
　　 Collection vs = values; return (vs != null ? vs : (values = new Values()));
}

private class Values extends AbstractCollection {
　　 public Iterator iterator() {
　　　　 return newValueIterator();
　　 }
　　 public int size() {
　　　　 return size;
　　 }
　　 public boolean contains(Object o) {
　　　　 return containsValue(o);
　　 }
　　 public void clear() {
　　　　 HashMap.this.clear();
　　 }
}

public Set entrySet() {
　　 Set es = entrySet;
　　 return (es != null ? es : (entrySet = new EntrySet()));
}

private class EntrySet extends AbstractSet {
　　 public Iterator iterator() {
　　　　 return newEntryIterator();
　　 }
　　 public boolean contains(Object o) {
　　　　 if (!(o instanceof Map.Entry))
　　　　　　 return false;
　　　　 Map.Entry e = (Map.Entry)o;
　　　　 Entry candidate = getEntry(e.getKey());
　　　　 return candidate != null && candidate.equals(e);
　　 }
　　 public boolean remove(Object o) {
　　　　 return removeMapping(o) != null;
　　 }
　　 public int size() {
　　　　 return size;
　　 }
　　 public void clear() {
　　　　 HashMap.this.clear();
　　 }
}

private void writeObject(java.io.ObjectOutputStream s) throws IOException {
　　 s.defaultWriteObject();
　　 s.writeInt(table.length);
　　 s.writeInt(size);
　　 for (Iterator i = entrySet().iterator(); i.hasNext(); ) {
　　　　 Map.Entry e = (Map.Entry) i.next();
　　　　 s.writeObject(e.getKey());
　　　　 s.writeObject(e.getValue());
　　 }
}

private static final long serialVersionUID = 362498820763181265L;

private void readObject(java.io.ObjectInputStream s) throws IOException, ClassNotFoundException {
　　 s.defaultReadObject();
　　 int numBuckets = s.readInt();
　　 table = new Entry[numBuckets];
　　 init();
　　 size = s.readInt(); for (int i=0;
　　 for (int i=0; i<size; i++) {
　　　　　Object key = s.readObject();
　　　　　Object value = s.readObject();　
　　　　　putForCreate(key, value);
　　　}
}

int capacity() {
　 return table.length;
}
float loadFactor() {
　　 return loadFactor;
}