HashSet and HashMap

HashSet and HashMap

總體介紹

之所以把HashSetHashMap放在一起講解,是因?yàn)槎咴贘ava里有著相同的實(shí)現(xiàn)蜓斧,前者僅僅是對(duì)后者做了一層包裝仓蛆,也就是說(shuō)HashSet里面有一個(gè)HashMap(適配器模式)。因此本文將重點(diǎn)分析HashMap挎春。

HashMap實(shí)現(xiàn)了Map接口看疙,即允許放入keynull的元素豆拨,也允許插入valuenull的元素;除該類未實(shí)現(xiàn)同步外能庆,其余跟Hashtable大致相同施禾;跟TreeMap不同,該容器不保證元素順序搁胆,根據(jù)需要該容器可能會(huì)對(duì)元素重新哈希弥搞,元素的順序也會(huì)被重新打散,因此不同時(shí)間迭代同一個(gè)HashMap的順序可能會(huì)不同丰涉。 根據(jù)對(duì)沖突的處理方式不同拓巧,哈希表有兩種實(shí)現(xiàn)方式,一種開放地址方式(Open addressing)一死,另一種是沖突鏈表方式(Separate chaining with linked lists)肛度。Java HashMap采用的是沖突鏈表方式

從上圖容易看出投慈,如果選擇合適的哈希函數(shù)承耿,put()get()方法可以在常數(shù)時(shí)間內(nèi)完成。但在對(duì)HashMap進(jìn)行迭代時(shí)伪煤,需要遍歷整個(gè)table以及后面跟的沖突鏈表加袋。因此對(duì)于迭代比較頻繁的場(chǎng)景,不宜將HashMap的初始大小設(shè)的過(guò)大抱既。

有兩個(gè)參數(shù)可以影響HashMap的性能:初始容量(inital capacity)和負(fù)載系數(shù)(load factor)职烧。初始容量指定了初始table的大小,負(fù)載系數(shù)用來(lái)指定自動(dòng)擴(kuò)容的臨界值防泵。當(dāng)entry的數(shù)量超過(guò)capacity*load_factor時(shí)蚀之,容器將自動(dòng)擴(kuò)容并重新哈希。對(duì)于插入元素較多的場(chǎng)景捷泞,將初始容量設(shè)大可以減少重新哈希的次數(shù)足删。

將對(duì)象放入到HashMapHashSet中時(shí),有兩個(gè)方法需要特別關(guān)心:hashCode()equals()锁右。hashCode()方法決定了對(duì)象會(huì)被放到哪個(gè)bucket里失受,當(dāng)多個(gè)對(duì)象的哈希值沖突時(shí),equals()方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”咏瑟。所以拂到,如果要將自定義的對(duì)象放入到HashMapHashSet中,需要@OverridehashCode()equals()方法码泞。

方法剖析

get()

get(Object key)方法根據(jù)指定的key值返回對(duì)應(yīng)的value兄旬,該方法調(diào)用了getEntry(Object key)得到相應(yīng)的entry,然后返回entry.getValue()浦夷。因此getEntry()是算法的核心辖试。 算法思想是首先通過(guò)hash()函數(shù)得到對(duì)應(yīng)bucket的下標(biāo),然后依次遍歷沖突鏈表劈狐,通過(guò)key.equals(k)方法來(lái)判斷是否是要找的那個(gè)entry罐孝。

上圖中hash(k)&(table.length-1)等價(jià)于hash(k)%table.length,原因是HashMap要求table.length必須是2的指數(shù)肥缔,因此table.length-1就是二進(jìn)制低位全是1莲兢,跟hash(k)相與會(huì)將哈希值的高位全抹掉,剩下的就是余數(shù)了续膳。

//getEntry()方法
final Entry<K,V> getEntry(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[hash&(table.length-1)];//得到?jīng)_突鏈表
         e != null; e = e.next) {//依次遍歷沖突鏈表中的每個(gè)entry
        Object k;
        //依據(jù)equals()方法判斷是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

put()

put(K key, V value)方法是將指定的key, value對(duì)添加到map里改艇。該方法首先會(huì)對(duì)map做一次查找,看是否包含該元組坟岔,如果已經(jīng)包含則直接返回谒兄,查找過(guò)程類似于getEntry()方法;如果沒(méi)有找到社付,則會(huì)通過(guò)addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry承疲,插入方式為頭插法

//addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//自動(dòng)擴(kuò)容鸥咖,并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);//hash%table.length
    }
    //在沖突鏈表頭部插入新的entry
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

remove()

remove(Object key)的作用是刪除key值對(duì)應(yīng)的entry燕鸽,該方法的具體邏輯是在removeEntryForKey(Object key)里實(shí)現(xiàn)的。removeEntryForKey()方法會(huì)首先找到key值對(duì)應(yīng)的entry啼辣,然后刪除該entry(修改鏈表的相應(yīng)引用)啊研。查找過(guò)程跟getEntry()過(guò)程類似。

