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