Java提高篇（三三）-----Map總結

        在前面LZ詳細介紹了HashMap、HashTable、TreeMap的實現方法，從資料結構、實現原理、源碼分析三個方面進行闡述，對這個三個類應該有了比較清晰的了解,下面LZ就Map做一個簡單的總結。

        推薦閱讀：

         

java增進篇（二五）—–HashTable

       

Java提高篇（二六）-----hashCode Map

一、Map概述

        先看Map的結構示意圖

「鍵值」對映射的抽象介面。此映射不包括重複的鍵，一個鍵對應一個值。

       

SortedMap：有序的鍵值對接口，繼承Map接口。

        NavigableMap：繼承SortedMap，具有了針對給定搜尋目標傳回給定的導覽方法的介面。

        AbstractMap：實現了Map中大部分的函數介面。它減少了「Map的實作類別」的重複編碼。

        Dictionary：任何可將鍵映射到對應值的類別的抽象父類。目前被Map介面取代。

        TreeMap：有序散列表，並實現SortedMap 介面，底層透過紅黑樹實現。

        HashMap：是基於「拉鍊法」所實現的散列表。底層採用「數組+鍊錶」實作。

        WeakHashMap：基於「拉鍊法」所實現的雜湊列表。

        HashTable：基於「拉鍊法」所實現的雜湊。

       

二、內部雜湊： 雜湊映射技術

        幾乎所有通用Map都使用雜湊映射技術。對於我們程式設計師來說我們必須要對其有所了解。

        哈希映射技術是一種非常簡單的元素映射到陣列的技術。由於雜湊映射採用的是數組結果，那麼必然存在一中用於確定任意鍵存取數組的索引機制，該機制能夠提供一個小於數組大小的整數，我們將該機制稱為雜湊函數。在Java中我們不必為尋找這樣的整數而大傷腦筋，因為每個物件都必定存在一個傳回整數值的hashCode方法，而我們需要做的就是將其轉換為整數，然後再將該值除以數組大小取餘即可。如下：

int hashValue = Maths.abs(obj.hashCode()) % size;

下面是HashMap、HashTable的：

----------HashMap------------
//计算hash值
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//计算key的索引位置
static int indexFor(int h, int length) {
        return h & (length-1);
}
-----HashTable--------------
int index = (hash & 0x7FFFFFFF) % tab.length;     //确认该key的索引位置

 位置的索引代表了該節點在數組中的該節點。下圖為雜湊映射的基本原理圖：

         在該圖中1-4步驟是找到此元素在陣列中位置，5-8步驟是將該元素插入陣列中。在插入的過程中會遇到一點小挫折。在眾多肯能存在多個元素他們的hash值是一樣的，這樣就會得到相同的索引位置，也就說多個元素會映射到相同的位置，這個過程我們稱之為「衝突」。解決衝突的辦法是在索引位置處插入連結列表，並簡單地將元素新增至此連結列表。當然也不是簡單的插入，在HashMap中的處理過程如下：取得索引位置的鍊錶，如果該鍊錶為null，則將該元素直接插入，否則透過比較是否存在與該key相同的key，若存在則覆蓋原來key的value並傳回舊值，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。以下是HashMap的put方法，該方法詳細展示了計算索引位置，將元素插入到適當的位置的全部過程：

public V put(K key, V value) {
        //当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
        if (key == null)
            return putForNullKey(value);
        //计算key的hash值
        int hash = hash(key.hashCode());                 
        //计算key hash 值在 table 数组中的位置
        int i = indexFor(hash, table.length);            
        //从i出开始迭代 e,判断是否存在相同的key
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            //判断该条链上是否有hash值相同的(key相同)
            //若存在相同，则直接覆盖value，返回旧value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;    //旧值 = 新值
                e.value = value;
                e.recordAccess(this);
                return oldValue;     //返回旧值
            }
        }
        //修改次数增加1
        modCount++;
        //将key、value添加至i位置处
        addEntry(hash, key, value, i);
        return null;
    }

         HashMap
      如果我們查看其它的Map，發現其原理都差不多！

