[数据结构与算法]HashMap源码分析（JDK1.7）

HashMap的底层结构

JDK7：Entry数组+链表

JDK8：Node数组+链表+红黑树

本文只讨论JDK1.7的HashMap，JDK1.8的HashMap将在另一篇文章中讨论

源码分析

重要属性

// 默认初始化数组长度-16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
// 默认最大数组长度-2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 空tabl
static final Entry<?,?>[] EMPTY_TABLE = {};
// map中维护的Entry数组
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 整个map中的元素个数
transient int size;
// 扩容阈值
int threshold;
// 负载因子，用于计算是否需要扩容
final float loadFactor;
// 整个map的修改次数
transient int modCount;
// ？？？
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
// 与此实例关联的随机化值，应用于密钥的哈希代码，以使哈希冲突更难找到。如果为0，则禁用替代哈希。
transient int hashSeed = 0;

重要方法

// 计算key在整个map中的hash值
final int hash(Object k) {
    int h = hashSeed;	// 默认为0
    // 判断 hashSeed 是否不等于0，并且k不属于字符串
    if (0 != h && k instanceof String) {
        // 调用底层的Hashing方法
        return sun.misc.Hashing.stringHash32((String) k);
    }
    
    // ----------- 不需要用替代hash -----------
    // 减少hash冲突
    h ^= k.hashCode();
    
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

// 传入hash值-h，数组长度-length
// 返回该hash值在数组中对应的位置
static int indexFor(int h, int length) {
    return h & (length-1);
}

// 初始化table
private void inflateTable(int toSize) {
    // 找到大于等于toSize的2的次幂，作为当前容量
    int capacity = roundUpToPowerOf2(toSize);
	
    // 计算阈值
    // 计算方式：(当前容量*负载因子，最大容量+1) 中的最小值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

// 初始化哈希掩码值，在用的时候才进行初始化。
// 一般情况下，都返回false
final boolean initHashSeedAsNeeded(int capacity) {
    // ----------- 重点看switching -----------
    // switching表示是否需要重新计算hashSeed
    
    // currentAltHashing 一般为false
    boolean currentAltHashing = hashSeed != 0;
    // capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD 一定为false，所以 useAltHashing 也为false
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    // currentAltHashing 和 useAltHashing 不同时，switching才为true
    boolean switching = currentAltHashing ^ useAltHashing;
	// 如果switching为true，重新计算hashSeed
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    // 返回是否重新计算了hashSeed
    return switching;
}

resize()方法

// 进行扩容
void resize(int newCapacity) {
    // 用一个局部变量oldTable指向原table
    Entry[] oldTable = table;
    // 原数组的容量（数组长度）
    int oldCapacity = oldTable.length;
    // 判断原数组容量是否已经达到设置的最大值
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 如果是，则将阈值设置为整型最大值，方法结束
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 执行到这里说明原数组容量尚未达到设置的最大值
	// 创建一个新table
    Entry[] newTable = new Entry[newCapacity];
    // 调用transfer方法
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 将新数组复制给原数组
    table = newTable;
    // 重新计算阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

// 重新计算每个节点的hashcode，并将其放在新数组的对应位置
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        // e表示当前节点
        while(null != e) {
            // 存储当前节点e的下一个Entry节点
            Entry<K,V> next = e.next;
            // 判断是否需要rehash，一般都不会进行rehash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            // 当前节点的下一个指向newTable[i]
            e.next = newTable[i];
            // 把当前节点挪如newTable[i]
            newTable[i] = e;
            // 让当前节点e指向next
            e = next;
        }
    }
}

需要注意的是，在多线程环境下进行resize()容易产生死循环问题，具体原因我会在另一篇博客里详细讨论

get()方法

public V get(Object key) {
    // 判断key是否为null
    if (key == null)
        return getForNullKey();
    
    // --------------- key 不为null ---------------
    // 获取entry
    Entry<K,V> entry = getEntry(key);
	// 如果entry不为null，则返回entry中的value，否则返回null
    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    // 判断hashmap是否有元素
    if (size == 0) {
        // 没有元素
        return null;
    }
	
    // -------------- hashmap中有元素 ----------------
    int hash = (key == null) ? 0 : hash(key);
    // 遍历该key对应的hash在table中对应的位置的链表
    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中空值的value
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;
}

put()方法

/*
重要变量
key: 待插入的key
value: 待插入的value
table: 整个HashMap中的Entry数组
hash: 待插入key在这个HashMap中的hash值
modCount: 修改次数
*/
public V put(K key, V value) {
    // 如果table数组为空，则初始化table数组
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果key为null值，则调用特殊的null值处理方法
    if (key == null)
        return putForNullKey(value);
    
	// ------------ key 不为null ---------------
    // 计算key在HashMap中的hash值
    int hash = hash(key);
    // 找到对应hash值在数组table中的位置
    int i = indexFor(hash, table.length);
    // 遍历该位置的链表，也就是遍历该位置的每个Entry节点
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 判断当前遍历到的Entry的hash是否与key的hash相同，并且判断key值是否一致
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            // 如果是，则说明链表中已有key，则进行替换
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            // 返回旧值
            return oldValue;
        }
    }
    
    // ------------ 该位置的链表中没有key ------------
    modCount++;
    // 新增Entry到Map中
    addEntry(hash, key, value, i);
    return null;
}

// 新增Entry到Map中
void addEntry(int hash, K key, V value, int bucketIndex) {
	// 判断是否需要扩容
    // 判断依据：size(当前Map中的元素个数)是否大于threshold(扩容阈值)，当前插入位置是否有Entry节点
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容，数组长度翻倍
        resize(2 * table.length);
        // 重新计算当前插入key的hash
        hash = (null != key) ? hash(key) : 0;
        // 重新计算当前插入key的hash在数组table对应的位置
        bucketIndex = indexFor(hash, table.length);
    }
	// 在该插入位置新建Entry节点
    createEntry(hash, key, value, bucketIndex);
}

// 在map中新建Entry节点
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++;
}

// put的key值为null
private V putForNullKey(V value) {
    // 直接在table[0]的位置插入
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
		// 如果table[0]已有key为null的节点，则直接覆盖
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    
    // -------- table[0]中没有key为null的Entry节点 --------
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}