HashMap源码解析

属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认初始化容量，1左移4位，也就是16

static final int MAXIMUM_CAPACITY = 1 << 30;
最大容量，1左移30位，最大值小于等于这个值

static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认加载因子，加载因子是用来确认hashmap容量在使用多少时进行扩容的值，默认是3/4

static final Entry<?,?>[] EMPTY_TABLE = {};
空Entry表，Entry就是HashMap的每一个键值对的保存实体对象

transient int size;
记录hashmap中真实保存的键值对数量

int threshold;
阈值，map内扩容的界定值

方法

构造方法

/**
 * 设置初始容量和加载因子
 * 未指定时使用默认值
* 在此方法中，只是初始化了容量和加载因子两个值，实际上，这个时候的Entry[]还是一个空的{}，实际要用到map的时候还是需要去给这个数组定义长度的
 */
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;
    //校验负载因子合法
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

    this.loadFactor = loadFactor;
    //在(int,int)的构造里面阈值设置的是初始容量，是因为在膨胀表的时候还会再对阈值进行处理
    threshold = initialCapacity;
    //初始化方法，用于继承时重写，自定义构造
    init();
    }

/**
* 传入Map作为入参的构造，会将入参map的全部entry转入当前的hashMap中
*/
public HashMap(Map<? extends K, ? extends V> m) {
    //调用构造(int,int)
    //将map的实际数量除以默认加载因子，得到计算的值之后与默认初始容量16比较，取两个值中间的最大值作为初始容量
    //使用默认的加载因子0.75
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
            DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    //扩容数组
    inflateTable(threshold);
    //插入map的全部值
    putAllForCreate(m);
}
/**
* 膨胀数组空间
* hashMap是延迟初始化，在put的时候才会真正去申请数组空间
*/
private void inflateTable(int toSize) {
    //取到实际要初始化的数组大小
    int capacity = roundUpToPowerOf2(toSize);
    //设置阈值是：容量*加载因子 和 `MAXIMUM_CAPACITY` 中的最小值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    //申请数组空间
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
/**
* 将一个int值向上取2的倍数，最大为 MAXIMUM_CAPACITY
* 比如：入参9，反参16; 入参8,反参8
*/
private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
/**
* 循环插入
*/
private void putAllForCreate(Map<? extends K, ? extends V> m) {
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            putForCreate(e.getKey(), e.getValue());
}
/**
* 创建时插入，这个方法只会被构造器调用
* 因为构造器中已经初始扩容，不需要考虑容量到达阈值的问题
*/
private void putForCreate(K key, V value) {
    // 计算k的hash值，如果k是null，则hash为0
    int hash = null == key ? 0 : hash(key);
    // 计算这个k在数组中的桶下标
    int i = indexFor(hash, table.length);
    //循环桶内的链表，判断是否存在相同的k
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //只有当两个hash值相等 且( k == entry.key 或者 k.equals(entry.key) )的时候
        //认定k相同
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            e.value = value;
            return;
        }
    }
    //没有相同的k，插入新的entry
    createEntry(hash, key, value, i);
}
/**
* 计算下标
* 在这个方法中表明了为什么hashMap的容量（也就是Entry[]数组的length）一定是2的倍数
* 通过与运算可以直接根据k的hash获取数组的下标
*/
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);
}
/**
* 创建entry
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    //将原来的entry作为新entry.next，证明HashMap是头插
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    //实际存储entry数量+1
    size++;
}
/**
* 计算hash值，使用到了k的hashCode
*/
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);
    }

put方法

