HashMap源码分析

此源码分析JDK版本为1.7，只是简单分析，算是个人看源码的一点小总结，随意性比较强，专业的还需百度。
先简单介绍一下HashMap，HashMap数据结构为数组加链表，时间复杂度为O(1)(最理想状态下)。HashMap源码中，需要推敲的代码非常的多，个人觉得比ArrayList、LinkedList等要有营养很多。个人觉得HashMap最主要关注的几个点：1.put()方法，2.hash()方法，3.size设置。关于hash()和size设置推荐一个博客可了解一下：深入理解HashMap（及hash函数的真正巧妙之处）
#简介

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

#属性

//默认初始化长度16(可推敲一下为何为16)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认扩容系数
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//空表实例
static final Entry<?,?>[] EMPTY_TABLE = {};
//数据数组(存放Entry的数组)
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//map大小
transient int size;
//map阈值(到达该阈值扩容)
int threshold;
//扩容系数
final float loadFactor;
//修改次数
transient int modCount;
//默认的hash阈值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
transient int hashSeed = 0;

#构造方法

//根据初始化长度和扩容系数创建HashMap
public HashMap(int initialCapacity, float loadFactor) {
    //如果初始化长度小于0抛异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //如果初始化长度超过默认最大长度则设置初始化为默认最大长度
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //如果扩容系数小于等于0或者扩容系数不是一个合法的数字抛异常(比如参数为:0.0/0.0)
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    //设置扩容系数
    this.loadFactor = loadFactor;
    //设置初始容量
    threshold = initialCapacity;
    //初始化(方法为空)
    init();
}
//创建初始化的的HashMap
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//创建默认HashMap
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//创建一个新的Map，将m的键值对放入
public HashMap(Map<? extends K, ? extends V> m) {
    //初始化长度和默认扩容因子的HashMap(根据默认的扩容因子计算是否小于默认大小，小于则按照默认大小)
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    //
    inflateTable(threshold);

    putAllForCreate(m);
    }

#方法

//返回格式化后大小
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    //如果传入的值大于最大值，则返回最大值
    //如果传入的的值大于1，则返回返回其对应的2的n次方值(Integer.highestOneBit(i))
    //否则则返回1
    return number >= MAXIMUM_CAPACITY
            ? MAXIMUM_CAPACITY
            : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
//
private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    //获取map大小
    int capacity = roundUpToPowerOf2(toSize);
    //获取map阈值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    //新建数组
    table = new Entry[capacity];
    //初始化HashSeed
    initHashSeedAsNeeded(capacity);
}
//初始化HashSeed(每次扩容时会使用)
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;
}
//hash实现
final int hash(Object k) {
    int h = hashSeed;
    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).
    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";
    return h & (length-1);
}
//获取大小(真实数据的大小，非数组长度)
public int size() {
    return size;
}
//判断大小是否为空
public boolean isEmpty() {
    return size == 0;
}
//根据key获取值
public V get(Object key) {
    //如果key为null，则根据null去获取值
    if (key == null)
        return getForNullKey();
    //key不为null则根据key获取Entry
    Entry<K,V> entry = getEntry(key);
    //根据entry是否为null获取值
    return null == entry ? null : entry.getValue();
}
//根据key为null获取值
private V getForNullKey() {
    //如果size为0则直接返回null
    if (size == 0) {
        return null;
    }
    //因为key为null直接放在数组第一个位置，因此遍历数组第一个下得Entry链表即可
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    //如果没有则返回null
    return null;
}
//根据key获取Entry
final Entry<K,V> getEntry(Object key) {
    //如果size为0则直接返回null
    if (size == 0) {
        return null;
    }
    //根据key是否等于null获取key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //根据hash值来获取该key对应的数组下标，遍历该下标下对应的链表
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        //如果hash值相等并且(key地址相同或者key相等)则返回
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    //说明并没有该值返回null
    return null;
}
//是否包含键key
public boolean containsKey(Object key) {
    //根据key获取Entry是否为null
    return getEntry(key) != null;
}
//放入键值对
public V put(K key, V value) {
    //如果数组为空则初始化数组
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //如果key为null则根据key为null放入
    if (key == null)
        return putForNullKey(value);
    //获取key所对应的hash值
    int hash = hash(key);
    //获取该key所对应的hash值所对应数组的下标
    int i = indexFor(hash, table.length);
    //遍历该数组下标的链表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //如果该key已经存在，则覆盖旧值并返回
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            //该方法为空，未知此方法干什么用
            e.recordAccess(this);
            return oldValue;
        }
    }
    //修改次数增加
    modCount++;
    //到此步则说明没有改key，则新增Entry
    addEntry(hash, key, value, i);
    //新增Entry返回null
    return null;
}
//放入Map
public void putAll(Map<? extends K, ? extends V> m) {
    //获取m的大小
    int numKeysToBeAdded = m.size();
    //如果size为0则直接返回
    if (numKeysToBeAdded == 0)
        return;
    //如果当前数组为空则扩容
    if (table == EMPTY_TABLE) {
        inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
    }
    //如果放入的m的size超过当前map的阈值则初始化
    if (numKeysToBeAdded > threshold) {
        //计算m扩容后的大小
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        //计算当前数组扩容后的大小
        int newCapacity = table.length;
        //循环扩大(a<<=1 等价于 a = a << 1)
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        if (newCapacity > table.length)
            resize(newCapacity);
    }
    //遍历m将entry放入当前map
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}
//新增Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果size大于等与扩容阈值并且该下标不为空
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //扩容
        resize(2 * table.length);
        //重新hash
        hash = (null != key) ? hash(key) : 0;
        //获取该hash对应的下标
        bucketIndex = indexFor(hash, table.length);
    }
    创建Entry
    createEntry(hash, key, value, bucketIndex);
}
//创建Entry
void createEntry(int hash, K key, V value, int bucketIndex) {
    //获取该下标下的第一个Entry
    Entry<K,V> e = table[bucketIndex];
    //将新建的Entry放至该数组下链表第一个(新Entry的next指向就得Entry)
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    //size+1
    size++;
}
//扩容
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, initHashSeedAsNeeded(newCapacity));
    //将table地址指向新的地址
    table = newTable;
    //设置扩容阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//转换
