Sparta Yew

    sparta-紫杉  11/4/21 15:21

    在對《Set和hashCode()》的一篇原創(chuàng)文章寫完后，由于對自己的一些論斷產(chǎn)生了模糊和懷疑，因此又對Set進(jìn)行了一些研究，形成本篇。

    在Set的使用場景中，我們不外乎看中了她存儲數(shù)據(jù)的唯一性，即不能存儲重復(fù)值，這在某些應(yīng)用場合下是很必要的一個特性。那么從更深一層來考慮，Set究竟如何使數(shù)據(jù)不重復(fù)的呢？ 從另一個層面來考慮，她又如何確保在驗證數(shù)據(jù)是否重復(fù)過程中的快速性呢？ 假設(shè)存儲在Set中的數(shù)據(jù)有很多條，很普通的一個實(shí)現(xiàn)是每放入Set一個值value1，便提取Set中已有的多條數(shù)據(jù)跟該value1值進(jìn)行對比，若相同，則不允許放入，反之則放入。運(yùn)氣好的話，迭代到幾個元素之后便能夠判斷該值是否重復(fù)，否則，將會迭代所有已有的值。若是該Set中已經(jīng)存儲了上萬條的數(shù)據(jù)，或者十幾萬條的數(shù)據(jù)？

    一篇網(wǎng)文《Set是如何實(shí)現(xiàn)沒有重復(fù)元素的？》一文給出了答案，該文內(nèi)容翔實(shí)，說理性強(qiáng)，論據(jù)充分，是一篇難得的好文，在此感謝作者。尤其它指出了在Set的實(shí)現(xiàn)中，使用了Map的key唯一性來確保Set的值不重復(fù)(眾所周知，Map中的key是唯一的)，有興趣的可以去查看一下。

    那么，Map中的key又是如何確保重復(fù)驗證的快速性及key值的唯一性呢？

    放心，這難不倒聰明的java的創(chuàng)造者們。他們巧妙地利用了Hash算法來實(shí)現(xiàn)并達(dá)到這一目的。 那么Hash又是什么？

    Hash算法又稱為散列算法，其實(shí)Hash算法產(chǎn)生的目的很單純，其發(fā)明的目的是提高海量數(shù)據(jù)的查找速度。舉個實(shí)例更能說明問題：

    假設(shè)數(shù)據(jù)表中有N個無序的字符串（例如：中文人名），給你一個字符串，請迅速找到它在數(shù)據(jù)表中的序號。
最笨的方法是逐個比較的方式來查找。查找時間是O(N)，簡單說最后的情況是比較N次。

    hash 表能夠加快查找速度。使用hash表首先要申請一個定長的指針數(shù)組。通過在建立數(shù)據(jù)表時通過特定的計算公式（hash散列函數(shù)）計算出每個字符串對應(yīng)的一個數(shù)值（就是將不固定長度的字符串轉(zhuǎn)換成一個固定長度的數(shù)值或索引值）。而后把此數(shù)值作為數(shù)組下標(biāo)，把此字符串在數(shù)據(jù)表的序號保存在此數(shù)組元素中（可以擴(kuò)展到保存一個對象實(shí)例指針）。將來想查找某字符串對應(yīng)位置時，只需要通過hash散列函數(shù)計算出字符串對應(yīng)的值就可以直接知道此字符串的序號等信息了。
    這樣查找時間是O(1)了。因為不需要查找了，知道數(shù)組下標(biāo)就能訪問數(shù)組相應(yīng)元素了，而元素中保存的就是序號等信息。

     不妨給你一個直觀的比方吧：

    張三，給你個任務(wù)，你到山東省東營區(qū)去找一下一個叫做“李四”的人吧。張三很老實(shí)，說了聲是就走了，三個月后回來，終于找著了那個叫做李四的人。他后來跟我們說，他采用了遍歷的手法，即挨家挨戶的去問，去找。

    而將這個任務(wù)分配給王五的時候，王五說，老板，你給個確切的地址吧。老板說：山東省東營市東營區(qū)xx街道辦事處xx社區(qū)xx號。結(jié)果不到一天時間，王五便找著了。

    這也許就是hash查找算法與普通查找算法的區(qū)別。

    通過查看HashMap的源代碼證實(shí)，該HashMap確實(shí)采用了Hash算法來提高查找key的速度，并且使用了equals()來判斷是否重復(fù)，有代碼為證：

hash：

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

put:

     public V put(K key, V value) {
        if (key == null) 
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

HashMap的put原理是這樣的：
1、首先對key采用hashCode()方法進(jìn)行散列化，就是將key轉(zhuǎn)換生成一個int值，相同的key肯定會生成相同的int值，并對該int值進(jìn)行hash計算得到hash值。
2、通過hash值得到Entry數(shù)組的下標(biāo)，然后通過該下標(biāo)，得到已經(jīng)存入的數(shù)據(jù)，將已經(jīng)存入的數(shù)據(jù)的key和hash進(jìn)行比對，若相同證明是重復(fù)，則忽略。
3、若不相同，則通過addentry()方法將數(shù)據(jù)存入該數(shù)組的下標(biāo)中，同時存入的還有key、hash值。

用一句話說來就是，通過待存入的key的hash值計算出數(shù)組的下標(biāo)，并根據(jù)該下標(biāo)提取已經(jīng)存入的值，將兩者進(jìn)行比對，若相同則忽略，不同則put進(jìn)去。

現(xiàn)在知道為什么Map中的key是唯一性的原因了吧？ 這與Map在put時兢兢業(yè)業(yè)檢查的努力是分不開的。

假設(shè)有一個key為1，value為"zhangSan"，經(jīng)過hash之后成為101,那么這個101就作為數(shù)組的下標(biāo)，然后將hash=101、key=1及value="zhangSan"的值封裝成實(shí)體對象存放到該數(shù)組的101下標(biāo)處。因為不同的key會產(chǎn)生不同的hash值，這也是為什么HashMap不排序的原因！

get：

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

    那么通過key提取值時，當(dāng)然先要通過該key計算出hash值來，再通過這個hash值作為下標(biāo)提取出對應(yīng)的實(shí)體對象所容納的value來。
同時加了必要的判斷來確保提取出正確的數(shù)值來。

    哈哈，在一個確定的城市里，領(lǐng)到了一個確定的門牌號，相比在茫茫人海中漫無目的的撈針，知道為何提取數(shù)據(jù)如何之快了吧！