Java源码解析之HashMap

public class HashMap<K,V>
    extends AbstractMap<K,V>
     implements Map<K,V>, Cloneable, Serializable
{}

//默认的初始化容量，必须是2的的次方数，默认是16；在初始化HashMap没有指定容量时使用
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量2^30，用于table数组，下面做的说明大家不要和size混淆
//我们知道int是32位的，最大正整数是2^31-1，
//另外我们分析源码会发现在resize的时候将阈值设为了Integer.MAX_VALUE，即2^31-1
//所以HashMap实际用到的最大size为2^31-1
static final int MAXIMUM_CAPACITY = 1 << 30;

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

//空数组，被所有HashMap共享，一般只是作为table的默认值
static final Entry<?,?>[] EMPTY_TABLE = {};

//用于存储HashMap中的桶，长度总是2的次方数，会在第一次put的时候分配内存
//transient表明序列化的时候table不会序列化
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//size表示HashMap中存储的映射个数
transient int size;

//HashMap实际使用的阈值变量
//一开始这个值是默认的阈值，
//但是当分配table内存是，值为容量*装载因子，即(capacity * load factor)
int threshold;

//装载因子，用以表示table装满程度
//当没有指明装载因子时使用DEFAULT_LOAD_FACTOR
final float loadFactor;

//用以记录HashMap自创建以来结构发生变化的次数
//结构发生变化指：1.增加映射， 2.移除映射， 3.rehash
//这个值会使由这个HashMap得到的迭代器(iterators)快速失败(fail-fast)
//因为在生成迭代器的时候复制了一份modCount当时的值，如果在这之后HashMap发生了结构变化，
//那么这个迭代器中的值就不等于modCount，迭代器就抛出ConcurrentModificationException
//但是通过这个迭代器去改变HashMap的结构是可以的
transient int modCount;

//可选哈希阈值默认值2^31-1
//目的是为了减少String键值的弱哈希计算的冲突
//JVM首先读取系统属性jdk.map.althashing.threshold，
//值为-1时，禁用该值；值为小于0时，抛出异常;值为正则启用可选哈希
//源码分析时会进一步讲解
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//哈希种子，在分配table存储时会计算该值
transient int hashSeed = 0;

//存储映射的Set变量
private transient Set<Map.Entry<K,V>> entrySet = null;

/**
 * 通过容量和装载因子初始化HashMap
 */
public HashMap(int initialCapacity, float loadFactor) {
        //以下对容量值进行检查，确保在(0, MAXIMUM_CAPACITY]之间
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //以下对装载因子进行检查，要求是正的Float数字
        //思考装载因子并没有限制在小于1的范围内，可见可以是大于1的数字，只是这个时候再也反映不出
        //table的装满程度，同时put的冲突几率将增高，装载因子失去设计时的意义
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        threshold = initialCapacity; //初始阈值为容量值
        /**
         * HashMap中此init方法的方法体是空的，子类有需要可以实现，
         * 主要是为了执行子类的钩子，用的是模板方法设计模式
         * 这个方法总是在构造方法的最后一步执行，伪构造方法(clone,readObject)也会调用执行
         */
        init(); /
}

/**
 * 使用容量和默认的装载因子初始化HashMap
 */
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 使用默认的容量和装载因子初始化HashMap
 */
public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

/**
 * 调用处是在虚拟机启动好之后
 */
private static class Holder {
        static final int ALTERNATIVE_HASHING_THRESHOLD;

        static {
            //获得系统属性jdk.map.althashing.threshold
            //此种方式调用时不进行安全检查，doPrivileged里面的代码享有特权
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold"));

            int threshold;
            try {
                //当系统属性值有被设置，那么获得该值，否者使用可选哈希阈值默认值
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;

                //如果系统属性设置为-1，则赋予Integer最大正整数
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }

                //小于0，抛出异常
                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for ‘jdk.map.althashing.threshold‘", failed);
            }