void transfer(Entry[] newTable, boolean rehash) {
    //定义数组长度
    int newCapacity = newTable.length;
    //遍历数组Entry
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            //如果重新hash则需要重新设置e的hash值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //根据e的hash值获取e的新的下标
            int i = indexFor(e.hash, newCapacity);
            //将下标为i的Entry赋予为当前Entry的next
            e.next = newTable[i];
            //将当前Entry赋予newTable的i下标(因为上一步已经将之前的Entry赋予为当前的next，所以直接将引用指向新的即可)
            newTable[i] = e;
            //将下一个Entry赋予为e继续循环
            e = next;
        }
    }
}
//根据key移除元素
public V remove(Object key) {
    //根据key移除元素
    Entry<K,V> e = removeEntryForKey(key);
    //返回值
    return (e == null ? null : e.value);
}
//根据key移除Entry
final Entry<K,V> removeEntryForKey(Object key) {
    //如果当前大小为0则返回null
    if (size == 0) {
        return null;
    }
    //获取key的hash值
    int hash = (key == null) ? 0 : hash(key);
    //根据key的hash值返回下标
    int i = indexFor(hash, table.length);
    //获取当前下标的Entry
    Entry<K,V> prev = table[i];
    //将当前下标的Entry赋予给e
    Entry<K,V> e = prev;
    //循环判断
    while (e != null) {
        //获取当前Entry的下一个Entry
        Entry<K,V> next = e.next;
        //定义临时变量k
        Object k;
        //如果当前Entry的hash值和key的hash值相同并且(当前Entry的key和key地址相同或者值相同)则进入
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            //修改次数+1
            modCount++;
            //大小-1
            size--;
            //如果prev为当前Entry则说明该Entry是链表第一个元素，则直接将第一个元素指向该Entry的next即可
            if (prev == e)
                table[i] = next;
            else
                //如果不是链表的第一个元素则将当前元素上一个元素的next指向当前元素的下一个元素即可
                prev.next = next;
            //未知该代码什么作用(代码内容为空)
           e.recordRemoval(this);
            //返回旧值
            return e;
        }
        //如果当前元素并不是要删除的元素则将当前元素赋予上一个元素prev，将下一个元素指向当前元素e，继续循环
        prev = e;
        e = next;
    }
    //走到这一步说明没有该元素，此时e已经为null，返回
    return e;
}
//删除Entry
final Entry<K,V> removeMapping(Object o) {
    //如果当前map大小为0或者不是MapEntry类型则返回null
    if (size == 0 || !(o instanceof Map.Entry))
        return null;
    //强转为Map.Entry类型
    Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
    //获取key
    Object key = entry.getKey();
    //下方代码和removeEntryForKey一致除了该判断是判断entry的hash和值(个人觉得完全可以在此调用根据key删除)
    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;
        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;
}
//清空map
public void clear() {
    //修改次数+1
    modCount++;
    //调用工具类(内部实现为遍历数组，将数组每个下标的元素指向null，此时扩容阈值threshold还是旧的)
    Arrays.fill(table, null);
    //设置大小为0
    size = 0;
}
//是否包含值
public boolean containsValue(Object value) {
    //如果值为null则调用是否包含空值方法
    if (value == null)
        return containsNullValue();
    //定义临时变量指向当前数组
    Entry[] tab = table;
    //遍历数组
    for (int i = 0; i < tab.length ; i++)
        //遍历当前Entry链表
        for (Entry e = tab[i] ; e != null ; e = e.next)
            //如果相同则返回true
            if (value.equals(e.value))
                return true;
    //说明不好看此值
    return false;
}
//是否包含空值(私有)
private boolean containsNullValue() {
    //方法体和判断值相同，只不过是判断是否为null
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (e.value == null)
                return true;
    return false;
}
//克隆
public Object clone() {
    HashMap<K,V> result = null;
    try {
        调用Object的克隆方法(浅克隆)
        result = (HashMap<K,V>)super.clone();
    } catch (CloneNotSupportedException e) {
        // assert false;
    }
    if (result.table != EMPTY_TABLE) {
        //刷新HashSeed
        result.inflateTable(Math.min(
            (int) Math.min(
                size * Math.min(1 / loadFactor, 4.0f),
                // we have limits...
                HashMap.MAXIMUM_CAPACITY),
           table.length));
    }
    //以下类似于初始化
    result.entrySet = null;
    result.modCount = 0;
    result.size = 0;
    result.init();
    //此处将旧的数据放入克隆之后的result
    result.putAllForCreate(this);
    //返回result
    return result;
}
//tag:Entry比较简单，代码量也少，就不分析了

#总结

1.获取值是先计算其hash值，再根据其hash值获取数组下标，然后遍历该下标对应的链表去取值
2.放入键值对则是先计算key的hash值，根据hash值获取数组下标，遍历查看是否有其对应的值，有则覆盖，没有则新增Entry
3.新增Entry时会先判断是否需要扩容，再创建Entry。创建Entry只需要将新的Entry放置该数组位置，将next指向旧的头节点
4.扩容是两倍扩容，根据是否重新hash而决定是否更改Entry的hash值，然后遍历获取新的数组下标将旧数据放置新的数组中，再将旧的数组指向新的数组