建站
咨詢
售后
建站咨詢
新聞中心
本篇對(duì)HashMap實(shí)現(xiàn)的源碼進(jìn)行簡(jiǎn)單的分析。 所使用的HashMap源碼的版本信息如下：
金水網(wǎng)站建設(shè)公司創(chuàng)新互聯(lián)建站,金水網(wǎng)站設(shè)計(jì)制作，有大型網(wǎng)站制作公司豐富經(jīng)驗(yàn)。已為金水成百上千提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)營(yíng)銷網(wǎng)站建設(shè)要多少錢，請(qǐng)找那個(gè)售后服務(wù)好的金水做網(wǎng)站的公司定做！
/* * @(#)HashMap.java 1.73 07/03/13 * * Copyright 2006 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */
一.概述
在Java中每一個(gè)對(duì)象都有一個(gè)哈希碼，這個(gè)值可以通過hashCode()方法獲得。hashCode()的值和對(duì)象的equals方法息息相關(guān)，是兩個(gè)對(duì)象的值是否相等的依據(jù)，所以當(dāng)我們覆蓋一個(gè)類的equals方法的時(shí)候也必須覆蓋hashCode方法。
例如String的hashCode方法為：
public int hashCode() {
int h = hash;
if (h == 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}可以看得出，一個(gè)字符串的哈希值為s[0]31n-1 + s[1]31n-2 + … + s[n-1]，是一個(gè)整數(shù)。也就是說所有的字符串可以通過hashCode()將其映射到整數(shù)的區(qū)間中，由于在java中整數(shù)的個(gè)數(shù)是有限的（四個(gè)字節(jié)有正負(fù)，***位為符號(hào)位-231 ~ 231 -1），當(dāng)s[0]31n-1 + s[1]31n-2 + … + s[n-1]足夠大的時(shí)候可能會(huì)溢出，導(dǎo)致其變成負(fù)值。從上面的情況我們可以看出兩個(gè)不同的字符串可能會(huì)被映射到同一個(gè)整數(shù)，發(fā)生沖突。因此java的開 發(fā)人員選擇了31這個(gè)乘數(shù)因子，盡量使得各個(gè)字符串映射的結(jié)果在整個(gè)java的整數(shù)域內(nèi)均勻分布。
談完java對(duì)象的哈希碼，我們來看看今天的主角HashMap，HashMap可以看作是Java實(shí)現(xiàn)的哈希表。HashMap中存放的是 key-value對(duì)，對(duì)應(yīng)的類型為java.util.HashMap.Entry，所以在HashMap中數(shù)據(jù)都存放在一個(gè)Entry引用類型的數(shù)組 table中。這里key是一個(gè)對(duì)象，為了把對(duì)象映射到table中的一個(gè)位置，我們可以通過求余法來，所以我們可以使用 [key的hashCode % table的長(zhǎng)度]來計(jì)算位置（當(dāng)然在實(shí)際操作的時(shí)候由于需要考慮table上的key的均勻分布可能需要對(duì)key的hashCode做一些處理）。
二.源碼解析
相關(guān)屬性 首先肯定是需要一個(gè)數(shù)組table，作為數(shù)據(jù)結(jié)構(gòu)的骨干。
transient Entry[] table;
這邊定義了一個(gè)Entry數(shù)組的引用。 繼續(xù)介紹幾個(gè)概念把
capacity容量 是指數(shù)組table的長(zhǎng)度
loadFactor 裝載因子，是實(shí)際存放量/capacity容量 的一個(gè)比值，在代碼中這個(gè)屬性是描述了裝載因子的***值，默認(rèn)大小為0.75
threshold（閾值）代表hashmap存放內(nèi)容數(shù)量的一個(gè)臨界點(diǎn)，當(dāng)存放量大于這個(gè)值的時(shí)候，就需要將table進(jìn)行夸張，也就是新建一個(gè)兩倍大的數(shù)組，并將老的元素轉(zhuǎn)移過去。threshold = (int)(capacity * loadFactor);
put方法詳解
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 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;
} 在HashMap中我們的key可以為null，所以***步就處理了key為null的情況。
當(dāng)key為非null的時(shí)候，你也許會(huì)認(rèn)為：恩，直接和table長(zhǎng)度相除取模吧，但是這里沒有，而是又好像做了一次哈希，這是為什么呢？這個(gè)還得先看indexFor(hash, table.length)方法，這個(gè)方法是決定存放位置的
static int indexFor(int h, int length) {
return h & (length-1);
}明眼的都可以發(fā)現(xiàn)，因?yàn)樵贖ashMap中table的長(zhǎng)度為2n (我們把運(yùn)算都換成二進(jìn)制進(jìn)行考慮)，所以h & (length-1)就等價(jià)于h%length，這也就是說，如果對(duì)原本的hashCode不做變換的話，其除去低length-1位后的部分不會(huì)對(duì) key在table中的位置產(chǎn)生任何影響，這樣只要保持低length-1位不變，不管高位如何都會(huì)沖突，所以就想辦法使得高位對(duì)其結(jié)果也產(chǎn)生影響，于是 就對(duì)hashCode又做了一次哈希
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}當(dāng)找到key所對(duì)應(yīng)的位置的時(shí)候，對(duì)對(duì)應(yīng)位置的Entry的鏈表進(jìn)行遍歷，如果以及存在key的話，就更新對(duì)應(yīng)的value，并返回老的 value。如果是新的key的話，就將其增加進(jìn)去。modCount是用來記錄hashmap結(jié)構(gòu)變化的次數(shù)的，這個(gè)在hashmap的fail- fast機(jī)制中需要使用（當(dāng)某一個(gè)線程獲取了map的游標(biāo)之后，另一個(gè)線程對(duì)map做了結(jié)構(gòu)修改的操作，那么原先準(zhǔn)備遍歷的線程會(huì)拋出異常）。 addEntry的方法如下
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry e = table[bucketIndex];
table[bucketIndex] = new Entry(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
} get方法
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry 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;
} get方法其實(shí)就是將key以put時(shí)相同的方法算出在table的所在位置，然后對(duì)所在位置的鏈表進(jìn)行遍歷，找到hash值和key都相等的Entry并將value返回。
名稱欄目：Java HashMap 核心源碼解讀
文章地址：http://www.dlmjj.cn/article/djsshio.html
