豐胸個(gè)人網(wǎng)站建設(shè)上海優(yōu)化網(wǎng)站公司哪家好
HashMap是Java語(yǔ)言中的一個(gè)重要數(shù)據(jù)結(jié)構(gòu),它實(shí)現(xiàn)了Map接口,允許我們存儲(chǔ)鍵值對(duì),并且可以根據(jù)鍵直接訪問對(duì)應(yīng)的值。
特性
- 鍵值對(duì)存儲(chǔ):HashMap存儲(chǔ)的是鍵值對(duì)數(shù)據(jù),可以方便的通過鍵來獲取值。
- 無(wú)序:HashMap中的元素沒有順序,每次輸出的順序都可能不一樣。這是因?yàn)镠ashMap內(nèi)部是通過哈希表來實(shí)現(xiàn)的,元素存儲(chǔ)在哈希表中,其位置取決于鍵的哈希值。
- 允許null鍵和null值:HashMap允許一個(gè)null鍵和一個(gè)null值。
- 擴(kuò)容:當(dāng)HashMap中的元素?cái)?shù)量達(dá)到一定的閾值(默認(rèn)是桶(bucket)的個(gè)數(shù),每個(gè)桶是一個(gè)鏈表或者紅黑樹)時(shí),會(huì)進(jìn)行擴(kuò)容,擴(kuò)容會(huì)導(dǎo)致原有的數(shù)據(jù)重新計(jì)算哈希值并重新放置
HashMap的工作原理
HashMap的工作原理主要涉及以下幾個(gè)部分:
- 哈希函數(shù):當(dāng)我們將鍵值對(duì)插入到HashMap中時(shí),HashMap會(huì)使用哈希函數(shù)(hash function)將鍵(key)轉(zhuǎn)換成一個(gè)哈希碼(hash code),這個(gè)哈希碼用來確定鍵值對(duì)應(yīng)該放在哪個(gè)桶(bucket)中。
- 桶和鏈表:在HashMap中,每個(gè)桶都是一個(gè)鏈表,鏈表中的每個(gè)節(jié)點(diǎn)都包含一個(gè)鍵值對(duì)。如果多個(gè)鍵哈希到同一個(gè)桶,那么這些鍵值對(duì)就會(huì)在鏈表中順序存儲(chǔ)。
- 擴(kuò)容和再哈希:當(dāng)某個(gè)桶中的鏈表長(zhǎng)度超過一個(gè)閾值(例如8)時(shí),HashMap會(huì)將這個(gè)桶拆分成兩個(gè)或更多的桶,這個(gè)過程就叫做擴(kuò)容。擴(kuò)容會(huì)使得HashMap的內(nèi)部數(shù)據(jù)結(jié)構(gòu)發(fā)生變化,可能會(huì)導(dǎo)致查詢性能下降。
- 紅黑樹:當(dāng)某個(gè)桶中的鏈表長(zhǎng)度超過一定閾值(例如16)時(shí),鏈表會(huì)轉(zhuǎn)化成紅黑樹以提高查詢效率。
源碼
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 其他常量 /** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 16; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Node<K,V>[] table; /** * The number of key-value mappings contained in this map. */ transient int size; /** * The next size value at which to resize (capacity * load factor). */ transient int threshold; /** * The load factor for the hash table. When the capacity is multiplied by * this factor, it is incremented. */ transient float loadFactor; // 其他變量和方法
}
其中,HashMap的核心是它的哈希表(由table數(shù)組實(shí)現(xiàn)),每個(gè)元素都是一個(gè)Node對(duì)象,其中包含鍵值對(duì)。HashMap還維護(hù)了一些其他變量,如size(映射數(shù)量)、threshold(下一次擴(kuò)容的閾值)和loadFactor(哈希表的加載因子)。
HashMap的主要方法包括:構(gòu)造函數(shù)、put(插入鍵值對(duì))、get(獲取鍵對(duì)應(yīng)的值)、remove(刪除鍵值對(duì))、isEmpty(判斷是否為空)等。其中,put和get方法是HashMap中最常用的方法,它們的實(shí)現(xiàn)涉及到哈希表的查找和插入操作。以下是put方法的源碼:
public V put(K key, V value) { return putVal(hash(key), key, value, false, true);
} final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) { // ①如果哈希表為空,將當(dāng)前元素插入到第一個(gè)位置。p為null。則直接在第一個(gè)位置插入元素。同時(shí)n++。 tab[i] = new Node<>(hash, key, value, null); // 創(chuàng)建新的節(jié)點(diǎn)插入到哈希表中。同時(shí)n++。如果超過閾值,則進(jìn)行擴(kuò)容。并重新計(jì)算哈希值和位置。并將元素插入到新的位置中。同時(shí)n++。如果超過閾值,則進(jìn)行擴(kuò)容。并重新計(jì)算哈希值和位置。
}}
如果哈希表已經(jīng)滿了,那么會(huì)進(jìn)行擴(kuò)容,即創(chuàng)建一個(gè)新的哈希表,大小是原來的兩倍,并將原來哈希表中的所有元素重新插入到新的哈希表中。擴(kuò)容會(huì)導(dǎo)致性能的損失,因?yàn)槊看尾迦氩僮鞫夹枰匦掠?jì)算元素的哈希值和位置。因此,在設(shè)計(jì)HashMap時(shí),需要考慮哈希表的大小和加載因子,以平衡性能和內(nèi)存使用。
在插入元素時(shí),如果哈希表中已經(jīng)存在相同的哈希值,那么會(huì)進(jìn)行沖突處理。HashMap采用鏈表或紅黑樹來處理沖突。當(dāng)沖突發(fā)生時(shí),會(huì)將當(dāng)前元素插入到鏈表的尾部或紅黑樹的葉節(jié)點(diǎn)上。當(dāng)鏈表的長(zhǎng)度超過一定閾值(如8)時(shí),會(huì)將鏈表轉(zhuǎn)換為紅黑樹,以提高查詢效率。
在查詢?cè)貢r(shí),HashMap會(huì)根據(jù)給定的鍵計(jì)算出哈希值,并找到對(duì)應(yīng)的桶。然后,在該桶中查找鏈表或紅黑樹,直到找到對(duì)應(yīng)的元素或到達(dá)鏈表的尾部或紅黑樹的葉節(jié)點(diǎn)。如果找不到指定的元素,則返回null。
總之,HashMap是一種高效的鍵值對(duì)存儲(chǔ)數(shù)據(jù)結(jié)構(gòu),通過哈希表實(shí)現(xiàn)了O(1)時(shí)間復(fù)雜度的插入、刪除和查詢操作。但是,由于哈希表的不確定性,HashMap不支持線程安全。如果需要線程安全,可以使用ConcurrentHashMap或者通過Collections.synchronizedMap方法將Map包裝為線程安全。
除了基本的操作,HashMap還提供了其他一些有用的方法,例如:
- containsKey(Object key):判斷指定鍵是否在Map中,存在則返回true。
- containsValue(Object value):判斷指定值是否在Map中,存在則返回true。
- get(Object key):返回指定鍵對(duì)應(yīng)的值,如果鍵不存在則返回null。
- putAll(Map<? extends K,? extends V> m):將指定Map中的所有映射復(fù)制到此Map中。
- remove(Object key):移除指定鍵及其關(guān)聯(lián)的值。
- size():返回Map中鍵-值映射關(guān)系的數(shù)量。
- isEmpty():測(cè)試此Map是否為空。
- keys():返回包含此映射中所有鍵的迭代器。
- values():返回包含此映射中所有值的迭代器。
- entrySet():返回包含此映射中所有映射關(guān)系的Set視圖。
此外,HashMap還提供了其他一些參數(shù)來控制其行為,如初始容量、加載因子等??梢酝ㄟ^構(gòu)造函數(shù)或者相關(guān)方法來設(shè)置這些參數(shù)。
總之,HashMap是一個(gè)非常實(shí)用的數(shù)據(jù)結(jié)構(gòu),適用于需要快速查找和插入鍵值對(duì)的情況。但是,需要注意的是,由于HashMap的不線程安全性,如果在多線程環(huán)境下使用,可能會(huì)導(dǎo)致數(shù)據(jù)的不一致性問題,需要使用線程安全的數(shù)據(jù)結(jié)構(gòu)或者通過Collections.synchronizedMap方法進(jìn)行包裝。