Touch Source of HashMap (1)


 

Touch Source of HashMap (1)

基于JDK1.7的HashMap源码阅读

概述

  • 横向维护一个Entry数组,用来存放最近一次添加的(key,value)形式的元素
  • 每个数组元素纵向维护一个Entry链表,当发生哈希冲突时,将原先的Entry往后挪,即链地址法解决哈希冲突

img

方法签名

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

具有Map的基本方法,可克隆、可序列化(自定义的序列化规则)

基本属性

// 默认容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子,值为0.75,扩容时用
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空的入口数组
static final Entry<?,?>[] EMPTY_TABLE = {};
/**
 * 入口数组,用来存储链表的头结点
 * 一开始将它指向 EMPTY_TABLE,这样的意图直到在第一次添加元素时
 * 才正式将table指向大小接近threshold的Entry对象
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 当前表中的元素个数
transient int size;
/**
 * 阈值,超过后扩容,值为capacity * load factor
 * 一开始table为 EMPTY_TABLE,即创建HashMap对象但未往其中添加元素,
 * 当第一次往其中添加元素时,表的大小会膨胀到这个值
 */
int threshold;
// 加载因子
final float loadFactor;
// 结构性修改的次数,与fail-fast机制有关
transient int modCount;

构造方法

1. 无参构造

实际上相当于new HashMap(16, 0.75)

public HashMap() {
    // 用默认的容量和加载因子构建
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

2. 初始容量和加载因子构造

核心构造器,其他三个构造都会调用这个构造器,只是传递的参数不一样而已

/**
 * 用初始容量和加载因子构造HashMap
 * 如果初始容量为负数或者加载因子非正数抛出异常
 */
public HashMap(int initialCapacity, float loadFactor) {
    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;
    /**
     *	将阈值设定为初始容量
     *  注:此处不是真正的阈值,是为了扩展哈希表,该阈值后面会重新计算,
     */
    threshold = initialCapacity;
    // 一个空方法用于未来的子对象扩展
    init();
}

/**
 * 给子类造的初始化钩子,在HashMap初始化了但是没有任何entries插入
 * 前,该方法会在所有的构造方法或者构造前预处理方法(如clone,readObject)
 * 中被调用,没有方法的话readObject方法需要子类明确的定义
 */
void init() {
}

3. 用初始容量构造

用给定的容量和默认的加载因子(0.75)构造一个空的 HashMap,相当于new HashMap(initialCapacity, 0.75)

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

4. 用Map实现类构造

用给定的Map实现类对象的键值对数据构造一个新的HashMap,该HashMap将用默认的加载因子(0.75)和一个足以容纳原来map 中的键值对的容量,如果 map 为空将抛出 NullPointerException

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    // 该方法用于初始化数组和阈值
    inflateTable(threshold);
    // 数据填充
    putAllForCreate(m);
}

足以容纳原来map 中的键值对的容量

初始容量为原来容量的1.3倍加1与默认初始化容量中的较大者(当map大小为0时,最小容量为1),阈值为该初始容量,加载因子为0.75,然后用阈值扩大哈希表

添加元素

  • 计算键的哈希值,通过&运算得到该键值对应该存放在数组中的下标位置(即确定桶下标)
  • 遍历桶寻找键相同的结点,若找到则替换原结点的值并返回,否则直接添加结点
public V put(K key, V value) {
    // 空表,扩充 
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 对于空键特殊处理
    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++;
    // 没有找到键与k相同的键值对,添加新的Entry
    addEntry(hash, key, value, i);
    return null;
}

扩充表

当第一次往HashMap对象中添加元素时调用

private void inflateTable(int toSize) {
	// 计算最接近toSize的符合2的n次幂的容量
	int capacity = roundUpToPowerOf2(toSize);
	// 设置阈值,通常为capacity * loadFactor
	threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 初始化table
	table = new Entry[capacity];
	initHashSeedAsNeeded(capacity);
}

添加结点

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 如果当前 HashMap 大小已经达到了阈值,并且新值要插入的数组位置已经有元素了,那么要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 将容量扩大为原来的两倍
        resize(2 * table.length);
        // 扩容以后,重新计算 hash 值
        hash = (null != key) ? hash(key) : 0;
        // 重新计算扩容后的新的下标
        bucketIndex = indexFor(hash, table.length);
    }
    // 添加结点
    createEntry(hash, key, value, bucketIndex);
}

哈希函数

进行哈希扰动,使得0和1的值变得均匀,减少哈希冲突

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);
}

具体分析见文章XXX

扩容

用一个新的大数组替换原来的小数组,并将原来数组中的值迁移到新的数组中。由于是双倍扩容,迁移过程中,会将原来 table[i] 中的链表的所有节点,分拆到新的数组的 newTable[i] 和 newTable[i + oldLength] 位置上。如原来数组长度是 16,那么扩容后,原来 table[0] 处的链表中的所有元素会被分配到新数组中 newTable[0] 和 newTable[16] 这两个位置,实际上是一个链表结点再散列的过程。

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指向扩容后得到的新的Entry对象
    table = newTable;
    // 计算新的阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

元素迁移

扩容后将酒标中的数据迁移到新表中,注意到该方法的时间复杂度为O(n²)

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放到链表入口
             * 如果没有发生哈希冲突那么newTable[i]即为null,表尾元素的next指针指向null完全合理
             */
            e.next = newTable[i];
            newTable[i] = e;
            // 处理链表中的下一个元素
            e = next;
        }
    }
}

注意

从上面可以看到当HashMap对象的size大于等于阈值(容量 * 加载因子)时,将进行扩容,而所谓的扩容并不是简单的创建一个新的Enrty数组,将原来的所有的链表搬到新的数组中就可以了,这其中涉及到了元素再散列的过程,即遍历每一条链表中每一个元素,通过它们的key和新的容量计算出它们在新表中应该存放的桶下标位置,再将它们添加到相应的桶中,如果不进行再散列过程的话,那么在调用indexFor()方法时由于插入和获取时的入参length值不同,自然获取不到想要的元素。

因而再散列是必须的,但是这将面临的另一个问题是由于再散列涉及了数组和链表的二维遍历,从而带来了O(n²)的时间复杂度,为避免程序性能的下降,建议明确HashMap对象的用途,在初始化时为之选择合适的容量和加载因子,从而人为地避免扩容算法的执行。

获取元素

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

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

获取空键键值对的非空值

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    // 所有键为null的建辉对都存储在table的0号单元所对应的链表中
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

通过key查找非空键的结点

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    // 计算hash值
    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;
}

删除元素

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

根据key删除结点

final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    // 计算哈希值,定位桶
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    // 获取桶口元素
    Entry<K,V> prev = table[i];
    // 复制一份prev指针
    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] = next;
            // 断开要删除的结点
            else
                prev.next = next;
            // 无动作
            e.recordRemoval(this);
            return e;
        }
        // prev指向e所指向的结点的前继
        prev = e;
        e = next;
    }
    return e;
}