Sparta Yew

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

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

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

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

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

    放心，這難不倒聰明的java的創造者們。他們巧妙地利用了Hash算法來實現并達到這一目的。 那么Hash又是什么？

    Hash算法又稱為散列算法，其實Hash算法產生的目的很單純，其發明的目的是提高海量數據的查找速度。舉個實例更能說明問題：

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

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

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

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

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

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

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

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()方法進行散列化，就是將key轉換生成一個int值，相同的key肯定會生成相同的int值，并對該int值進行hash計算得到hash值。
2、通過hash值得到Entry數組的下標，然后通過該下標，得到已經存入的數據，將已經存入的數據的key和hash進行比對，若相同證明是重復，則忽略。
3、若不相同，則通過addentry()方法將數據存入該數組的下標中，同時存入的還有key、hash值。

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

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

假設有一個key為1，value為"zhangSan"，經過hash之后成為101,那么這個101就作為數組的下標，然后將hash=101、key=1及value="zhangSan"的值封裝成實體對象存放到該數組的101下標處。因為不同的key會產生不同的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提取值時，當然先要通過該key計算出hash值來，再通過這個hash值作為下標提取出對應的實體對象所容納的value來。
同時加了必要的判斷來確保提取出正確的數值來。

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