摘要：經(jīng)過上述討論，我們發(fā)現(xiàn)，哈希查找的時間復(fù)雜度最小沒有沖突是二是什么首先是中的一個接口。在中，有很多類實現(xiàn)了接口，就是其中的一個三是什么是一個實現(xiàn)了接口的基于哈希表的類。
我們要想知道HashMap是什么就先要了解Hash和Map是什么
一、Hash是什么
① 哈希查找是一種數(shù)據(jù)結(jié)構(gòu)中用于 查找 的算法，相比于其他查找算法，他的時間復(fù)雜度更
低，所以在實際應(yīng)用中大量采取了哈希表的方式，Hashmap就是java內(nèi)置的哈希查找的方法
② 哈希函數(shù)的基本思想： 將記錄的存儲地址和關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系。這樣，當(dāng)想查找某條記錄時，我們根據(jù)記錄的關(guān)鍵字就可以得到它的存儲地址，進(jìn)而快速判斷這條記錄是否存在，存儲在哪里。
③負(fù)載因子：負(fù)載因子是哈希表在其容量自動增加之前可以達(dá)到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負(fù)載因子越大表示散列表的裝填程度越高，反之愈小。如果負(fù)載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負(fù)載因子太小，那么散列表的數(shù)據(jù)將過于稀疏，對空間造成嚴(yán)重浪費(fèi)。hashmap默認(rèn)負(fù)載因子為0.75，一般情況下我們是無需修改的。
④ 哈希函數(shù)的缺陷+改進(jìn)方式： 在哈希存儲中，不同的關(guān)鍵字可能映射到了相同的地址，這就叫產(chǎn)生沖突，我們必須相處沖突處理的方法。當(dāng)然，前輩們已經(jīng)相處了各種各樣的方法，我在這里先不做深究。
⑤ 經(jīng)過上述討論，我們發(fā)現(xiàn)，哈希查找的時間復(fù)雜度最?。]有沖突）是O(1)
二、Map是什么
首先Map是java中的一個接口。它是java中的一種重要的數(shù)據(jù)結(jié)構(gòu)。
Map是從鍵(關(guān)鍵字)到值(記錄)的映射,鍵不允許重復(fù),每個鍵最多能映射一個值。
在java中，有很多類實現(xiàn)了Map接口，HashMap就是其中的一個
三、Hashmap是什么
HashMap是一個實現(xiàn)了Map接口的基于哈希表的類 。
也就是說，HashMap既有map的鍵值對特點，也有哈希表的特點
簡單點說，利用HashMap類：
查找時，給出一個關(guān)鍵字key，我們可以根據(jù)hash算法計算出key-value的存儲位置然后取出value
存儲時，我們根據(jù)哈希算法計算出該鍵值對應(yīng)該存儲的位置，將其存進(jìn)去。
也就是說，當(dāng)沒有沖突時，HashMap存取的時間復(fù)雜度為O(1)
這是HashMap類的部分代碼(部分?jǐn)?shù)據(jù)域和構(gòu)造函數(shù))
public class HashMap extends AbstractMap
implements Map, Cloneable, Serializable {
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)初始容量
static final int MAXIMUM_CAPACITY = 1 << 30; //HashMap的最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默認(rèn)負(fù)載因子0.75
static final int TREEIFY_THRESHOLD = 8; //當(dāng)某條鏈表中元素的個數(shù)大于8時//將轉(zhuǎn)變?yōu)榧t黑樹
transient Node[] table; // table數(shù)組，每一個元素都是一個Node對象，接下來會介紹Node是什么
transient Set> entrySet;
transient int size; //記錄哈希表中的鍵值對個數(shù)
int threshold; //閾值，即當(dāng)table中元素個數(shù)大于這個值就要resize()
final float loadFactor; //加載因子
HashMap有四種構(gòu)造函數(shù)
①第一種 允許用戶自己決定初始容量和加載因子，但這個初始容量不一定是HashMap真正的初始容量，下文會對此進(jìn)行解釋
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//初始容量不可以小于0
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;//不可以大于最大容量
if (loadFactor <= 0 ||Float.isNaN(loadFactor))//加載因子不可以小于0
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
在構(gòu)造函數(shù)中，我們可以看到，閾值利用tableSizeFor進(jìn)行了計算，而此時的閾值并不是真正的閾值，是數(shù)組的容量，我們也會發(fā)現(xiàn)其實在構(gòu)造函數(shù)中并沒有給table分配內(nèi)存，這是因為在插入鍵值對時，put函數(shù)會判斷table是否為null，如果是那么用resize()函數(shù)為其分配空間并計算真正的閾值
其他三種構(gòu)造函數(shù)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
}
【小貼士】
1.AbstractMap抽象類是什么？
AbstractMap抽象類實現(xiàn)了Map接口的大部分方法，讓HashMap繼承它減少了實現(xiàn)Map接口的工作量。那它為什么是抽象類呢，因為它有唯一的一個抽象方法
Public abstract Set> entrySet();
當(dāng)然在HashMap中有很多方法對AbstractMap的方法進(jìn)行了覆蓋
下一節(jié)：HashMap的數(shù)據(jù)結(jié)構(gòu)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69987.html