           //最后存储为可选哈希值
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
}

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key; //键值，注意这里key是final的，说明一旦赋值不允许修改，强调key值设计原则
        V value; //映射值
        Entry<K,V> next; //关联的下一个Enrty引用
        int hash; //哈希码

        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry)o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        public final int hashCode() {
            return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
        }

        public final String toString() {
            return getKey() + "=" + getValue();
        }

        /**
         * 此方法被调用，当已存在的Entry中的value被修改的时候
         * 子类需要实现
         */
        void recordAccess(HashMap<K,V> m) {
        }

        /**
         * 此方法被调用，当这个Entry被移除
         * 子类需要实现
         */
        void recordRemoval(HashMap<K,V> m) {
        }
}

/**
 * 迭代器实现抽象类，只有next()未实现，留待子类实现
 */
private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;        // 下一个entry
        int expectedModCount;   // 用于快速失败机制
        int index;               // 桶的位置索引
        Entry<K,V> current;     // 当前entry

        HashIterator() {
            expectedModCount = modCount; //赋予当时HashMap的modCount值
            if (size > 0) {
                Entry[] t = table;
                //找到table数组中按序不为null的那个桶
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

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

        final Entry<K,V> nextEntry() {
            //这句很重要，当生成迭代器后，HashMap结构发生了变化，则迅速失败
            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;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
           //这句很重要，当生成迭代器后，HashMap结构发生了变化，则迅速失败
           if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            //移除后要更新expectedModCount，否者再次调用会迅速失败
            expectedModCount = modCount;
        }
}

private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
 }

private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey(); //强调key值设计理念
        }
}

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
}

/**
 * 用于生成key的set集合，所有方法都委托给HashMap的方法
 */
private final class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
            return newKeyIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsKey(o);
        }
        public boolean remove(Object o) {
            return HashMap.this.removeEntryForKey(o) != null;
        }
        public void clear() {
            HashMap.this.clear();
        }
}

/**
 * 用于生成value集合，所有方法都委托给HashMap的方法
 */
private final class Values extends AbstractCollection<V> {
        public Iterator<V> iterator() {
            return newValueIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsValue(o);
        }
        public void clear() {
            HashMap.this.clear();
        }
}

/**
 * 用于生成entry的set集合，所有方法实现都委托给HashMap的方法
 */
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            return newEntryIterator();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;
            Entry<K,V> candidate = getEntry(e.getKey());
            return candidate != null && candidate.equals(e);
        }
        public boolean remove(Object o) {
            return removeMapping(o) != null;
        }
        public int size() {
            return size;
        }
        public void clear() {
            HashMap.this.clear();
        }
}

/**
 * 将键值key与映射值value组成一个映射存储在HashMap中
 * 允许key为null，因为key唯一，所以最多有一个这样的映射
 * 允许有多个value为null的映射，但是key不同
 */
public V put(K key, V value) {
        //在第一次put的时候会检查到table为空并初始化
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //如果key为null就调用专用的方法进行put，然后返回
        if (key == null)
            return putForNullKey(value);
        //根据键值key进行哈希计算得到哈希码
        int hash = hash(key);
        //根据哈希码计算应当将该映射放在table的哪个索引链表下
        int i = indexFor(hash, table.length);
        //遍历第i个链表查找是否存在于key相同的entry，存在则替换entry的value值并返回旧的value值
        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); //put替换存在的entry的value值须调用，子类实现的方法
                return oldValue;
            }
        }

        //如果不存在为key的entry，则添加新的entry到HashMap中
        //因为HashMap结构发生变化，则modCount加1
        //返回null
        modCount++;
        addEntry(hash, key, value, i);
        return null;
}

/**
 * put键值key为null的时候调用的方法
 * 直接在table的第0个索引的链表上查找替换或添加 
 */
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;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
}

