容器学习一：HashMap源码分析

一.HashMap的存储结构

 

二.HashMap成员变量

    //默认初始容量，总为2的次方值
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    //最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //默认加载因子  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //Entry数组，每一个Entry是一个键值对实体
    transient Entry[] table;

    //实际存的Entry个数  
    transient int size;

    //数组扩容的阀值，当size+1 > threshold时，扩充到以前容量的两倍
    //threshold = table.length * loadFactor
    int threshold;

    //负载比率
    final float loadFactor;

    //Map结构一旦变化，如put remove clear等操作的时候，modCount随之变化
    transient volatile int modCount;

 

三.Entry对象

//很简单的一个键值对实体而已
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;          //key
        V value;              //value
        Entry<K,V> next;  //next Entry
        final int hash;       //计算出key的hash值

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
        .....
}

 

四.构造函数

	// 构造函数
	public HashMap(int initialCapacity, float loadFactor) {
		if (initialCapacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: "
					+ initialCapacity);
		if (initialCapacity > MAXIMUM_CAPACITY)
			initialCapacity = MAXIMUM_CAPACITY;
		if (loadFactor <= 0 || Float.isNaN(loadFactor))
			throw new IllegalArgumentException("Illegal load factor: "
					+ loadFactor);

		// 将传入的initialCapacity值，转变成2的次方值capacity去实例化hashmap的属性
		// 比喻传入initialCapacity = 100，则算出来capacity = 2 << 7 = 128，
		// 最终threshold = 128 * 0.75 = 96，table = new Entry[128]
		int capacity = 1;
		while (capacity < initialCapacity)
			capacity <<= 1;

		this.loadFactor = loadFactor;
		threshold = (int) (capacity * loadFactor);
		table = new Entry[capacity];
		// 模板方法模式，子类想在init里面做点什么重写init就好了
		init();
	}

 

五.hash算法和index算法

    /**
     * 让hashMap里面的元素尽量分布均需，方便查找
     * @param h entry中key的hash值
     * @return 打散后的hash值
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /** 
     * 类似求模运算， 将hash值同length-1(必定是01111...1)相与，运算的结果处于1到length-1间，0刚好用来保存key为null和0的元素 
     * @param h 打散后的hash值 
     * @param length 数组的长度 
     * @return 数组下标 1到lenght-1  
     */ 
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

六.取数据  

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        //key != null时
        //1.根据key计算出hash和index
        int hash = hash(key.hashCode());
        //2.从index处的链表头Entry e开始遍历链表，
        //如果e满足hash(key.hashCode()) == e.hash && (key == e.key || key.equals(e.key))，就是我们要找的entry
        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)))    //注释3里的逻辑更好理解
                return e.value;
        }
        return null;
    }

    //如果key为空，直接从table[0]链表里面遍历寻找value
    private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

 

七.存数据，扩容

