了解HashMap原理對于日后的緩存機制多少有些認識。在網(wǎng)絡中也有很多方面的帖子，但是很多都是輕描淡寫，很少有把握的比較準確的信息，在這里試著不妨說解一二。

對于HashMap主要以鍵值(key-value)的方式來體現(xiàn)，籠統(tǒng)的說就是采用key值的哈希算法來，外加取余最終獲取索引，而這個索引可以認定是一種地址，既而把相應的value存儲在地址指向內(nèi)容中。這樣說或許比較概念化，也可能復述不夠清楚，來看列式更加清晰：

int?? hash=key.hashCode();//------------------------1

int?? index=hash%table.lenth;//table表示當前對象的長度-----------------------2

其實最終就是這兩個式子決定了值得存儲位置。但是以上兩個表達式還有欠缺。為什么這么說？例如在key.hashCode()后可能存在是一個負整數(shù)，你會問：是啊，那這個時候怎么辦呢？所以在這里就需要進一步加強改造式子2了，修改后的：

int?? index=(hash&Ox7FFFFFFF)%table.lenth;

到這里又迷惑了，為什么上面是這樣的呢？對于先前我們談到在hash有可能產(chǎn)生負數(shù)的情況，這里我們使用當前的hash做一個“與”操作，在這里需要和int最大的值相“與”。這樣的話就可以保證數(shù)據(jù)的統(tǒng)一性，把有符號的數(shù)值給“與”掉。而一般這里我們把二進制的數(shù)值轉(zhuǎn)換成16進制的就變成了：Ox7FFFFFFF。(注：與操作的方式為，不同為0，相同為1)。而對于hashCode()的方法一般有：

public int hashCode(){

int hash=0,offset,len=count;

char[]?var=value;

for(int i=0;i

h=31*hash+var[offset++];

}

return hash;

}

說道這里大家可能會說，到這里算完事了吧。但是你可曾想到如果數(shù)據(jù)都采用上面的方式，最終得到的可能index會相同怎么辦呢？如果你想到的話，那恭喜你!又增進一步了，這里就是要說到一個名詞：沖突率。是的就是前面說道的一旦index有相同怎么辦？數(shù)據(jù)又該如何存放呢，而且這個在數(shù)據(jù)量非常龐大的時候這個基率更大。這里按照算法需要明確的一點：每個鍵(key)被散列分布到任何一個數(shù)組索引的可能性相同，而且不取決于其它鍵分布的位置。這句話怎么理解呢？從概率論的角度，也就是說如果key的個數(shù)達到一個極限，每個key分布的機率都是均等的。更進一步就是：即便key1不等于key2也還是可能key1.hashCode()=key2.hashCode()。

對于早期的解決沖突的方法有折疊法(folding)，例如我們在做系統(tǒng)的時候有時候會采用部門編號附加到某個單據(jù)標號后，這里比如產(chǎn)生一個9～11位的編碼。通過對半折疊做。

現(xiàn)在的策略有：

1.鍵式散列

2.開放地址法

在了解這兩個策略前，我們先定義清楚幾個名詞解釋：

threshold[閥值]，對象大小的邊界值;

loadFactor[加載因子]=n/m；其中n代表對象元素個數(shù)，m表示當前表的容積最大值

threshold=(int)table.length*loadFactor

清晰了這幾個定義，我們再來看具體的解決方式

鍵式散列：

我們直接看一個實例，這樣就更加清晰它的工作方式，從而避免文字定義。我們這里還是來舉一個圖書編號的例子，下面比如有這樣一些編號：

78938-0000

45678-0001

72678-0002

24678-0001

16678-0001

98678-0003

85678-0002

45232-0004

步驟：

1.把編號作為key,即：int hash=key.hashCode();

2.int index=hash%表大小；

3.逐步按順序插入對象中

現(xiàn)在問題出現(xiàn)了：對于編號通過散列算法后很可能產(chǎn)生相同的索引值，意味著存在沖突。

