HashMap的實現(xiàn)

先介紹一些基本的原理。

1.hash函數(shù)

　　（1）hash函數(shù)是一個映像，hash的原意就是雜湊。hash函數(shù)的作用就是保證哈希函數(shù)值都落在表長允許的范圍之內即可。

　　（2）對不同的關鍵字，hash函數(shù)可能產(chǎn)生相同的哈希地址。

2.hash函數(shù)的構造方法們

哈希函數(shù)的構造方法，一是為了得到在表長內的哈希地址，另一個重要作用是保證得到的哈希地址能“均勻地”分布在表中，避免集中。

　　（1）　　直接定址法

　　　　就是根據(jù)給定的關鍵字，獲得一個線性值，作為哈希地址。

　　　　　　H(key) = a*key+b;　　(a,b為常數(shù)）

　　　　直接定址法不會產(chǎn)生哈希地址沖突，但是他的地址范圍取決于關鍵字集合，空間利用率低。

　　（2）　　數(shù)字分析法

　　　　適用于關鍵字是數(shù)值類型的，十進制，二進制，十六進制等。

　　　　分析關鍵字之間的異同點。比如：‘123555123’，’489555741‘，中間三位是相同的，那么就可以取前三位和末三位作為區(qū)別這兩個關鍵字的有效數(shù)字位置

　　　　將有效位置上的數(shù)字相加（舍去進位），對相應的進制數(shù)（2、10、16）取模，就可以得到進制內的對應的數(shù)字代表著兩個關鍵字。（也可以對有效數(shù)字位置上的數(shù)字進行其他方式的處理）

　　（3）　　平方取中法

　　　　同數(shù)字分析法，適用于關鍵字是數(shù)值類型的。

　　　　并不是經(jīng)常碰見有明顯異同的關鍵字，這個時候，每一個位置都是有效位置。

　　　　平方取中的思想是一個數(shù)的平方數(shù)中間幾位跟該數(shù)的每一位都有關系，取平方數(shù)的中間幾位（位數(shù)由表長決定）來作為哈希地址。

　　（4）　　折疊法

　　　　　適用于關鍵字是數(shù)值類型的，并且位數(shù)很多，并且每一位上的數(shù)字分布大致均勻。

　　　　　將關鍵字分割成長度相同的若干個部分，最后一個可以不同，然后相加（舍去進位），得到哈希地址。

　　（5）　　除留余數(shù)法

　　　　這是一種最簡單、最常用的方法。

　　　　取關鍵字被某個不大于哈希表長m的數(shù)p除后所得余數(shù)作為哈希地址。

　　　　H(key) = key MOD p, (p<=m);

　　(6)?　　隨機數(shù)法

　　　　比較好理解，就是用關鍵字作為隨機參數(shù)，獲取隨機數(shù)作為哈希地址。

　　　　表長不同，取隨機數(shù)的范圍不同。

除直接定址法之外，別的哈希函數(shù)構造方法都有可能使不同關鍵字獲得相同哈希地址，這個時候就需要進行沖突避免。處理沖突的方法有下面幾種：

　　（1）開放定址法

　　　　Hi = ( H(key)+Di?) MOD M;

　　　　其中D^_i為增量序列,M為哈希表長。

　　　　Di一般有三種取值：

　　　　　（1）　Di = 1,2,3,...M-1；（線性探測再散列）

　　　　　（2）　Di = 1^{2 ,?}-1², 2^{2 ,} -2²,3^{2 ,.......}k²（二次探測再散列）

　　　　　（3） ?Di = 偽隨機數(shù)序列　　（偽隨機數(shù)探測再散列）

　　（2）再哈希法

　　　　H_i = RH_i(key) ? i = 1,2,3....k

　　　　RHi 是一系列的哈希函數(shù)，當產(chǎn)生沖突時候，就順序選擇一個哈希函數(shù)進行計算哈希地址，如果仍然沖突，繼續(xù)選擇下一個哈希函數(shù)，只到?jīng)]有哈希沖突為止。

　　　　這種方法能有效避免“聚集”，但是增加了計算時間。

　　（3）鏈地址法

　　　　將所有關鍵字為同義詞（哈希地址相同）的記錄存儲在同一個鏈表中，表頭存儲在長度為M的數(shù)組中，表頭在數(shù)組中的位置，就是哈希地址。

　　　　也就是說如果一個關鍵字的哈希地址是k(k<m,m為表長），那么就存儲在表頭在k位置的鏈表中。

　（4）建立一個公共溢出區(qū)

　　　　如果發(fā)生沖突，也就是當前的哈希地址已經(jīng)被占用，則存放在公共溢出區(qū)中。此時，哈希函數(shù)操作兩個表，一個是常規(guī)的哈希表，另一個是公共溢出表。

?

下面介紹HashMap的數(shù)據(jù)存儲實現(xiàn)原理：

（1）選擇的哈希算法：

　　HashMap存儲數(shù)據(jù)時候，調用put(k,v)方法：

　　源代碼：

------------------------------------

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

-------------------------------------

　　其中hash(key)的源代碼如下：

　　源代碼：

-------------------------------------------------------------------------------　　　

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

-------------------------------------------------------------------------------

　　putVal()的源代碼：

-----------------

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length; ??-----------------------a-----------------------確定當前的哈希表容量是否不足，如果是就增大為原來的一倍
if ((p = tab[i = (n - 1) & hash]) == null)---------b------------------判斷獲得的哈希地址是否被占用。對hash值進行取模，（n-1)&hash得到的值肯定小于n,也就是resize后的哈希表長，可見，HashMap使用的哈希函數(shù)是除留余數(shù)法。
tab[i] = newNode(hash, key, value, null);--------------c------------------新建一個結點node，把新節(jié)點加入哈希地址中的鏈表中（如果哈希地址沒被占用，如果占用，則在下面的代碼進行處理）
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {　　
if ((e = p.next) == null) {　　--------------------------d-------------------------如果獲得鏈表的最后一個結點，把新結點接到后面，可見新的結點是在鏈尾。
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

---------------------------------------------

?

可見，HashMap采用的哈希函數(shù)是除留余數(shù)法，采用過的沖突避免算法是鏈地址法。

一步一步來，總會變好的。

總結

以上是生活随笔為你收集整理的浅谈HashMap的实现原理的全部內容，希望文章能夠幫你解決所遇到的問題。

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