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