解釋上面的操作：如果對于key.hashCode()產(chǎn)生了沖突(比如途中對于插入24678-0001對于通過哈希算法后可能產(chǎn)生的index或許也是501)，既而把相應的前驅(qū)有相同的index的對象指向當前引用。這也就是大家認定的單鏈表方式。以此類推…

而這里存在沖突對象的元素放在Entry對象中，Entry具有以下一些屬性：

int hash;

Object key;

Entry next;

對于Entry對象就可以直接追溯到鏈表數(shù)據(jù)結(jié)構體中查閱。

開放地址法：

1.線性地址探測法：

如何理解這個概念呢，一句話：就是通過算法規(guī)則在對象地址N+1中查閱找到為NULL的索引內(nèi)容。

處理方式：如果index索引與當前的index有沖突，即把當前的索引index+1。如果在index+1已經(jīng)存在占位現(xiàn)象(index+1的內(nèi)容不為NULL)試圖接著index+2執(zhí)行。。。直到找到索引為內(nèi)容為NULL的為止。這種處理方式也叫：線性地址探測法(offset-of-1)

如果采用線性地址探測法會帶來一個效率的不良影響。現(xiàn)在我們來分析這種方式會帶來哪些不良因素。大家試想下如果一個非常龐大的數(shù)據(jù)存儲在Map中，假如在某些記錄集中有一些數(shù)據(jù)非常相似(他們產(chǎn)生的索引在內(nèi)存的某個塊中非常的密集)，也就是說他們產(chǎn)生的索引地址是一個連續(xù)數(shù)值，而造成數(shù)據(jù)成塊現(xiàn)象。另一個致命的問題就是在數(shù)據(jù)刪除后，如果再次查詢可能無法定到下一個連續(xù)數(shù)字，這個又是一個什么概念呢？例如以下圖片就很好的說明開發(fā)地址散列如何把數(shù)據(jù)按照算法插入到對象中：

對于上圖的注釋步驟說明：

從數(shù)據(jù)“78938-0000”開始通過哈希算法按順序依次插入到對象中，例如78938-0000通過換

算得到索引為0，當前所指內(nèi)容為NULL所以直接插入；45678-0001同樣通過換算得到索引為地址501所指內(nèi)容，當前內(nèi)容為NULL所以也可以插入；72678-0002得到索引502所指內(nèi)容，當前內(nèi)容為NULL也可以插入；請注意當24678-0001得到索引也為501，當前地址所指內(nèi)容為45678-0001。即表示當前數(shù)據(jù)存在沖突，則直接對地址501+1=502所指向內(nèi)容為72678-0002不為NULL也不允許插入，再次對索引502+1=503所指內(nèi)容為NULL允許插入。。。依次類推只要對于索引存在沖突現(xiàn)象，則逐次下移位知道索引地址所指為NULL；如果索引不沖突則還是按照算法放入內(nèi)容。對于這樣的對象是一種插入方式，接下來就是我們的刪除(remove)方法了。按照常理對于刪除，方式基本區(qū)別不大。但是現(xiàn)在問題又出現(xiàn)了，如果刪除的某個數(shù)據(jù)是一個存在沖突索引的內(nèi)容，帶來后續(xù)的問題又會接踵而來。那是什么問題呢？我們還是同樣來看看圖示的描述，對于圖-2中如果刪除(remove)數(shù)據(jù)24678-0001的方法如下圖所示：

對于我們會想當然的覺得只要把指向數(shù)據(jù)置為NULL就可以,這樣的做法對于刪除來說當然是沒有問題的。如果再次定位檢索數(shù)據(jù)16678-0001不會成功，因為這個時候以前的鏈路已經(jīng)堵上了，但是需要檢索的數(shù)據(jù)事實上又存在。那我們?nèi)绾蝸斫鉀Q這個問題呢？對于JDK中的Entry類中的方法存在一個：boolean markedForRemoval;它就是一個典型的刪除標志位，對于對象中如果需要刪除時，我們只是對于它做一個“軟刪除”即置一個標志位為true就可以。而插入時，默認狀態(tài)為false就可以。這樣的話就變成以下圖所示：