/**
* 插入键值对
*/
public V put(K key, V value) {
    //如果数组是空数组，初始化表
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //k == null ，插入null键的键值对
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    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);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
/**
* 插入空键的值
*/
private V putForNullKey(V value) {
    //循环下标为0的桶，因为null的hash为0，调用indexFor永远返回0,即null永远在0号桶内
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        //如果存在null的k，替换
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            //替换参数后执行的钩子方法
            e.recordAccess(this);
            return oldValue;
        }
    }
    //结构变化次数+1，注意如果是替换并不会修改这个值
    modCount++;
    //新增实体，hash=0,bucketIndex=0
    addEntry(0, null, value, 0);
    return null;
}
/**
* 增加实体，插入前先判断是否需要扩容
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果当前的实际容量大于等于阈值
    // 且 想要插入的桶不为空 这个判断是提高哈希表的负载，如果桶为空，那么直接插入桶中，并不会影响到后续的查询效率
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //扩容、将数据从老table转入新table
        resize(2 * table.length);
        //重新计算插入k的hash
        hash = (null != key) ? hash(key) : 0;
        //重新计算插入k的桶下表
        bucketIndex = indexFor(hash, table.length);
    }
    //创建实体，上面有这个方法的具体实现
    createEntry(hash, key, value, bucketIndex);
}
/**
* 重哈希
*/
void resize(int newCapacity) {
    //保存老表的引用和长度
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //如果当前的容量已经到达了最大值，不会再扩容
    //但是会把阈值设置成int的最大值
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //创建一个新容量的数组，申请内存
    Entry[] newTable = new Entry[newCapacity];
    //移动老数据到新table中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //将table指向新表
    table = newTable;
    //重新计算阈值，仍然保持不超过MAXIMUM_CAPACITY
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
* 从当前表转移数据到新表中
*/
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //循环老表的数据，将每一个桶内的链表数据循环插入到新表中
    for (Entry<K,V> e : table) {
        while(null != e) {
            //保留指向链表下一单位的指针，因为将entry插入新桶中的时候会替换掉e.next
            Entry<K,V> next = e.next;
            //如果需要重哈希
            if (rehash) {
                //重新设置hash，null-key的hash仍然=0
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //获取在新数组中的桶下标
            int i = indexFor(e.hash, newCapacity);
            //将指定下标下的对象保留在当前实体的next中，替换桶中的指针
            //头插
            e.next = newTable[i];
            newTable[i] = e;
            //将entry的next指给e，继续e的循环
            e = next;
        }
    }    
}

get方法

/**
* 获取对象
*/
public V get(Object key) {
    //如果k是null，调用获取null方法
    if (key == null)
        return getForNullKey();
    //调用获取entry方法
    Entry<K,V> entry = getEntry(key);
    //如果entry不存在，返回null，否则返回entry.value
    return null == entry ? null : entry.getValue();
}
/**
* 获取null-key的值
*/
private V getForNullKey() {
    //表实际容量=0，返回null
    if (size == 0) {
        return null;
    }
    //循环桶[0],找到k=null，返回value
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    //不存在null键的entry
    return null;
}
/**
* 根据key获取实体
*/
final Entry<K,V> getEntry(Object key) {
    //表实际容量=0，返回null
    if (size == 0) {
        return null;
    }
    //计算hash，k=null时hash为0
    int hash = (key == null) ? 0 : hash(key);
    //循环hash所在的下标桶
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
        e = e.next) {
        Object k;
        //如果key存在，返回entry
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    //不存在，返回null
    return null;
}

常用方法

/**
* 清空表
* 结构修改次数+1,将table每一格设置为null
*/
public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}
/**
* 获取表实际容量
*/
public int size() {
    return size;
}
/**
* 是否为空表
*/
public boolean isEmpty() {
    return size == 0;
}
/**
* 将指定Map中的键值对复制到此Map中
*/ 
public void putAll(Map<? extends K, ? extends V> m) {  
    //统计需复制多少个键值对  
    int numKeysToBeAdded = m.size();  
    if (numKeysToBeAdded == 0)  
        return; 

    //若table还没初始化，先用刚刚统计的复制数去膨胀初始化table  
    if (table == EMPTY_TABLE) {  
        inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));  
    }  

    //若需复制的数目 > 阈值，则需先扩容 
    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);  
    }  
    //开始复制，实际上不断调用Put函数插入  
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
        put(e.getKey(), e.getValue());
}
/**
* 根据key删除某个entry，返回删除key的value
*/
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}
/**
* 根据key删除某个entry
*/
final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    // 1. 计算hash值
    int hash = (key == null) ? 0 : hash(key);  
    // 2. 计算存储的数组下标位置
    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--; 
            // 若删除的是table数组中的元素（即链表的头结点） 
            // 则删除操作 = 将头结点的next引用存入table[i]中  
            if (prev == e) 
                table[i] = next;

            //否则 将以table[i]为头结点的链表中，当前Entry的前1个Entry中的next 设置为 当前Entry的next（即删除当前Entry = 直接跳过当前Entry）
            else  
                prev.next = next;   
            e.recordRemoval(this);  
            return e;  
        }  
        prev = e;  
        e = next;  
    }

    return e;
}
/**
* 判断是否存在该键的键值对
*/
public boolean containsKey(Object key) {  
    return getEntry(key) != null; 
}

1.7和1.8的区别

JDK 1.8 的优化目的主要是：减少 Hash冲突 & 提高哈希表的存、取效率。
对于1.7中如果链表过长，导致实际查询效率下降的问题，1.8引入了红黑树来解决。
默认：在链表长度大于8进化成红黑树，扩容时重新计算后的树数量小于6退化成链表
１.8采用了尾插。

HashMap如何解决Hash冲突

1. hash算法

• 扰动处理，7中9次（4次移位5次异或），8中2次（1次移位1次异或）

2. hashCode

• hashTable使用hashCode作为key的哈希值

HashMap特点

1. 键值都允许为null

• hashmap将null的hash认为0
• hashTable使用hashCode作为hash，所以null无法调用hashCode()方法，故无法插入

2. 线程不安全

• 无同步锁
• 1.7中resize()方法多线程场景可能会出现链表成环

3. 不保证有序，也不保证顺序不变

• 采用k的哈希值作为存储桶下标
• 扩容时的重哈希，会重新计算桶下标，移动entry位置

为什么推荐使用String、Integer这种包装类作为key？

• 包装类和String都是final，保证hash不可更改
• 内部重写了equals()和hashCode()方法，有效减少hash碰撞

若key为自定义对象类，应该实现什么方法？

• hashCode()
  计算存储数据的存储位置
• equals()
  比较是否为同一个key值时会调用这个方法

链表成环

• 高并发下，两个线程同时对一个hashMap进行resize()，有可能出现newTable[i].next=newTable[i]
  一旦出现这种结果，就回导致查询时陷入死循环，而导致CPU进入100%。
• 7中使用尾插入会导致这种现象，8中变化为头插，可以大程度避免成环的现象。