HashMap源码分析

  size记录了所有键值对的数目，包括数组（内部实现）中的和数组某些位置附属链表（hash值相同，不允许覆盖已存在的键值对，所以要以链表形式附加）中的键值对。

HashMap的内部实现是数组+链表，通过键的hash值来定位键值对在数组中的位置，是一种离散结构，所以数组的某些索引上没有存储元素。

1. 默认参数：

// 默认初始容量 - 必须是2的乘方值
static final int DEFAULT_INITIAL_CAPACITY = 16;

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

// 加载因子，在0~1之间取值，太小导致空间浪费；太大导致哈希冲突频繁。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

2. 读取

    // 返回和指定的键关联的键值对
    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : 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 != null && key.equals(k)))) // 键值对的哈希值相等并且键相同或者键的值相等
                return e;
        }
        return null;
    }

3. 添加

    // 在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系，则旧值被替换。
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        // 遍历，如果有，则更新值，返回旧值，modCount不变
        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); // HashMap实现为空，子类可以重写
                return oldValue;
            }
        }

        // 增加新的键值对，修改次数加1
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

    // key为null时优化
    private V putForNullKey(V 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;
            }
        }

        // 没有找到则新增键值对，修改次数加1
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    // 该方法取而代之put方法为构造器和伪构造器（克隆，读取对象）所调用。该方法不会增大table或者检查更改等。它调用createEntry而不是addEntry方法。
    private void putForCreate(K key, V value) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);

        // 查找已存在的与该键对应的映射。这不会在克隆或反序列化时发生。仅仅会在输入的Map是可排序的且排序可变的情况下发生。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }

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

    // 遍历输入Map中的所有映射，依次调用putForCreate方法
    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());
        }
    }

    // 将指定映射的所有映射关系复制到此映射中，这些映射关系将替换此映射目前针对指定映射中所有键的所有映射关系。
    public void putAll(Map<? extends K, ? extends V> m) {
        int numKeysToBeAdded = m.size();
        if (numKeysToBeAdded == 0)
            return;


        if (numKeysToBeAdded > threshold) {
            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
            if (targetCapacity > MAXIMUM_CAPACITY)
                targetCapacity = MAXIMUM_CAPACITY;
            int newCapacity = table.length;
            while (newCapacity < targetCapacity)
                newCapacity <<= 1;
            if (newCapacity > table.length)
                resize(newCapacity);
        }

        for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
            Map.Entry<? extends K, ? extends V> e = i.next();
            put(e.getKey(), e.getValue());
        }
    }
}

    // 用键、值、哈希码创建一个新的映射到数组指定的位置。根据需要来扩容。
    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

    // 和addEntry方法类似。主要用于克隆、反序列化等伪构造操作中，不用考虑扩容问题。
    void createEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        size++;
    }

4. 扩容

    // 重新计算该Map元素的哈希值并把元素存放到更大容量的数组中。当键的数量达到阀值时该方法自动调用。
    // 如果当前容量已经是最大值，该方法不会增大容量，而是将阀值设置为Integer.MAX_VALUE，这样该方法就不会被后续调用。
    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);
    }

    // 把所有的映射从当前数组转移到新的数组中
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null; // 原始数组的该位置赋为null
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); // 重新计算位置
                    e.next = newTable[i]; // 早加入的映射放到链表的尾端
                    newTable[i] = e; // 新的映射加入到链表的首端
                    e = next; // 处理下一个映射
                } while (e != null);
            }
        }
    }

5. 删除

    // 从hashmap中删除指定键的映射
    // 返回被删除映射的值（null值有两种可能：没有找到指定键的映射；该映射的值为null)
    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    final Entry<K,V> removeEntryForKey(Object key) {
        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;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) { // 键的哈希值和键都相等
                modCount++;
                size--;
                if (prev == e) // 链表的第一个元素(table[i])符合要求
                    table[i] = next; // 链表的第二个元素变成第一个
                else
                    prev.next = next; // 把e从链表中删除，前后元素关联
                e.recordRemoval(this);
                return e;
            }
            prev = e; // 当前元素作为前一个元素
            e = next; // 下一个元素作为当前元素。这两句相当于指针往后移动一位
        }

        return e;
    }

    // 处理流程和removeEntryForKey类似，虽然传入的是键值对对象，遍历还是根据键来的
    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();
        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;
            if (e.hash == hash && e.equals(entry)) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

    // 清除所有的键值对，大小变为0
    public void clear() {
        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = null;
        size = 0;
    }