HashMap

HashMap jdk-1.8.0

一、总结

• 允许key = null
• put时，hash散列值相同的元素，放在Entry 的首位置上
• 数组扩容，length*2
• 链表扩容，一个链转变为红黑树
• Map m = Collections.synchronizedMap(new HashMap(...)); 线程安全
• ConcurrentHashMap 线程安全

二、成员变量

1.源码

    /**
     * The default initial capacity - MUST be a power of two.
     */
    // 默认的初始化容量大小，一定是2的N幂 2^N
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    // 最大的容量，一定要是2^N的形式 且小于 2^30 
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    // 默认的负载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    // hashMap 数组+链表组成，Entry 数组部分
    transient Entry[] table;

    /**
     * The number of key-value mappings contained in this map.
     */
    // hashMap中key-value对的数量
    // transient 不可序列化
    transient int size;

    /**
     * The next size value at which to resize (capacity * load factor).
     * @serial
     */
    // threshold = capacity * load factor ; 边界值，
    // 当新增元素后的Map.size >= threshold , hashMap 进行扩容操作 
    int threshold;

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    // 负载因子，final 修饰，内容不可变更
    final float loadFactor;

    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     */
    // hashMap 被修改的次数，volatile 线程间可见，防止多个线程同时对一个hashMap进
    // 行操作，抛出异常
    transient volatile int modCount;

三、构造方法

1.1源码

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        // 初始化hashMap的容量大小
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // hashMap 的最大容量 2^30 
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        // 负载因子：小于0 或者 不是一个 数值 
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        // 数组的大小，一定是一个  2^N次幂的形式
        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        // 1 向左移动一位，与当前的初始化的大小进行比较；如果小于，继续移位
        // 初始化时，可以直接定义为  2^N 次幂


        this.loadFactor = loadFactor;
        // 计算边界值，如果新增数据后 size > threshold 则扩充
        threshold = (int)(capacity * loadFactor);
        table = new Entry[capacity];
        // 初始化
        init();
    }

1.2.分析

1.2.1

Float.isNaN()

1.2.2 init()
方法体内无任务实现，是给子类提供的，如 LinkedHashMap 继承 HashMap 并覆盖重写了此方法

2.

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentExcepti[/ur[/url]l]on if the initial capacity is negative.
     */
    // 根据指定的容量初始化
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    // 默认的构造方法
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // 0.75
        threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
        // 16*0.75
        table = new Entry[DEFAULT_INITIAL_CAPACITY];
        init();
    }

3.源码

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    // 根据已有的Map初始化
    public HashMap(Map<? extends K, ? extends V> m) {
    // 容量大小： m.size / 0.75 + 1 与 16 取最大值 
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }
    // 遍历Map
    private void putAllForCreate(Map<? extends K, ? extends V> m) {
        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
            Map.Entry<? extends K, ? extends V> e = i.next();
            putForCreate(e.getKey(), e.getValue());
        }
    }  


    /**
     * This method is used instead of put by constructors and
     * pseudoconstructors (clone, readObject).  It does not resize the table,
     * check for comodification, etc.  It calls createEntry rather than
     * addEntry.
     */
    private void putForCreate(K key, V value) {

        // 判断key 是否为 null 若是，则放在 数组 0 的位置上
        // 否则，进行二次hash计算
        int hash = (key == null) ? 0 : hash(key.hashCode());
        // hash % length 确定数据存放在数组中的位置
        int i = indexFor(hash, table.length);

        /**
         * Look for preexisting entry for key.  This will never happen for
         * clone or deserialize.  It will only happen for construction if the
         * input Map is a sorted map whose ordering is inconsistent w/ equals.
         */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                // key 已存在，返回原有的value值，并替换为新值
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }

        createEntry(hash, key, value, i);
    }

    /**
     * Like addEntry except that this version is used when creating entries
     * as part of Map construction or "pseudo-construction" (cloning,
     * deserialization).  This version needn't worry about resizing the table.
     *
     * Subclass overrides this to alter the behavior of HashMap(Map),
     * clone, and readObject.
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        // bucketIndex 数组中存放该数据的位置
        // 取出该位置的原有的链表
	Entry<K,V> e = table[bucketIndex];
        // 生成新的链表
        // Entry 的构造方法
        // 将原有的链表数据放在新加入的Entry 的链接的next位置上
        // 新加入的数据在链表的首位
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        // size 表示 map 中 key - value 对的数量
        size++;
    }

四、get

1.源码

    public V get(Object key) {
        // hashMap允许key = null .将所有key = null 的放在数组0 的位置上
        if (key == null)
            // 去数组第0个位置上查找
            return getForNullKey();
        // 计算hash数值
        int hash = hash(key.hashCode());
        // 取出 hash值对应的数组中的位置
        // 遍历此位置下的链表，是否有与key相等的值；有则返回value，无返回null
        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;
    }

    /**
     * Offloaded version of get() to look up null keys.  Null keys map
     * to index 0.  This null case is split out into separate methods
     * for the sake of performance in the two most commonly used
     * operations (get and put), but incorporated with conditionals in
     * others.
     */
    // 取出 key = null 的数组第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;
    }

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    // 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);
    }

    /**
     * Returns index for hash code h.
     */
    // 计算后的hash值与当前数组的长度取余
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

