久久精品小视频,亚洲国产欧美一区二区丝袜黑人 ,日韩黄色网址

blog已經(jīng)轉(zhuǎn)移至github,大家請(qǐng)?jiān)L問 http://qaseven.github.io/

Java中的HashMap淺析

　在Java的集合框架中，HashSet，HashMap是用的比較多的一種，順序結(jié)構(gòu)的ArrayList、LinkedList這種也比較多，而像那幾個(gè)線程同步的容器就用的比較少，像Vector和HashTable，因?yàn)檫@兩個(gè)線程同步的容器已經(jīng)不被JDK推薦使用了，這是個(gè)比較老式的線程安全的容器，JDK比較推薦的是采用Collections里面的關(guān)于線程同步的方法。
　　　　問題來源：
　　　　1.為什么要有HashMap？
　　　　《Thinking In Java》里面有一個(gè)自己采用二維數(shù)組實(shí)現(xiàn)的保存key-value的demo，書上也說到性能問題，因?yàn)閺臄?shù)據(jù)結(jié)構(gòu)的順序結(jié)構(gòu)的觀點(diǎn)來看，常規(guī)的線性存儲(chǔ)，你弱需要找到其中的某個(gè)元素，就需要遍歷這個(gè)鏈表或者數(shù)組，而遍歷的同時(shí)需要讓鏈表中的每一個(gè)元素都和目標(biāo)元素做比較，相等才返回，Java里面用equals或者==。這對(duì)性能是毀滅性的傷害。
　　　　2.HashMap的優(yōu)勢(shì)是什么？
　　　　Hash算法就是根據(jù)某個(gè)算法將一系列目標(biāo)對(duì)象轉(zhuǎn)換成地址，當(dāng)要獲取某個(gè)元素的時(shí)候，只需要將目標(biāo)對(duì)象做相應(yīng)的運(yùn)算獲得地址，直接獲取。
　　　　3.Java中的Hash？
　　　　事實(shí)上Java的數(shù)據(jù)無非就三種，基本類型，引用類型(類似C里面的指針類型）和數(shù)組，有些地方說是2種類型，只有引用類型和數(shù)組。通過這三種數(shù)據(jù)類型可以構(gòu)建出任何數(shù)據(jù)結(jié)構(gòu)。在Java中，ArrayList這種底層就是用Objec數(shù)組來構(gòu)建的，而HashMap也是用數(shù)組來構(gòu)建，只不過數(shù)據(jù)數(shù)組的數(shù)據(jù)類型是一個(gè)叫做Entry的內(nèi)部類來保存key、value、hash(不是hashCode)和next(也就是鏈表的下一個(gè)元素)。其實(shí)HashSet也是HashMap，只不過比較特殊，沒有使用Entry的value而只用了key而已。看看HashSet的構(gòu)造方法：
　　　　public HashSet() {
　　　　map = new HashMap<E,Object>();
　　　　}
　　　　所以從這個(gè)意義上來講就沒必要討論HashSet了，他只不過是特殊的HashMap而已。
　　　　HashMap詳解：
　　　　基調(diào)：由于通過hash算法產(chǎn)生的邏輯地址可能導(dǎo)致沖突，所以對(duì)于一個(gè)長(zhǎng)度為length的數(shù)組，里面存放小于length個(gè)數(shù)據(jù)元素的時(shí)候就有可能出現(xiàn)沖突的現(xiàn)象，因?yàn)楸热缯f要在長(zhǎng)度為16的數(shù)組中存放字符串(也就是一個(gè)空的HashMap默認(rèn)的長(zhǎng)度)，每個(gè)字符串通過調(diào)用自身的hashCode()方法會(huì)得到該字符串的hashCode，然后通過HashMap的這兩個(gè)方法會(huì)算出在數(shù)組中的位置，也就是下面的 i。
　　　　int hash = hash(key.hashCode());
　　　　int i = indexFor(hash, table.length);
　　　　任意字符串的hashCode通過上面2個(gè)方法都會(huì)得到一個(gè)i，這個(gè)i就是在數(shù)組中的位置，這里比較巧妙的設(shè)計(jì)就是indexFor(hash,table.length)這個(gè)方法：
　　　　static int indexFor(int h, int length) {
　　　　return h & (length-1);
　　　　}
　　　　這個(gè)方法里面的任意h與(length-1)做位運(yùn)算之后得到的值始終都是在length之內(nèi)的，也就是在數(shù)組table之內(nèi)，因?yàn)槟萌我庖粋€(gè)數(shù)來和另一個(gè)數(shù)來做與運(yùn)算，結(jié)果肯定是小于等于較小的哪一個(gè)數(shù)，我以前第一次看到這就比較震驚，為什么那些人能想出這么巧妙的計(jì)算在table中的位置的方法。與此同時(shí)，既然字符串調(diào)用hashCode()會(huì)得到一個(gè)值，那么就會(huì)出現(xiàn)不相同的字符串調(diào)用hashCode方法之后得到的值是一樣的，這種可能性是存在的，而且?guī)缀蹩隙ㄊ谴嬖诘摹＿@時(shí)候就需要在數(shù)組的某個(gè)位置增加一個(gè)鏈表結(jié)構(gòu)，用戶存儲(chǔ)相同的hashCode的字符串，而這個(gè)時(shí)候HashMap的size同樣也會(huì)自增1，盡管這2個(gè)字符串只有一個(gè)存在于數(shù)組中。HashMap中的size變量有兩個(gè)作用，第一是通過調(diào)用size()方法來返回map的長(zhǎng)度，
　　　　public int size() {
　　　　return size;
　　　　}
　　　　第二個(gè)作用相當(dāng)重要，就是解決hash算法的核心力量，解決沖突。在HashMap的構(gòu)造方法中可以看出，hashmap的長(zhǎng)度和底層數(shù)組table都是capacity，但是還有一個(gè)變量叫做threshold，極限值，閾值的意思，默認(rèn)情況的構(gòu)造方法：
　　　　public HashMap() {
　　　　this.loadFactor = DEFAULT_LOAD_FACTOR;
　　　　threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
　　　　table = new Entry[DEFAULT_INITIAL_CAPACITY];
　　　　init();
　　　　}
這個(gè)閾值就是數(shù)組長(zhǎng)度和加載因子的乘積，這東西有什么用呢，假設(shè)都按照默認(rèn)情況來看，默認(rèn)構(gòu)造方法構(gòu)造出來的hashmap長(zhǎng)度為16，底層數(shù)組長(zhǎng)度也為16，而閾值
　　　　threshold長(zhǎng)度為12，因?yàn)槟J(rèn)加載因子是0.75。也就是說當(dāng)箱map中存放12個(gè)元素是，map的結(jié)構(gòu)沒什么變化，但是當(dāng)存儲(chǔ)第13個(gè)的時(shí)候，table就需要擴(kuò)容了，擴(kuò)大為原來的2倍。這時(shí)候是什么結(jié)局呢，如果加載因子是1，那么map中存放16個(gè)的時(shí)候他是不會(huì)擴(kuò)容的，table.length = 16,而為0.75的時(shí)候存放16個(gè)數(shù)據(jù)的時(shí)候table.length = 32。那么同樣是存放16個(gè)數(shù)據(jù)，分別在長(zhǎng)度為16的數(shù)組和32的數(shù)組中存放，出現(xiàn)沖突的幾率一般來說16的數(shù)組要大一些，那為什么會(huì)大一些呢，因?yàn)槟硞€(gè)數(shù)據(jù)存放進(jìn)入數(shù)組的位置是根據(jù)
　　　　int hash = hash(key.hashCode());
　　　　int i = indexFor(hash, table.length);
　　　　這兩個(gè)方法算出來的，其中就包括table.length，換句話說，位置i跟hash和table.length是相關(guān)的，也就是說位置i與table.length是聯(lián)動(dòng)的，換個(gè)角度，存放的16個(gè)數(shù)據(jù)假設(shè)是固定的，而得出hashCode的算法也是固定的，那么位置i就只跟length的大小有關(guān)聯(lián)了，一般來說length越大，數(shù)據(jù)的沖突幾率就低一些，在map.getValue(key)的時(shí)候需要在鏈表中比較的次數(shù)就少一些，性能就高一些。這就是Java中hashmap的性能因素，一般來說加載因子factor大，同樣個(gè)數(shù)的數(shù)據(jù)所占用空間就越小，table.length就越小，沖突幾率就越大，反之空間利用率低，性能高，類比一下，比如你地上放了10個(gè)碗，你手里面握了10顆大米，你撒下去，前提是必須10顆米都要撒進(jìn)碗里，你是不是會(huì)發(fā)現(xiàn)有些碗里面裝了兩顆三顆，而有些碗是空的，接下來，你在地上擺20個(gè)碗，還是撒10顆米下去，依然是所有的米都要進(jìn)碗，依然還是會(huì)出現(xiàn)有些晚是空的，有些是一顆兩顆三顆這種現(xiàn)象，但是很明顯一般來講20個(gè)碗的時(shí)候每個(gè)碗里面裝不止一顆的情況要比10個(gè)碗的情況要少，當(dāng)然也不一定完全是這樣，但是一般來說是這樣，這就是hash算法，如果設(shè)計(jì)的好的情況下我們希望每個(gè)碗里面都最多放一顆進(jìn)去，但是這種情況比較少見，但不管怎么說，按照普遍情況來看，20個(gè)碗的裝多顆的情況是比10個(gè)碗裝多顆的情況要少一點(diǎn)。從數(shù)據(jù)結(jié)構(gòu)的角度來說叫做用空間換時(shí)間的策略，以空間換時(shí)間何止hash算法，雙向鏈表也是用空間換時(shí)間的策略。至于說為什么默認(rèn)是0.75，我估計(jì)這個(gè)是前輩們和科學(xué)家們總結(jié)出來的一個(gè)這種的辦法，空間利用率比較不錯(cuò)的同時(shí)性能比較令人接受吧。
　　　　順便說一下啊，當(dāng)我們不斷的往一個(gè)hashmap里面添加數(shù)據(jù)的時(shí)候，如果超過某個(gè)閾值，他就會(huì)擴(kuò)容，擴(kuò)容的同時(shí)會(huì)讓之前的所有元素重新生成地址，并且把原來的數(shù)組里面的數(shù)據(jù)遷移到新的數(shù)組中(新的數(shù)組容量是原來的兩倍長(zhǎng)度)。順便說下，這個(gè)數(shù)據(jù)遷移其實(shí)對(duì)性能損耗還是相當(dāng)大的，畢竟你是要復(fù)制數(shù)組，同時(shí)要重新構(gòu)建每個(gè)元素的在table中的位置，因此我們可以在使用hashMap之前大概的估算一下這個(gè)hashMap里面大概會(huì)存多少個(gè)元素，這樣就可以在new hashmap的時(shí)候就給定他的容量，這樣數(shù)據(jù)遷移的次數(shù)相對(duì)就少一些，性能就更好一點(diǎn)。
　　　　接下來從JDK的源碼來看看HashMap。
　　　　1.構(gòu)造出一個(gè)空的HashMap。默認(rèn)長(zhǎng)度16，底層Entry數(shù)組也是16的默認(rèn)長(zhǎng)度。默認(rèn)加載因子default_factor為0.75。閾值16*0.75=12。key和value都存在與Entry這個(gè)類型里面。
　　　　public HashMap() {
　　　　this.loadFactor = DEFAULT_LOAD_FACTOR;
　　　　threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
　　　　table = new Entry[DEFAULT_INITIAL_CAPACITY];
　　　　init();
　　　　}
　　　　2.調(diào)用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<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;
}
}