/**
 * 在table的第bucketIndex个链表上添加哈希码为hash，键值为key，映射值为value的entry
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
        //首先检查HashMap的size是否已经到达或者大于阈值，并且第bucketIndex个索引的链表不为null
        //那么HashMap需要rehash尝试申请更多table空间，注意是尝试，不一定能分配到的
        //同时我们也能知道如果第bucketIndex个索引的链表为null，即时超过阈值也不会去申请空间
        //注意size指的是HashMap实际的entry数量，threshold是table的装满程度的具体阈值
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length); //尝试请求申请当前table长度的2倍空间
            //重新计算put映射的key的哈希码
            //因为这个方法是给所有key的添加使用的，所以要考虑可以为null的情况
            hash = (null != key) ? hash(key) : 0;
            //重新计算put的映射应该放在申请新空间后的table的哪个索引链表上
            bucketIndex = indexFor(hash, table.length);
        }
        
        //创建Entry对象，并插入到第bucketIndex个索引链表的第一个位置
        createEntry(hash, key, value, bucketIndex);
}

/**
 * 创建Entry对象，并插入到第bucketIndex个索引链表的第一个位置，size加1
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
}

/**
 * 获取HashMap中键值为key的entry的value值
 * 如果返回null，有可能存储的value就是null，也有可能没有key对应entry，需要结合containsKey检查
 */
public V get(Object key) {
        if (key == null)
            return getForNullKey();  //key为null，调用专用方法
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        //直接到table的第0个索引链表下查找
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
}

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

        //首先根据key计算哈希码，然后根据哈希码找到table下的索引链表，最后查找
        int hash = (key == null) ? 0 : hash(key);
        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;
}

/**
 * 从HashMap中移除键值为key的entry，并且返回对应的value值
 */
public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
}

final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        //首先根据key计算哈希码，然后根据哈希码找到table下的索引链表 
        int hash = (key == null) ? 0 : hash(key);
        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;
            //找到该key对应的entry
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
               //结构该表，计数加1；同时HashMap大小减一
                modCount++;
                size--;
                //如果移除的是table索引的第一个entry，则直接修改table[i]
                if (prev == e)
                    table[i] = next;
                //不是第一个entry，则将移除entry的前一个entry的next指向移除entry的next
                else
                    prev.next = next;
                //记录移除的entry
                e.recordRemoval(this);
                return e;
            }
            //顺序后移，再次循环
            prev = e;
            e = next;
        }

        //返回移除的entry
        return e;
}

/**
 * 在HashMap使用之前需要做一次膨化处理
 */
private void inflateTable(int toSize) {
        //找到大于等于toSize且是2的次方数的最小数
        //所以我们需要知道table数组的长度一定是2的次方数
        int capacity = roundUpToPowerOf2(toSize);

        //计算阈值
        //取二者中较小的那个
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        //初始化哈希种子
        initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

/**
 * 初始化hashSeed，但是貌似hashSeed一直是0，不知道其中缘由
 */
final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;
        boolean useAltHashing = sun.misc.VM.isBooted() &&  //检查虚拟机是否已启动
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean switching = currentAltHashing ^ useAltHashing;
        if (switching) {
            hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)  //生成随机种子
                : 0;
        }
        return switching;
}

final int hash(Object k) {
        int h = hashSeed;
        //当哈希种子不为0且k是String时调用特殊的哈希算法
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        // 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).
        // 下面的方法可以使在table每个位置的冲突次数都是一个常数值，在装载因子为0.75的时候为8
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        // 因为table的length总是2的次方数，所以下面的方法是对h在length上做模运算
        // 比如50 % 16 = 2 = 000010 = 110010 & 001111
        return h & (length-1);
}

/**
 * resize table的大小
 */
void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //如果容量已经到达最大容量值，就将阈值设为Integer最大值，返回
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        //将当前table内容转换到新的容量table中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/**
 * 将旧table中的entry转化到新table中去，rehash指明是否需要重新计算哈希码
 */
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;
            }
        }
}