五、containsKey()

    /**
     * Returns <tt>true</tt> if this map contains a mapping for the
     * specified key.
     *
     * @param   key   The key whose presence in this map is to be tested
     * @return <tt>true</tt> if this map contains a mapping for the specified
     * key.
     */
    // 当前map 中是否包含 某个 key 值
    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

    /**
     * Returns the entry associated with the specified key in the
     * HashMap.  Returns null if the HashMap contains no mapping
     * for the key.
     */
    // 判断当前的key是否为null,若是，hash = 0 ；否则，计算hash值
    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        // 获取 hash % length 位置处的数组，遍历链表
        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 != null && key.equals(k))))
                return e;
        }
        return null;
    }

六、put

1.源码

    /**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        // hashMap 允许 key = null 
        // 判断 key == null ，若是 ，放在 数组 0 的位置上
        if (key == null)
            return putForNullKey(value);
        // 跟组 key 的hash值再次计算 hash 
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        // 确认存放位置 hash % length 
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 判断当前的 key 是否已存在，若是，返回 value 
            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;
    }

    /**
     * Offloaded version of put for null keys
     */
    private V putForNullKey(V value) {
        // 取出 数组 0 位置处的链表，判断链表是否已有值，若有，替换value，返回
        // 原有的 value
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        // 新增value
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    /**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    // 增加数组
    // hash 表示 key 的hash值
    // key value 为需要加入的数据
    // buketIndex 数组的下标位置
    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        // Entry<K,V> 构造方法，四个成员变量
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            // 扩容：当前数组长度的2倍
            resize(2 * table.length);
    }

        /**
         * Creates new entry.
         */
         // 新加入的链表的值，放在链表的首位，将原有的链表作为新加入值的next
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

    /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    // 数组扩容，当 size > threshold = init
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        // 若数组大小已经达到最大值，不再扩容
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        
        Entry[] newTable = new Entry[newCapacity];
        // 数组重新定位存储位置
        transfer(newTable);
        table = newTable;
        // 新的负载因子
        threshold = (int)(newCapacity * loadFactor);
    }

    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable) {
        // 将数组赋值给src，不对原数组进行变更
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            // 取出原数据中 j 位置的数据
            Entry<K,V> e = src[j];
            if (e != null) {
                // 释放存储空间
                src[j] = null;
                do {
                    // 原链表的 e.next
                    Entry<K,V> next = e.next;
                    // 新数组中的存放位置
                    int i = indexFor(e.hash, newCapacity);
                    // 原链表的 e.next 指向  新数组中的 i 处的链表
                    e.next = newTable[i];
                    // 将 原链表的 e 赋值给  新的链表
                    newTable[i] = e;
                    // 原链表的指针下移
                    e = next;
                    // 处理结果，新的链表中的数据是原链表中数据的倒置
                } while (e != null);
            }
        }
    }

扩容，将原数组中的数据拷贝到新的数组中

2.总结

modCount 记录当前操作此Map的次数

在 对map进行迭代处理时，会记录操作的次数，当modCount 与 期望的操作次数不同时，抛出
throw new ConcurrentModificationException();

七.remove

1.源码

    /**
     * Removes the mapping for the specified key from this map if present.
     *
     * @param  key key whose mapping is to be removed from the map
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    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) {
        // 计算 hash 值
        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;

        while (e != null) {
            // 非空
            Entry<K,V> next = e.next;
            Object k;
            // 获取数组i位置处的链表，遍历此链表
            // 若key在链表首位，则将 e 直接指向  e.next 
            // 若key不在链表首位，prev.next = next 
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++; // 操作次数，fast fail 
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next; // 链表指针下移
        }

        return e;
    }

八、clone

1.源码

    /**
     * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
     * values themselves are not cloned.
     *
     * @return a shallow copy of this map
     */
    public Object clone() {
        HashMap<K,V> result = null;
	try {
	    result = (HashMap<K,V>)super.clone();
	} catch (CloneNotSupportedException e) {
	    // assert false;
	}
        result.table = new Entry[table.length];
        result.entrySet = null;
        result.modCount = 0;
        result.size = 0;
        result.init();
        result.putAllForCreate(this);

        return result;
    }

2.分析

对当前map 的 拷贝，包括值

九、modCount 快速失败

1.示例

Map<String,String> map = new HashMap<String,String>();
map.put("1", "1");
map.put("2", "1");
map.put("3", "1");
map.put("4", "1");
map.put("5", "1");
		
Iterator<String> iterator = map.keySet().iterator();
while(iterator.hasNext()){
String next = iterator.next();
map.put("6", "5");
}

2.分析
快速失败 modCount 记录当前的线程对此集合的操作次数，迭代前，将 modCount 赋值给 expectedCount ,在迭代过程中如果 modCount 发生变更，则说明有其他线程在对此 map 进行操作

3.源码

   private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;	// next entry to return
        int expectedModCount;	// For fast-fail
        int index;		// current slot
        Entry<K,V> current;	// current entry

        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Entry<K,V> nextEntry() {
             // 此处判断，失败
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
	    current = e;
            return e;
        }

}

HashMap分析
扩容机制