public V put(K key, V value) {
    	//1.key为空时候，调用putForNullKey方法
        if (key == null)
            return putForNullKey(value);
        //2.key不为空
        //2-1.计算hash和index
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        //2-2.根据index得到当前链表头e=table[i]不为空
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //2-3.如果e满足hash(key.hashCode())=e.hash && key==e.key || key.equals(e.key)，value覆盖oldValue
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //2-4.table[i]为空，直接插入entry
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    private V putForNullKey(V value) {
    	//1.从0位置的链表头开始，遍历
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        	//1-1.e.key==null时，直接替代value
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //2.头Entry不存在时，直接插入entry
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
    
    /** 
     * @param hash 计算后key的hash值
     * @param key 
     * @param value
     * @param bucketIndex 应该插入到Entry[]的哪个位置
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
    	//1.当前bucketIndex位置的头Entry e
    	Entry<K,V> e = table[bucketIndex];
    	//2.在bucketIndex位置新建一个Entry，新建Entry.next=原头Entry，也就是addEntry的Entry都被加到了链表头
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        //hashmap在每次addEntry完后检查是否扩容，而list是在每次加入之前检查：ensureCapacity(size + 1);elementData[size++] = e;
        if (size++ >= threshold)
            resize(2 * table.length);
    }
    
    //扩容，把hashmap的容量设置为新容量newCapacity
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //每次扩到到原来的两倍，总有一个时候到MAXIMUM_CAPACITY
        if (oldCapacity == MAXIMUM_CAPACITY) {
        	//到了MAXIMUM_CAPACITY设置threshold后直接return
            threshold = Integer.MAX_VALUE;
            return;
        }

        //1.新建newCapacity大小的Entry数组
        Entry[] newTable = new Entry[newCapacity];
        //2.把当前Entry的数据全部移到新Entry数组中
        transfer(newTable);
        //3.用已经就绪的新Entry数组重新给table赋值
        table = newTable;
        //4.设置新的threshold
        threshold = (int)(newCapacity * loadFactor);
    }

    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        //1.从0开始遍历原Entry数组
        for (int j = 0; j < src.length; j++) {
        	//2.拿到下标为j的链表头Entry e
            Entry<K,V> e = src[j];
            //3.遍历链表
            if (e != null) {
                src[j] = null;
                do {
                	//3-1.e的下一个Entry，为了继续遍历做准备
                    Entry<K,V> next = e.next;
                    //3-2.计算e应该存放在新Entry数组的位置下标
                    int i = indexFor(e.hash, newCapacity);
                    //3-3.将e插入到新Entry[i]链表的表头
                    e.next = newTable[i];
                    //3-4.将Entry[i]表头的Entry重新定位为e，这样就完成了一个元素的重新hash 
                    newTable[i] = e;
                    //3-5.继续链表的下一个Entry
                    e = next;
                } while (e != null);
            }
        }
    }

 

八.删数据

 

public V remove(Object key) {
		Entry<K, V> e = removeEntryForKey(key);
		return (e == null ? null : e.value);
	}

	/**
	 * Removes and returns the entry associated with the specified key in the
	 * HashMap. Returns null if the HashMap contains no mapping for this key.
	 */
	final Entry<K, V> removeEntryForKey(Object key) {
		// 1.计算hash和index
		int hash = (key == null) ? 0 : hash(key.hashCode());
		int i = indexFor(hash, table.length);
		Entry<K, V> prev = table[i];
		Entry<K, V> e = prev;
		// 2.遍历i位置的Entry链表
		while (e != null) {
			Entry<K, V> next = e.next;
			Object k;
			// 2-1.e满足hash(key.hashCode()) == e.hash && (key == e.key ||
			// key.equals(e.key))，找到了要移除的Entry
			if (e.hash == hash
					&& ((k = e.key) == key || (key != null && key.equals(k)))) {
				// 2-2.移除操作modCount++, size--
				modCount++;
				size--;
				// 2-3-1.如果prev和e相等，说明要删除的Entry是链表头，直接将table[i]位置的Entry设置为next，就删除了e
				if (prev == e)
					table[i] = next;
				else
					// 2-3-2.如果不相等e =
					// prev.next，说明要删除的Entry是除链表头外的其他Entry，将prev.next设置为next，就删除了e
					prev.next = next;
				e.recordRemoval(this);
				return e;
			}
			// 把prev和e到移到下一个
			prev = e;
			e = next;
		}

		return e;
	}

	/**
	 * 还是将o的key拿到，然后和removeEntryForKey(Object key)一样了
	 * 
	 * @param o
	 *            must be Map.Entry
	 * @return
	 */
	final Entry<K, V> removeMapping(Object o) {
		if (!(o instanceof Map.Entry))
			return null;

		Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
		Object key = entry.getKey();
		......
	}

 

九.对table[0]位置存放数据的理解

package com.zzy.collection2;

import java.util.Map;

public class TestHashMapEntry0 {
	public static void main(String[] args) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(null, 1);
		map.put(null, 2);
		
		map.put(0, 3);
		map.put(0, 4);
	}

}

 

1. put(null, value)其本质是addEntry(0, null, value, 0);
2. put(0, value)其本质是addEntry(0, 0, value, 0);
3. put(null, value1)后put(0, value2)都是向table[0]链表中处添加Entry，但 0 != null，所有value2不会覆盖value1。
   
4. put(null, value1)后再次put(null, value2)，value2覆盖value1。