通過以上方式更好的解決沖突地址刪除數(shù)據(jù)無法檢索其他鏈路數(shù)據(jù)問題了。

2.雙散列(余商法)

在了解開放地址散列的時候我們一直在說解決方法，但是大家都知道一個數(shù)據(jù)結(jié)構的完善更多的是需要高效的算法。這當中我們卻沒有涉及到。接下來我們就來看看在開放地址散列中它存在的一些不足以及如何改善這樣的方法，既而達到無論是在方法的解決上還是在算法的復雜度上更加達到高效的方案。

在圖2-1中類似這樣一些數(shù)據(jù)插入進對象，存在沖突采用不斷移位加一的方式，直到找到不為NULL內(nèi)容的索引地址。也正是由于這樣一種可能加大了時間上的變慢。大家是否注意到像圖這樣一些數(shù)據(jù)目前呈現(xiàn)出一種連續(xù)索引的插入，而且是一種成塊是的數(shù)據(jù)。如果數(shù)據(jù)量非常的龐大，或許這種可能性更大。盡管它解決了沖突，但是對于數(shù)據(jù)檢索的時間度來說，我們是不敢想象的。所有分布到同一個索引index上的key保持相同的路徑：index,index+1,index+2…依此類推。更加糟糕的是索引鍵值的檢索需要從索引開始查找。正是這樣的原因，對于線性探索法我們需要更進一步的改進。而剛才所描述這種成塊出現(xiàn)的數(shù)據(jù)也就定義成：簇。而這樣一種現(xiàn)象稱之為：主簇現(xiàn)象。

(主簇：就是沖突處理允許簇加速增長時出現(xiàn)的現(xiàn)象)而開放式地址沖突也是允許主簇現(xiàn)象產(chǎn)生的。那我們?nèi)绾蝸肀苊膺@種主簇現(xiàn)象呢？這個方式就是我們要來說明的：雙散列解決沖突法了。主要的方式為：

uint hash=key.hasCode();

uint index=(hash&Ox7FFFFFFF)%table.length;

u按照以上方式得到索引存在沖突，則開始對當前索引移位，而移位方式為：

ffset=(hash&Ox7FFFFFFF)/table.length;

u如果第一次移位還存在同樣的沖突，則繼續(xù)：當前沖突索引位置(索引號+余數(shù))%表.length

u如果存在的余數(shù)恰好是表的倍數(shù)，則作偏移位置為一下移，依此類推

這樣雙散列沖突處理就避免了主簇現(xiàn)象。至于HashSet的原理基本和它是一致的，這里不再復述。在這里其實還是主要說了一些簡單的解決方式，而且都是在一些具體參數(shù)滿足條件下的說明，像一旦數(shù)據(jù)超過初始值該需要rehash，加載因子一旦大于1.0是何種情況等等。還有很多問題都可以值得我們更加進一步討論的，比如：在java.util.HashMap中的加載因子為什么會是0.75，而它默認的初始大小為什么又是16等等這些問題都還值得說明。要說明這些問題可能又需要更加詳盡的說明清楚。

源碼分析:HashMap

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

有關AbstractMap：http://blog.csdn.net/treeroot/archive/2004/09/20/110343.aspx

有關Map：http://blog.csdn.net/treeroot/archive/2004/09/20/110331.aspx

有關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ù)組中的位置，只是簡單的與關系。

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。

Entry getEntry(Object key) {

Object k = maskNull(key);

int hash = hash(k);

int i = indexFor(hash, table.length);

Entry e = table[i];

while (e != null && !(e.hash == hash && eq(k, e.key)))

e = e.next;

return e;

}

這個方法根據(jù)key值返回Entry節(jié)點，也是先獲得索引位置，再遍歷鏈表，如果沒有找到返回的是null。

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)

posted on 2009-05-14 13:32 郭鵬 閱讀(791) 評論(0) ?編輯 ?收藏 所屬分類: JAVA

總結(jié)

以上是生活随笔為你收集整理的hashmap hash冲突怎么解决_HashMap原理及冲突之简谈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。