三、Map最佳化

         首先被映射，假設哈希映射的內部數組的大小只有1，所有的元素都將只有1，所有的元素都構成一個較大的位（從而一個長的大小（從而較大的大小）（從而較大地1，所有的元素都只有1，所有的元素都構成一個較大（從而一個長的）鍊錶。由於我們更新、訪問都要對這條鍊錶進行線性搜索，這樣勢必會降低效率。我們假設，如果存在一個非常大數組，每個位置鍊錶處都只有一個元素，在進行訪問時計算其 index 值就會獲得該對象，這樣做雖然會提高我們搜索的效率，但是它浪費了控制項。誠然，雖然這兩種方式都是極端的，但是它給我們提供了一種優化思路：使用一個較大的數組讓元素能夠均勻分佈。

在Map有兩個會影響到其效率，一是容器的初始化大小、二是負載因子。

3.1、調整實現大小

         在哈希映射表中，以內部數組中的每個位置稱為「儲存桶」(bucket)，而可用桶數的儲存空間（即可用桶的數組”大小）稱作容量(capacity)，我們為了讓Map物件能夠有效地處理任意數的元素，將Map設計成可以調整自身的大小。我們知道當Map中的元素達到一定量的時候就會調整容器本身的大小，但是這個調整大小的過程其開銷是非常大的。調整大小需要將原來所有的元素插入到新數組中。我們知道index = hash(key) % length。這樣可能會導致原先衝突的鍵不在衝突，不衝突的鍵現在衝突的，重新計算、調整、插入的過程開銷是非常大的，效率也比較低。所以，如果我們開始知道Map的預期大小值，將Map調整的足夠大，則可以大幅減少甚至不需要重新調整大小，這很有可能會提高速度。

下面是HashMap調整容器大小的過程，透過下面的程式碼我們可以看到其擴容過程的複雜性：

🎜🎜

void resize(int newCapacity) {
            Entry[] oldTable = table;    //原始容器
            int oldCapacity = oldTable.length;    //原始容器大小
            if (oldCapacity == MAXIMUM_CAPACITY) {     //是否超过最大值：1073741824
                threshold = Integer.MAX_VALUE;
                return;
            }

            //新的数组：大小为 oldCapacity * 2
            Entry[] newTable = new Entry[newCapacity];    
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
           /*
            * 重新计算阀值 =  newCapacity * loadFactor >  MAXIMUM_CAPACITY + 1 ? 
            *                         newCapacity * loadFactor :MAXIMUM_CAPACITY + 1
            */
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);   
        }
        
        //将元素插入到新数组中
        void transfer(Entry[] newTable, boolean rehash) {
            int newCapacity = newTable.length;
            for (Entry<K,V> e : table) {
                while(null != e) {
                    Entry<K,V> next = e.next;
                    if (rehash) {
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }
            }
        }

3.2、负载因子

         为了确认何时需要调整Map容器，Map使用了一个额外的参数并且粗略计算存储容器的密度。在Map调整大小之前，使用”负载因子”来指示Map将会承担的“负载量”，也就是它的负载程度，当容器中元素的数量达到了这个“负载量”，则Map将会进行扩容操作。负载因子、容量、Map大小之间的关系如下：负载因子 * 容量 > map大小  ----->调整Map大小。

         例如：如果负载因子大小为0.75（HashMap的默认值），默认容量为11，则 11 * 0.75 = 8.25 = 8，所以当我们容器中插入第八个元素的时候，Map就会调整大小。

        负载因子本身就是在控件和时间之间的折衷。当我使用较小的负载因子时，虽然降低了冲突的可能性，使得单个链表的长度减小了，加快了访问和更新的速度，但是它占用了更多的控件，使得数组中的大部分控件没有得到利用，元素分布比较稀疏，同时由于Map频繁的调整大小，可能会降低性能。但是如果负载因子过大，会使得元素分布比较紧凑，导致产生冲突的可能性加大，从而访问、更新速度较慢。所以我们一般推荐不更改负载因子的值，采用默认值0.75.

最后

        推荐阅读：

        java提高篇（二三）—–HashMap

        java提高篇（二五）—–HashTable

        Java提高篇（二六）-----hashCode

        Java提高篇（二七）—–TreeMap

 

---

以上就是Java提高篇（三三）-----Map总结的内容，更多相关内容请关注PHP中文网（www.php.cn）！