JAVA HASHMAP的原理分析

核心提示：还是来整体看一下HashMap的结构吧. 如下图所示(图没画好),方框代表Hash桶,椭图代表桶内的元素,在这里就是Key-value对所组成Map.Entry对像.如果有多个元索被Hash函数定位到同一个桶内,我们称之为hash冲突,桶内的元素组成单向链表.让我们看一下hashMap JDK源码(因篇幅关系,删除了部

还是来整体看一下HashMap的结构吧. 如下图所示(图没画好),方框代表Hash桶,椭图代表桶内的元素,在这里就是Key-value对所组成Map.Entry对像.

　　　

如果有多个元索被Hash函数定位到同一个桶内,我们称之为hash冲突,桶内的元素组成单向链表.让我们看一下hashMap JDK源码(因篇幅关系,删除了部分代码与注释,感兴可以查看JDK1.6源码):

public　class　HashMap<K,V>
　　　　extends　AbstractMap<K,V>
　　　　implements　Map<K,V>,　Cloneable,　Serializable
{
　　　　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;
　　　　transient　int　size;
　　　　int　threshold;
　　　　final　float　loadFactor;
　　　　transient　volatile　int　modCount;
　　　　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);
　　　　　　　　//　Find　a　power　of　2　>=　initialCapacity
　　　　　　　　int　capacity　=　1;
　　　　　　　　while　(capacity　<　initialCapacity)
　　　　　　　　　　　　capacity　<<=　1;
　　　　　　　　this.loadFactor　=　loadFactor;
　　　　　　　　threshold　=　(int)(capacity　*　loadFactor);
　　　　　　　　table　=　new　Entry[capacity];
　　　　　　　　init();
　　　　}
　　　
　　　　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;
　　　　}
　　　　private　V　getForNullKey()　{
　　　　　　　　for　(Entry<K,V>　e　=　table[0];　e　!=　null;　e　=　e.next)　{
　　　　　　　　　　　　if　(e.key　==　null)
　　　　　　　　　　　　　　　　return　e.value;
　　　　　　　　}
　　　　　　　　return　null;
　　　　}
　　　　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;
　　　　}
　　　　private　V　putForNullKey(V　value)　{
　　　　　　　　for　(Entry<K,V>　e　=　table[0];　e　!=　null;　e　=　e.next)　{
　　　　　　　　　　　　if　(e.key　==　null)　{
　　　　　　　　　　　　　　　　V　oldValue　=　e.value;
　　　　　　　　　　　　　　　　e.value　=　value;
　　　　　　　　　　　　　　　　e.recordAccess(this);
　　　　　　　　　　　　　　　　return　oldValue;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　　　　　modCount++;
　　　　　　　　addEntry(0,　null,　value,　0);
　　　　　　　　return　null;
　　　　}
}