您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java散列表怎么實(shí)現(xiàn)”,感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java散列表怎么實(shí)現(xiàn)”吧!
數(shù)組的特點(diǎn)是尋址容易,插入和刪除困難;而鏈表的特點(diǎn)是尋址困難,插入和刪除容易。而對于tree結(jié)構(gòu),它們的查找都是先從根節(jié)點(diǎn)進(jìn)行查找,從節(jié)點(diǎn)取出數(shù)據(jù)或索引與查找值進(jìn)行比較,雖然查找和增刪的綜合效率較好,但是最終還是需要進(jìn)行多次查找。為此引入了散列表來嘗試進(jìn)一步提升查找效率和增刪的綜合效率。
之前所掌握的查找算法,最簡單的順序表結(jié)構(gòu)查找包括簡單的順序查找、二分查找、插值查找、斐波那契查找,以及后來的樹結(jié)構(gòu)查找包括二叉排序樹、平衡二叉樹、多路查找樹、紅黑樹等。它們有一個(gè)功能特點(diǎn)就是,要查找的元素始終要與已經(jīng)存在的元素進(jìn)行多次比較,才能最終的出要該的元素是否存在或者不存在的結(jié)果。
我們知道,這些比較用于逐漸的定位某一個(gè)確切的位置,上面的大部分查找算法要求數(shù)據(jù)必須是有序存儲的,算法就是通過比較兩個(gè)數(shù)據(jù)的大小來縮小查找的范圍,最終找到一個(gè)大小相等的數(shù)據(jù),或說明該元素存在,或者最終也沒有找到一個(gè)大小相等的數(shù)據(jù),說明不存在。
為什么一定要“比較”?能否直接通過關(guān)鍵字key得到要查找的記錄內(nèi)存存儲位置呢?當(dāng)然有,這就是散列表。
事先在數(shù)據(jù)(這里可以是key-value鍵值對形式的數(shù)據(jù),也可以是單個(gè)key形式的數(shù)據(jù))的存儲位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)函數(shù)關(guān)系f,使得每個(gè)關(guān)鍵字k對應(yīng)一個(gè)存儲位置f(key)。即:存儲位置=f(key),該映射被稱為散列函數(shù),利用散列函數(shù)來存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)被稱為散列表。通過f(key)計(jì)算出存儲位置的過程被稱為散列,所得的存儲位置稱散列地址。
散列表通?;跀?shù)組來實(shí)現(xiàn)。存放數(shù)據(jù)的時(shí)候,散列函數(shù)f(key)根據(jù)key計(jì)算出數(shù)據(jù)應(yīng)該存儲的位置-數(shù)組下標(biāo),從而將不同的數(shù)據(jù)分散在不同的存儲位置,這也是“散列”的由來;查找的時(shí)候,通過散列函數(shù)f(key)對應(yīng)的key可以直接確定查找值所在位置-數(shù)組下標(biāo),而不需要一個(gè)個(gè)比較。這樣就“預(yù)先知道”key所在的位置,直接找到數(shù)據(jù),提升效率。散列表存放元素的數(shù)組位置也被稱為“槽(slot)”。
散列表與線性表、樹、圖等結(jié)構(gòu)不同的是,后幾種結(jié)構(gòu)數(shù)據(jù)元素之間都存在某種邏輯關(guān)系,而使用散列技術(shù)的散列表的數(shù)據(jù)元素之間不存在什么邏輯關(guān)系,元素的位置只與關(guān)鍵字key和散列函數(shù)f(key)有關(guān)聯(lián)。
對于查找來說,散列技術(shù)簡化了比較過程,效率就會大大提高,但萬事有利就有弊,由于數(shù)據(jù)元素之間并沒有確切的關(guān)系,散列技術(shù)不具備很多常規(guī)數(shù)據(jù)結(jié)構(gòu)的能力。相對于其他查找結(jié)構(gòu),它只支持部分操作(查找、增刪……),另一部分操作不能實(shí)現(xiàn)(排序、索引操作、范圍查找、順序輸出、查找最大/小值……)。因此,散列表主要是面向查找的存儲結(jié)構(gòu)。
散列表的英文名稱為 hash table,因此散列表又被稱為哈希表,散列函數(shù)又被稱為哈希函數(shù),函數(shù)的實(shí)現(xiàn)步驟被稱為散列算法/哈希算法。
我們還能看出來,散列算法實(shí)際上是將任意長度的key變換成固定范圍長度的值。這種轉(zhuǎn)換是一種壓縮映射,簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。也就是,散列值的范圍大小通常遠(yuǎn)小于輸入的key的范圍。
例如,輸入的key為5,28,19,15,20,33,12,17,10,共9個(gè),此時(shí)肯定不能將哈希表(內(nèi)部數(shù)組)的長度初始化為33,那樣的話就太浪費(fèi)空間了。理想的結(jié)果是,將這9個(gè)key通過某個(gè)散列函數(shù)f(key)將它們放入長度為10的哈希表(數(shù)組)中,并且然而由于散列算法是一種壓縮映射算法,散列表的長度單元是有限的,關(guān)鍵字key是無限的,對于某個(gè)散列算法,如果key樣本如果大,那么兩個(gè)不同的key映射到相同的單元,即f(key)的值相等的情況幾乎是一種必然,這種現(xiàn)象也被稱為散列沖突/哈希沖突。
例如對上面的key個(gè)數(shù)采用的散列函數(shù)是f(key)=key mod 9,f(5)=5,所以數(shù)據(jù)5應(yīng)該放在散列表的第5個(gè)槽里;f(28)=1,所以數(shù)據(jù)28應(yīng)該放在散列表的第1個(gè)槽里;f(19)=1,也就是說,數(shù)據(jù)19也應(yīng)該放在散列表表的第1個(gè)槽里——于是就造成了碰撞。
盡管我們可以通過精心設(shè)計(jì)的散列函數(shù)讓沖突盡可能的少,但是不能完全避免。因此散列表必須具備處理散列沖突的能力。
從上面的散列表的概述可以看出來,要實(shí)現(xiàn)散列表,最關(guān)鍵的就是散列函數(shù)f(key)的選擇和處理散列沖突的能力,我們先來看散列函數(shù)的選擇。
良好的散列函數(shù)應(yīng)該滿足下面兩個(gè)原則:
計(jì)算簡單:如果散列算法需要很復(fù)雜的計(jì)算,會耗費(fèi)很多時(shí)間,這對于需要頻繁地查找來說,就會大大降低查找的效率了。因此散列函數(shù)的計(jì)算時(shí)間不應(yīng)該超過其他查找技術(shù)與關(guān)鍵字比較的時(shí)間。
散列地址分布均勻:我們剛才也提到?jīng)_突帶來的問題,雖然不能完全避免沖突,但是可能設(shè)計(jì)好的散列函數(shù)盡量讓散列地址均勻地分布在存儲空間中,這樣可以保證存儲空間的有效利用,并減少沖突的發(fā)生和為處理沖突而耗費(fèi)的時(shí)間。 下面介紹幾種常用的散列函數(shù)構(gòu)造方法!
直接定址法
取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址(這種散列函數(shù)也叫自身函數(shù))。f(key)=a×key+b(a、b為常數(shù))。
比如對0-100歲人口數(shù)統(tǒng)計(jì),直接采用年齡作為關(guān)鍵字。
比如統(tǒng)計(jì)1980年忠厚每年出生的人口數(shù)目,我們可以對出生年份關(guān)鍵字減去1980來作為地址。
這樣的散列函數(shù)優(yōu)點(diǎn)就是簡單、均勻,也不會產(chǎn)生沖突,但問題是這需要事先知道關(guān)鍵字的分布情況,適合查找表較小且連續(xù)的情況。由于這樣的限制,在現(xiàn)實(shí)應(yīng)用中,此方法雖然簡單,但卻并不常用。
數(shù)字分析法
假設(shè)關(guān)鍵字是以r為基的數(shù),并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的,則可取關(guān)鍵字的若干數(shù)位組成哈希地址。
比如對于手機(jī)號碼的key,用手機(jī)號碼后四位參與計(jì)算。
數(shù)字分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況,如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻,就可以考慮用這個(gè)方法。
折疊法
將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分(注意最后一部分位數(shù)不夠時(shí)可以短些),然后將這幾部分疊加求和,并按散列表表長,取后幾位作為散列地址。 比如我們的關(guān)鍵字是9876543210,散列表表長為三位,我們將它分為四組,987|654|321|0,然后將它們疊加求和987+654+321+0=1962,再求后3位得到散列地址為962。
有時(shí)可能這還不能夠保證分布均勻,不妨從一端向另一端來回折疊后對齊相加。比如我們將987和321反轉(zhuǎn),再與654和0相加,變成789+654+123+0=1566,此時(shí)散列地址為566。
折疊法事先不需要知道關(guān)鍵字的分布,適合關(guān)鍵字位數(shù)較多的情況。
平方取中法
取關(guān)鍵字平方后的中間幾位為哈希地址。通過平方擴(kuò)大差別,另外中間幾位與乘數(shù)的每一位相關(guān),由此產(chǎn)生的散列地址較為均勻。
假設(shè)關(guān)鍵字是1234,那么它的平方就是1522756,再抽取中間的3位就是227,用做散列地址。再比如關(guān)鍵字是4321,那么它的平方就是18671041,抽取中間的3位就可以是671,也可以是710,用做散列地址。
平方取中法比較適合于不知道關(guān)鍵字的分布,而位數(shù)又不是很大的情況。
除留余數(shù)法
此方法為最常用的構(gòu)造散列函數(shù)方法。對于散列表長為m的散列函數(shù)公式為:f(key)=key mod p(p≤m)
mod是取模(求余數(shù))的意思。事實(shí)上,這方法不僅可以對關(guān)鍵字直接取模,也可在折疊、平方取中后再取模。很顯然,本方法的關(guān)鍵就在于選擇合適的p,p如果選得不好,就可能會容易產(chǎn)生沖突。HashMap就采用了這種方法(利用位運(yùn)算代替取模運(yùn)算,提高程序的計(jì)算效率)。需要注意的是,只有在特定情況下,位運(yùn)算才可以轉(zhuǎn)換成取模運(yùn)算(當(dāng) b = 2^n 時(shí),a % b = a & (b - 1) )。
因此根據(jù)前輩們的經(jīng)驗(yàn),若散列表表長為m,通常p為小于或等于表長(最好接近m)的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。
隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)數(shù),取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址。也就是:f(key)=random(key)
這里random是隨機(jī)函數(shù)。當(dāng)關(guān)鍵字的長度不等時(shí),采用這個(gè)方法構(gòu)造散列函數(shù)是比較合適的。
總之,現(xiàn)實(shí)中,應(yīng)該視不同的情況采用不同的散列函數(shù)。我們只能給出一些考慮的因素來提供參考:
1.計(jì)算散列地址所需的時(shí)間。
2.關(guān)鍵字的長度。
3.散列表的大小。
4.關(guān)鍵字的分布情況。
5.記錄查找的頻率。
綜合這些因素,才能決策選擇哪種散列函數(shù)更合適。
設(shè)計(jì)得再好的散列函數(shù)也不可能完全避免沖突。對無論以何種散列函數(shù)構(gòu)建的散列表,還必須考慮如何處理散列沖突。常見方法有以下幾種:
使用輔助數(shù)據(jù)結(jié)構(gòu):分離鏈接法/鏈地址法/拉鏈法
不使用輔助數(shù)據(jù)結(jié)構(gòu):開放定址法(線性探測、平方探測、雙散列)
再散列
在存儲數(shù)據(jù)的過程中,如果發(fā)生沖突,可以利用單鏈表在已有數(shù)據(jù)的后面插入新數(shù)據(jù),訪問的數(shù)組下標(biāo)元素作為鏈表的頭部。這種解決沖突的方法被稱為“分離鏈接法”,又被稱為分離鏈接法、拉鏈法。可以想象,除了鏈表之外,其他輔助結(jié)構(gòu)都能解決沖突現(xiàn)象:二叉樹或者另一張散列表,如果采用鏈表來輔助解決散列沖突,并且散列函數(shù)設(shè)計(jì)的很好,那么鏈表應(yīng)該是比較短的,此時(shí)其他復(fù)雜的輔助結(jié)構(gòu)便不值得嘗試了。
如下圖,使用鏈地址法的散列表:
JDK1.8之前的HashMap就是使用的鏈表來處理散列沖突,為了降低鏈表過長造成的遍歷性能損耗,在JDK1.8中采用鏈表+紅黑樹的方法來處理散列沖突,當(dāng)鏈表長度大于8個(gè)時(shí),轉(zhuǎn)換為紅黑樹,紅黑樹的查找效率明顯高于單鏈表的。而小于等于8個(gè)時(shí),采用鏈表則完全可以接受,避免紅黑樹的復(fù)雜結(jié)構(gòu)。
開放定址法的基本思路就是出現(xiàn)沖突時(shí),通過另外的算法尋找其他空余的位置,因此不需要額外的輔助數(shù)據(jù)結(jié)構(gòu),只要散列表足夠大,空的散列地址總能找到,并將記錄存入。
開放定址法法又可以分為線性探測法、平方探測法、雙散列法。
3.2.1 線性探測法(Linear Probing)
線性探測公式為:(H(key)+di)% m;其中H(key)為哈希函數(shù),m 為表長-1,di為一個(gè)增量序列(di=0,1,2,3...,m-1)。
線性探測法的主要思想是:當(dāng)發(fā)生碰撞時(shí)(一個(gè)鍵被散列到一個(gè)已經(jīng)有鍵值對的數(shù)組位置),我們會檢查數(shù)組的下一個(gè)位置,這個(gè)過程被稱作線性探測。線性探測可能會產(chǎn)生三種結(jié)果:
命中:該位置的鍵與要查找的鍵相同;
未命中:該位置為空;
該位置的鍵和被查找的鍵不同。
當(dāng)我們查找某個(gè)鍵時(shí),首先通過散列函數(shù)得到一個(gè)數(shù)組索引后,之后我們就開始檢查相應(yīng)位置的鍵是否與給定鍵相同,若不同則繼續(xù)查找(若到數(shù)組末尾也沒找到就折回?cái)?shù)組開頭),直到找到該鍵或遇到一個(gè)空位置。由線性探測的過程我們可以知道,若數(shù)組已滿的時(shí)候我們再向其中插入新鍵,會陷入無限循環(huán)之中。
3.2.2 平方探測法
如果散列函數(shù)選的不是那么的好,可能導(dǎo)致沖突不斷出現(xiàn)。如果先存入key1,能夠找到某個(gè)空余位置存入,存入key2時(shí)與key1沖突,此時(shí)被存入到key1的下一個(gè)位置,后來key3又與它們發(fā)生散列沖突……這樣就出現(xiàn)了關(guān)鍵字聚集在某一區(qū)域的情況,即出現(xiàn)了數(shù)據(jù)聚集的現(xiàn)象。
一種解決方法是,增大di的增量:(H(key)+di²)% m(di=0,1,2,3...,m/2)
增加平方運(yùn)算的目的是為了不讓關(guān)鍵字都聚集在某一塊區(qū)域。我們稱這種方法為平方探測法。
如果m—表長-1不為素?cái)?shù),那么備選單元的數(shù)量將會減少,造成散列沖突的可能性就會大大增加。
3.2.3 雙散列法
準(zhǔn)備兩個(gè)散列函數(shù)。雙散列一般公式為:F(i)= i * hash3(x),意思是用第二個(gè)散列函數(shù)算出x的散列值,然后在距離hash3(x),2hash3(x)的地方探測。
前面的鏈地址法和開放定址法都是為了讓散列表中的元素分布的更加合理,但是散列表空間總有用完的時(shí)候,甚至當(dāng)它們的散列表填充元素過多時(shí),都會增大發(fā)生散列沖突的概率。這里的再散列法就是計(jì)算出什么時(shí)候讓散列表進(jìn)行擴(kuò)展以及在散列表擴(kuò)展的時(shí)候,如何讓原來的元素在新的空間中合理的分布。
一般方法是:當(dāng)散列表的元素足夠的多時(shí),建立另外一個(gè)大約兩倍大的表,再用一個(gè)新的散列函數(shù),掃描整個(gè)原始表然后按照新的映射插入到新的表里,這就是再散列。其開銷非常大,因?yàn)樯婕暗剿性氐囊苿印?/p>
再散列的觸發(fā)條件通常有:只要表有一半滿了就做、只有當(dāng)插入失敗時(shí)才做(這種比較極端)、當(dāng)表到達(dá)某個(gè)擴(kuò)容因子時(shí)再做。第三種是較好的方法,HashMap就是用的這種方法。
散列表的擴(kuò)容因子: 所謂的擴(kuò)容因子α=填入表中的記錄個(gè)數(shù)/散列表長度,α標(biāo)志著散列表的裝滿的程度。一般來說,當(dāng)元素?cái)?shù)量達(dá)到設(shè)定的擴(kuò)容因子的數(shù)量時(shí),就表示可以進(jìn)行再散列擴(kuò)容了,也叫裝填因子。因此一個(gè)合理的擴(kuò)容因子非常重要。α越大,產(chǎn)生沖突的可能性就越大;α越小,產(chǎn)生沖突的可能性就越小,但是造成了空間浪費(fèi)。JDK1.8的HasmMap裝填因子默認(rèn)為0.75。
JDK已經(jīng)提供了現(xiàn)成的散列表實(shí)現(xiàn),比如著名的HashMap。JDK1.8的HashMap是采用數(shù)組+鏈表+紅黑樹來實(shí)現(xiàn)的。散列函數(shù)采用基于hashcode()的去除留余法,并且采用分離鏈接法和再散列法的散列沖突解決辦法。
這里提供另一種采用線性探測的散列表的Java簡單實(shí)現(xiàn),從下面的實(shí)現(xiàn)上可以看出來,實(shí)際上線性探測的散列表效率并不高,并且產(chǎn)生了數(shù)據(jù)聚集,但是JDK中也有使用線性探測實(shí)現(xiàn)的散列表類,比如ThreadLocal中的ThreadLocalMap,因?yàn)榫€性探測的實(shí)現(xiàn)比較簡單。
/** * 基于線性探測法的散列表簡單實(shí)現(xiàn) * * @param <K> key類型 * @param <V> value類型 */ public class LinearProbingHashMap<K, V> { /** * 存儲節(jié)點(diǎn)數(shù)據(jù)的數(shù)組 */ transient Entry<K, V>[] table; /** * 存儲的節(jié)點(diǎn)對象 * * @param <K> * @param <V> */ private static class Entry<K, V> implements Map.Entry<K, V> { /** * 保存hash值,避免重復(fù)計(jì)算 */ final int hash; /** * key值 */ final K key; /** * value值 */ V value; /** * 構(gòu)造器 * * @param hash * @param key * @param value */ private Entry(int hash, K key, V value) { this.hash = hash; this.key = key; this.value = value; } @Override public final K getKey() { return key; } @Override public final V getValue() { return value; } /*@Override public final String toString() { return hash + "=" + key + "=" + value; }*/ @Override public final String toString() { return key + "=" + value; } @Override public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } @Override public int hashCode() { return hash; } } /** * 散列表的容量,初始為16 */ private int capacity = 16; /** * 散列表節(jié)點(diǎn)數(shù)量 */ private int size; /** * 空構(gòu)造器,并不會初始化內(nèi)部數(shù)組 */ public LinearProbingHashMap() { } /** * 插入 * * @param key k * @param value v */ public V put(K key, V value) { //初始化 if (table == null) { table = new Entry[capacity]; } //擴(kuò)容,這里判斷元素?cái)?shù)量大于等于0.75*capacity if (size >= capacity * 0.75) { resize(2 * capacity); } int hash = hash(key); //計(jì)算應(yīng)該插入的數(shù)組元素下標(biāo) int position = hash & (capacity - 1); //插入邏輯,總會成功 while (true) { if (table[position] == null) { table[position] = new Entry<>(hash, key, value); size++; break; //判斷是否是重復(fù)的key,這里使用hash值和==判斷 } else if (hash == table[position].hashCode() && table[position].getKey() == key) { return table[position].setValue(value); } position = nextIndex(position, capacity); } return null; } /** * 查找 * * @param key 要查找的key * @return 查找到的value */ public V get(K key) { if (table == null) { return null; } //計(jì)算出key對應(yīng)的數(shù)組位置 int position = hash(key) & (capacity - 1); //如果該位置不為null,則開始查找連續(xù)的元素 if (table[position] != null) { do { if (table[position].getKey() == key) { return table[position].getValue(); } position = nextIndex(position, capacity); } while (table[position] != null); } return null; } /** * 刪除元素 * * @param key 查找的元素 * @return 被刪除的元素value;null不代表不是被刪除的value */ public V delete(K key) { if (table == null) { return null; } //計(jì)算出key對應(yīng)的數(shù)組位置 int position = hash(key) & (capacity - 1); V value; //如果該位置不為null,則開始查找連續(xù)的元素 if (table[position] != null) { do { if (table[position].getKey() == key) { //刪除元素 value = table[position].getValue(); table[position] = null; size--; //將后面的連續(xù)的元素全部重新插入 position = nextIndex(position, capacity); Entry<K, V> positionEntry; while ((positionEntry = table[position]) != null) { table[position] = null; size--; put(positionEntry.getKey(), positionEntry.getValue()); position = nextIndex(position, capacity); } return value; } position = nextIndex(position, capacity); } while (table[position] != null); } return null; } public int size() { return size; } /** * 獲取hash值,不是直接取hash值,而是借鑒了HashMap的擾動算法,這樣可以讓元素分布更加均勻 * * @param key k * @return hash值 */ private int hash(K key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } /** * 擴(kuò)容 * * @param newCapacity 新容量 */ private void resize(int newCapacity) { if (newCapacity <= 0) { throw new StackOverflowError("容量超出最大容量"); } this.capacity = newCapacity; Entry<K, V>[] oldTab = table; table = new Entry[capacity]; for (Entry<K, V> e : oldTab) { if (e != null) { int position = e.hashCode() & (capacity - 1); while (table[position] != null) { position = nextIndex(position, capacity); } table[position] = e; } } } /** * 下一個(gè)位置 * * @param i 當(dāng)前位置 * @param len 數(shù)組長度 * @return 下一個(gè)位置, 此處包含循環(huán)的邏輯循環(huán) */ private static int nextIndex(int i, int len) { return ((i + 1 < len) ? i + 1 : 0); } @Override public String toString() { return "LinearProbingHashST{" + "table=" + Arrays.toString(table) + '}'; } }
public class LinearProbingHashMapTest { public static void main(String[] args) { System.out.println("==========>插入一批元素"); LinearProbingHashMap<Object, Object> objectObjectLinearProbingHashMap = new LinearProbingHashMap<>(); objectObjectLinearProbingHashMap.put(49, 16); objectObjectLinearProbingHashMap.put("Aa", 1); objectObjectLinearProbingHashMap.put(34, 78); objectObjectLinearProbingHashMap.put(17, 85); //Aa與BB的hash值是一樣的 objectObjectLinearProbingHashMap.put("BB", 2); objectObjectLinearProbingHashMap.put(36, 36); objectObjectLinearProbingHashMap.put(21, 37); objectObjectLinearProbingHashMap.put(9, 87); objectObjectLinearProbingHashMap.put("兓", 62); objectObjectLinearProbingHashMap.put(46, 43); objectObjectLinearProbingHashMap.put("呵呵", 3); objectObjectLinearProbingHashMap.put("嘻嘻", 4); System.out.println(objectObjectLinearProbingHashMap); System.out.println("size:" + objectObjectLinearProbingHashMap.size()); System.out.println(objectObjectLinearProbingHashMap); System.out.println("==========>刪除 BB"); Object delete = objectObjectLinearProbingHashMap.delete("BB"); System.out.println(delete); System.out.println("size:" + objectObjectLinearProbingHashMap.size()); System.out.println(objectObjectLinearProbingHashMap); System.out.println("==========>插入(46,44) 重復(fù)添加46,將會替換value"); Object put = objectObjectLinearProbingHashMap.put(46, 44); System.out.println(put); System.out.println("size:" + objectObjectLinearProbingHashMap.size()); System.out.println(objectObjectLinearProbingHashMap); System.out.println("==========>插入null 將會嘗試添加到第一個(gè)元素"); Object putNull = objectObjectLinearProbingHashMap.put(null, "nullnull"); System.out.println(putNull); System.out.println("size:" + objectObjectLinearProbingHashMap.size()); System.out.println(objectObjectLinearProbingHashMap); System.out.println("==========>獲取null 對應(yīng)的value"); Object o = objectObjectLinearProbingHashMap.get(null); System.out.println(o); System.out.println("==========>擴(kuò)容"); objectObjectLinearProbingHashMap.put("BB", 5); System.out.println("size:" + objectObjectLinearProbingHashMap.size()); System.out.println(objectObjectLinearProbingHashMap); System.out.println("==========>獲取BB 對應(yīng)的value"); Object bb = objectObjectLinearProbingHashMap.get("BB"); System.out.println(bb); System.out.println("==========>刪除 34"); Object delete34 = objectObjectLinearProbingHashMap.delete(34); System.out.println(delete34); System.out.println("size:" + objectObjectLinearProbingHashMap.size()); System.out.println(objectObjectLinearProbingHashMap); } }
到此,相信大家對“Java散列表怎么實(shí)現(xiàn)”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。