　　　　首先是判斷key是否為空，如果為空，那么調(diào)用下面這個(gè)方法，這個(gè)方法說明，HashMap的null的key始終是存放在table的table[0]位置的，不管table[0]位置有沒有沖突都是這樣。

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;
}

　　　　如果不為空，那么繼續(xù)，這里，如果算出來的位置i出已經(jīng)有元素了，說明沖突了，那么遍歷沖突鏈表，如果發(fā)現(xiàn)key相等，那么直接用新的value替換掉就的value并且返回舊的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;
}
}

　　　　接下來，上面的步驟說明，新添加的數(shù)據(jù)在位置i處不是key相等的情況，就真正的添加數(shù)據(jù)了。調(diào)用addEntry(hash, key, value, i)方法。
　　　　void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　Entry<K,V> e = table[bucketIndex];
　　　　table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
　　　　if (size++ >= threshold)
　　　　resize(2 * table.length);
　　　　}
　　　　此時(shí)把新的添加進(jìn)table[i]位置，而原來的數(shù)據(jù)(可能是null也可能是一個(gè)鏈表)的引用直接存放進(jìn)新的數(shù)據(jù)的next中。形成新的鏈表。
　　　　接下來就是調(diào)用map的get(key)方法了。這個(gè)過程和put方法是逆向的。

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;
}

