久久国产成人午夜av影院,福利片在线观看,欧美日韩一区二区三区在线电影

Java中的HashMap淺析

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

　　　　如果不為空，那么繼續，這里，如果算出來的位置i出已經有元素了，說明沖突了，那么遍歷沖突鏈表，如果發現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;
}
}

　　　　接下來，上面的步驟說明，新添加的數據在位置i處不是key相等的情況，就真正的添加數據了。調用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);
　　　　}
　　　　此時把新的添加進table[i]位置，而原來的數據(可能是null也可能是一個鏈表)的引用直接存放進新的數據的next中。形成新的鏈表。
　　　　接下來就是調用map的get(key)方法了。這個過程和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，那么調用getForNullKey()方法。遍歷table[0]出的鏈表，因為空key是存在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相等，取出數據。

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;

　　　　這里還有一個Java里面的規定，就是2個對象的equals相等，那么hashCode也必須相等。但是hashCode相等equals不一定相等。這是hashmap存在于Java里面的依據，同時這就是為什么會有沖突的原因了，兩個不一樣的對象計算出來的hashCode相等的原因。如果2個對象equals相等，但是hashcode不想等，那就說明這2個元素都能存進hashmap，但是很明顯hashmap里面的key是唯一的，直接就推翻了hashmap。
　　　　寫得比較粗糙，HashMap里面的很多細節都沒寫，主要是因為一來我們只需要用HashMap就行了，二來是細節源碼里面都有，看一下就知道了。

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

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 如何進行Web服務的性能測試？利用drozer進行Android滲透測試 Appium Android Bootstrap源碼分析之命令解析執行 Fliptest—iOS 的應用A/B測試框架 iOS功能測試工具 Frank iOS單元測試框架Kiwi for iOS Appium Android Bootstrap之控件AndroidElement 移動應用測試框架—Calabash Android 簡介 Appium Server源碼分析之作為Bootstrap客戶端移植MonkeyRunner的圖片對比功能實現-Appium篇

qileilove

Java中的HashMap淺析

導航

統計

常用鏈接

留言簿(55)

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評論

閱讀排行榜

評論排行榜