天天看點

Java_集合_HashMap(6)

1,儲存方式

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{
	
    static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
    transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
	
    transient int size;
    int threshold; // 負載因子
    final float loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
    transient int modCount; // 修改次數
	
    public HashMap(int initialCapacity, float loadFactor) {
	...
        threshold = initialCapacity;
	...
    }
	
    static class HashMapEntry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        HashMapEntry<K,V> next;
        int hash;
		
        HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    }
}
           

1)内部儲存為:HashMapEntry[],而HashMapEntry為明顯的連結清單特征,是以可以記住,HashMap的儲存方式為數組+連結清單

2)HashMap的儲存單元:(hash,key,value,bucketIndex)共同存儲

2,自增方式

public V put(K key, V value) {
	// table為空時,建立table,threshold初始值為4
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
			
	// 擷取 key的hash值
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
	// 擷取 hashcode對Length的求餘,Length的值一定是2的次幂
        int i = indexFor(hash, table.length);
		
	// 周遊,當key的hashCode和equal相等時,更新資料
        for (HashMapEntry<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;
    }
	
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
        // Android-changed: Replace usage of Math.min() here because this method is
        // called from the <clinit> of runtime, at which point the native libraries
        // needed by Float.* might not be loaded.
        float thresholdFloat = capacity * loadFactor;
        if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
            thresholdFloat = MAXIMUM_CAPACITY + 1;
        }
        threshold = (int) thresholdFloat;
        table = new HashMapEntry[capacity];
    }
	
    /**
     * {1 - 1}, {2 - 2}, {3 - 4}, {8 - 8}, {9 - 16}
     *
     * @param number 輸入參數
     * @return 傳回值,一定為2的次幂
     */
    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        int rounded = number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (rounded = Integer.highestOneBit(number)) != 0
                    ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
                    : 1;
        return rounded;
    }
	
    /**
     * 等價于 h % length
     * @param h hashCode值
     * @param length 2的次幂值
     * @return 求餘值
     */
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length - 1);
    }
	
    /**
     * 添加資料,解決Hash沖突問題
     *
     * @param hash        key的hash值
     * @param key         key值
     * @param value       value值
     * @param bucketIndex key的hash值,對容量求出的 bucketIndex
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
	    // 如果達到了最大容量,則擴容;并重新計算bucketIndex和hash值
        if ((size >= threshold) && (null != table[bucketIndex])) {
		    // 擴容
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
	
    /**
     * 擴容
     * @param newCapacity 新的容量大小,2的次幂值
     */
    void resize(int newCapacity) {
        HashMapEntry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        HashMapEntry[] newTable = new HashMapEntry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
	
    /**
     * Transfers all entries from current table to newTable.
     * 注意是所有(包含數組和連結清單),而不是頭部;這是為了解決平攤之後,可能餘值不一樣的問題
     */
    void transfer(HashMapEntry[] newTable) {
        int newCapacity = newTable.length;
        for (HashMapEntry<K,V> e : table) {
            while(null != e) {
                HashMapEntry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
	
    /**
     * 如果原先資料為空,則增加一條資料
     * 如果原先資料不為空,則“舊資料”成為“新資料”的next
     * 該處為連結清單形式
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMapEntry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
        size++;
    }
           

這裡的問題很多,面試問的最多的也是這一段,接下來一一回答

1)HashMap的實作原理:利用hashCode值将(hash,key,value, next)共同存儲,并采用數組+連結清單的形勢實作。

hash:擴容時,重新計算bucketIndex使用

key、value:儲存内容

next:上一次儲存的對象

2)如何解決HashCode碰撞:拉鍊法,即:以數組的節點作為連結點,延伸出一個連結清單進行存儲。

具體儲存的方法為:createEntry(...),每次放入都是作為一個連結清單節點放入

3)大小超過負載因子時:擴容,将原先所有資料從新計算bucketIndex再次安放。

容量:值永遠為2的次幂,為了使得(h & length - 1) == h % length公式成立

負載因子:當 存入的值,大于負載因子*容量 時,将會發生 refash(擴容);擴容執行了建立數組,并且将原先資料搬移過去,是很耗費性能的事,而hashCode是散列分布的,在容量快滿時,很有可能計算出重複的值。可以分析出,負載因子高時,可能導緻連結清單較長的可能性大,周遊時需要的時間增長;負載因子低時,連結清單長的可能性很小,但數組會較大;是以0.75為折中方案

4)多線程,同時擴充,發生了條件競争:可能出現死循環,是以多線程操作,需要線程安全的保障

5)為什麼HashMap的容量總是2的次幂:計算BucketIndex時,加快運作是速度。使得(h & length - 1) == h % length成立

3,查詢資料

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
	
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }
           

1)先計算出hashCode值,擷取到數組中的連結清單節點;

2)依據連結清單的頭部,依次執行equal方法,找出符合要求的value

4,整體大小

public int size() {
        return size;
    }
           

大小,則是通過使用一個全局量記錄。需要擷取時,擷取即可

5,外話

1)和Hashtable對比的影響性能的差別有:(更多的差別,就不列舉)

HashMap線程不安全,hashtable線程安全

HashMap容量為2的次幂,hashtable容量不是,是以hashMap在計算bucketIndex時,效率高很多

2)Map的子類中,還有幾個有意思的集合,可以去研究

IndentityHashMap:采用數組的偶數儲存Key,偶數+1儲存Value

TreeMap:采用維持紅黑樹,進而保障查詢資料的效率