//removeEntryForKey()
final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);//hash&(table.length-1)
    Entry<K,V> prev = table[i];//得到?jīng)_突鏈表
    Entry<K,V> e = prev;
    while (e != null) {//遍歷沖突鏈表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要?jiǎng)h除的entry
            modCount++; size--;
            if (prev == e) table[i] = next;//刪除的是沖突鏈表的第一個(gè)entry
            else prev.next = next;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

HashSet

前面已經(jīng)說(shuō)過(guò)HashSet是對(duì)HashMap的簡(jiǎn)單包裝鸥拧,對(duì)HashSet的函數(shù)調(diào)用都會(huì)轉(zhuǎn)換成合適的HashMap方法党远,因此HashSet的實(shí)現(xiàn)非常簡(jiǎn)單,只有不到300行代碼住涉。這里不再贅述麸锉。

//HashSet是對(duì)HashMap的簡(jiǎn)單包裝
public class HashSet<E>
{
    ......
    private transient HashMap<E,Object> map;//HashSet里面有一個(gè)HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//簡(jiǎn)單的方法轉(zhuǎn)換
        return map.put(e, PRESENT)==null;
    }
    ......
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市舆声,隨后出現(xiàn)的幾起案子花沉,更是在濱河造成了極大的恐慌,老刑警劉巖媳握,帶你破解...
    沈念sama閱讀 223,002評(píng)論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件碱屁,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡蛾找,警方通過(guò)查閱死者的電腦和手機(jī)娩脾,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)打毛,“玉大人柿赊,你說(shuō)我怎么就攤上這事俩功。” “怎么了碰声?”我有些...
    開封第一講書人閱讀 169,787評(píng)論 0 365
  • 文/不壞的土叔 我叫張陵诡蜓,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我胰挑,道長(zhǎng)蔓罚,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,237評(píng)論 1 300
  • 正文 為了忘掉前任瞻颂,我火速辦了婚禮豺谈,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘贡这。我一直安慰自己茬末,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評(píng)論 6 398
  • 文/花漫 我一把揭開白布藕坯。 她就那樣靜靜地躺著团南,像睡著了一般。 火紅的嫁衣襯著肌膚如雪炼彪。 梳的紋絲不亂的頭發(fā)上吐根,一...
    開封第一講書人閱讀 52,821評(píng)論 1 314
  • 那天,我揣著相機(jī)與錄音辐马,去河邊找鬼拷橘。 笑死,一個(gè)胖子當(dāng)著我的面吹牛喜爷,可吹牛的內(nèi)容都是我干的冗疮。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼檩帐,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼术幔!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起湃密,我...
    開封第一講書人閱讀 40,196評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤诅挑,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后泛源,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拔妥,經(jīng)...
    沈念sama閱讀 46,716評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評(píng)論 3 343
  • 正文 我和宋清朗相戀三年达箍,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了没龙。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,928評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖硬纤,靈堂內(nèi)的尸體忽然破棺而出解滓,到底是詐尸還是另有隱情,我是刑警寧澤筝家,帶...
    沈念sama閱讀 36,583評(píng)論 5 351
  • 正文 年R本政府宣布伐蒂,位于F島的核電站,受9級(jí)特大地震影響肛鹏,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜恩沛,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評(píng)論 3 336
  • 文/蒙蒙 一在扰、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧雷客,春花似錦芒珠、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至部逮,卻和暖如春娜汁,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背兄朋。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工掐禁, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人颅和。 一個(gè)月前我還...
    沈念sama閱讀 49,378評(píng)論 3 379
  • 正文 我出身青樓傅事,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親峡扩。 傳聞我的和親對(duì)象是個(gè)殘疾皇子蹭越,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容

  • 一响鹃、基本數(shù)據(jù)類型 注釋 單行注釋:// 區(qū)域注釋:/* */ 文檔注釋:/** */ 數(shù)值 對(duì)于byte類型而言...
    龍貓小爺閱讀 4,268評(píng)論 0 16
  • 實(shí)際上,HashSet 和 HashMap 之間有很多相似之處巍佑,對(duì)于 HashSet 而言茴迁,系統(tǒng)采用 Hash 算...
    曹振華閱讀 2,515評(píng)論 1 37
  • 起點(diǎn)不高不低,距離不遠(yuǎn)不近萤衰,結(jié)局不好不壞堕义。不念過(guò)往的天真,不幻明天的想象,今天陽(yáng)光和風(fēng)都在倦卖。曾經(jīng)眼淚洗臉洒擦,曾經(jīng)固執(zhí)...
    微笑的百合花閱讀 1,697評(píng)論 3 4
  • 2017.11.7兒子正式斷母乳! 對(duì)于一直自己帶大怕膛,從他出生開始就沒(méi)有睡過(guò)一個(gè)安穩(wěn)覺的母親來(lái)說(shuō)熟嫩,其實(shí)真的不忍心說(shuō)...
    菜菜子082閱讀 554評(píng)論 0 1
  • 一只燃著的香煙, 抽與不抽它都在默默地消耗著褐捻。 它不像蠟燭掸茅, 燃得明亮就成就了自己的奉獻(xiàn); 它也不像美酒柠逞, 喝著醇...
    踏錯(cuò)了鞋子閱讀 270評(píng)論 1 2