　　　　首先判斷key == null，如過為true，那么調(diào)用getForNullKey()方法。遍歷table[0]出的鏈表，因?yàn)榭誯ey是存在table[0]處的。前面說到。
　　　　private V getForNullKey() {
　　　　for (Entry<K,V> e = table[0]; e != null; e = e.next) {
　　　　if (e.key == null)
　　　　return e.value;
　　　　}
　　　　return null;
　　　　}
　　　　如果key == null 為false，那么上面get方法的下半部分，通過hashCode算出hash，通過hash和table.length算出位置i，遍歷table[i]處的鏈表，ken相等，取出數(shù)據(jù)。

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;

　　　　這里還有一個(gè)Java里面的規(guī)定，就是2個(gè)對(duì)象的equals相等，那么hashCode也必須相等。但是hashCode相等equals不一定相等。這是hashmap存在于Java里面的依據(jù)，同時(shí)這就是為什么會(huì)有沖突的原因了，兩個(gè)不一樣的對(duì)象計(jì)算出來的hashCode相等的原因。如果2個(gè)對(duì)象equals相等，但是hashcode不想等，那就說明這2個(gè)元素都能存進(jìn)hashmap，但是很明顯hashmap里面的key是唯一的，直接就推翻了hashmap。
　　　　寫得比較粗糙，HashMap里面的很多細(xì)節(jié)都沒寫，主要是因?yàn)橐粊砦覀冎恍枰肏ashMap就行了，二來是細(xì)節(jié)源碼里面都有，看一下就知道了。

posted on 2014-07-22 09:24 順其自然EVO 閱讀(623) 評(píng)論(0) 編輯收藏所屬分類: 測(cè)試學(xué)習(xí)專欄

新用戶注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關(guān)文章: 如何進(jìn)行Web服務(wù)的性能測(cè)試？利用drozer進(jìn)行Android滲透測(cè)試 Appium Android Bootstrap源碼分析之命令解析執(zhí)行 Fliptest—iOS 的應(yīng)用A/B測(cè)試框架 iOS功能測(cè)試工具 Frank iOS單元測(cè)試框架Kiwi for iOS Appium Android Bootstrap之控件AndroidElement 移動(dòng)應(yīng)用測(cè)試框架—Calabash Android 簡(jiǎn)介 Appium Server源碼分析之作為Bootstrap客戶端移植MonkeyRunner的圖片對(duì)比功能實(shí)現(xiàn)-Appium篇

qileilove

Java中的HashMap淺析

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(55)

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