HashMap源码小读一（jdk7）

本文主要是介绍HashMap源码小读一（jdk7），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

仅针对JDK 1.7.0_80版本

1. 内部数据存储结构

2. 初始化

public HashMap() {
	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

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();
}
复制代码

3. 新增元素

java.util.HashMap#put

public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        // 如果table为空，初始化table
        inflateTable(threshold);
    }
    if (key == null)
        // 如果key为null -> 如果key为null则hash值为0，将元素存放在table[0]中
        // 如果table[0]为null，则将其放置在table[0]除
        // 如果table[0]不为null，则寻找table[0]的节点中key为null的节点并设置新value
        return putForNullKey(value);
    // 计算key的hash
    int hash = hash(key);
    // 确定hash对应在table中的index
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        // 处理table[i]
        // 如果table[i] 不为空
        Object k;
        // 
        if (e.hash == hash && // key的hash相等
            ((k = e.key) == key || key.equals(k))) { // map的链表结构节点的key == 待保存的key。或者 key equals。
            // 此时表示待保存的元素的key已存在map中
            // 替换旧值并返回就值
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
复制代码

java.util.HashMap#indexFor

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    // 首先因为需要确定在table中的index，所以最后的结果范围必须为 [0, capacity-1]
    // 那正常的操作逻辑是使用 h % length
    // 而又因为位运算的 & 操作其实是比 % 操作更高效的
    // 所以此处采用了 & 操作
    // 那为了确保 在进行 & 操作后的结果能够全部覆盖到 [0, capacity-1] 的范围
    // 所以需要将 capacity 设置为2的整数次幂
    // 因为 2^n 的二进制位       0000 0000 0000 0000 0000 0000 0001 0000
    // 而 2^n -1 的二进制码为    0000 0000 0000 0000 0000 0000 0000 1111
    // 再进行 & 操作时 就能够覆盖到[0, capacity-1]
    return h & (length-1);
}
复制代码

java.util.HashMap#inflateTable

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    // 找到最接近于大于等于指定值的2的幂设定为初始容量
    int capacity = roundUpToPowerOf2(toSize);
    // 设置扩容阈值
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 初始化table
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
复制代码

java.util.HashMap#roundUpToPowerOf2

// 获取到比与number最接近且大于number的2的整次幂的正整数
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;
    // number 如果 > 1 --> Integer.highestOneBit((number - 1) << 1)
    // 如number为23		   0000 0000 0000 0000 0000 0000 0001 0111
    // number -  1 		    0000 0000 0000 0000 0000 0000 0001 0110
    // << 1					0000 0000 0000 0000 0000 0000 0010 1100
    // 44
    // highestOneBit -> 32
}	
复制代码

java.lang.Integer#highestOneBit

public static int highestOneBit(int i) {
    // HD, Figure 3-1
    // 将一个整数右移一位，然后做或操作
    // 例如，此时 i = 22
    // i = 22   	0000 0000 0000 0000 0000 0000 0001 0110
    // i >> 1		0000 0000 0000 0000 0000 0000 0000 1011
    
    // |            0000 0000 0000 0000 0000 0000 0001 1111
    // >> 2         0000 0000 0000 0000 0000 0000 0000 1111
    // |            0000 0000 0000 0000 0000 0000 0001 1111
    // >> 4			0000 0000 0000 0000 0000 0000 0000 0000
    // |			0000 0000 0000 0000 0000 0000 0001 1111
    // >> 8			0000 0000 0000 0000 0000 0000 0000 0000
    // | 			0000 0000 0000 0000 0000 0000 0001 1111
    // >> 16		0000 0000 0000 0000 0000 0000 0000 0000
    // | 			0000 0000 0000 0000 0000 0000 0001 1111
    
    // --> i		0000 0000 0000 0000 0000 0000 0001 1111
    // i>>>1		0000 0000 0000 0000 0000 0000 0000 1111
    // i - (i>>>1)	0000 0000 0000 0000 0000 0000 0001 0000
    // 返回 16
    // 所以可以看出 -> 这些操作的结果是将原始的数值保留最高为为1的结果 ，因为只存在一位上为1，所以返回的结果为2的整数次幂，且为小于i且最接近i的数。
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
复制代码

java.util.HashMap#initHashSeedAsNeeded

final boolean initHashSeedAsNeeded(int capacity) {
    // 初始化的时候hashSeed为0，此处false
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() && // vm启动时会为其赋值为true
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); // capacity(8) >= 2147483647 --> false
    // useAltHashing -> false
    // false ^ false -> false
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    // 此时hashSeed依旧为0
    return switching;
}
复制代码

sun.misc.VM#isBooted

private static volatile boolean booted = false;
public static boolean isBooted() {
    return booted;
}
复制代码

java.util.HashMap.Holder

private static class Holder {
     /**
     * Table capacity above which to switch to use alternative hashing.
     */
    static final int ALTERNATIVE_HASHING_THRESHOLD;
	static {
        // 这里的altThreshold值可以通过测试的出为null
    	String altThreshold = java.security.AccessController.doPrivileged(
            new sun.security.action.GetPropertyAction(
                "jdk.map.althashing.threshold"));
        int threshold;
        try {
            threshold = (null != altThreshold) // null != null -> false
                    ? Integer.parseInt(altThreshold)
                	// static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
                    : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT; // 2147483647
             // disable alternative hashing if -1
            if (threshold == -1) { // false
                threshold = Integer.MAX_VALUE;
            }
            if (threshold < 0) { // false
                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; // 2147483647
    }
}
复制代码

测试代码

import sun.misc.VM;

import java.util.HashMap;

public class Test {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        System.out.println("VM.isBooted(): " + VM.isBooted());
        String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                        "jdk.map.althashing.threshold"));
        System.out.println("altThreshold: " + altThreshold);
        map.put("222", "333");
        System.out.println("VM.isBooted(): " + VM.isBooted());
        System.out.println("altThreshold: " + altThreshold);
    }
}
复制代码

输出结果为：

VM.isBooted(): true
altThreshold: null
VM.isBooted(): true
altThreshold: null
复制代码

java.util.HashMap#putForNullKey

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        // e为数组中taile[0]中的节点
        // e != null -> 表示table[0]中已存在节点数据
        // 找到table[0]中节点的key为null的节点 并设置新value，返回旧value
        // 如果不存在 -> 跳出循环
        if (e.key == null) { // 如果节点的key为null
            V oldValue = e.value; // 将新的value设置到节点中，将旧的value返回
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
        
    }
    modCount++;
    // 在table[0]中没有找到key为null的节点
    // 将key为null的节点添加到hash为0的位置即table[0]中
    addEntry(0, null, value, 0);
    return null;
}
复制代码

java.util.HashMap#addEntry

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 当前map中的数据可数 是否到达扩容阈值，并且table[index]已经存在值
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 所以在addEntry中 
        // 只有 当前map的size 到达 扩容阈值 并且
        // 待增加元素的index出的table[index]已经有元素时 
        // 才会触发扩容
        resize(2 * table.length);
        // 计算hash -> 如果key为null则hash为0，此时会将元素放到table[0]中
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
     createEntry(hash, key, value, bucketIndex);
}
复制代码

java.util.HashMap#createEntry

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 创建一个新的Entry并存放在table[index]处，注意Entry的构造方法，会将当前table[index]传入
    // 使新创建的Entry的next指向table[index] -> 表明在链表中新增元素时增加在头结点处
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    // size + 1
    size++;
}
复制代码

java.util.HashMap.Entry#Entry

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

hash计算方式 java.util.HashMap#hash

TODO

final int hash(Object k) {
    int h = hashSeed; // 以hashSeed当前为0为例
    if (0 != h && k instanceof String) {
        // hashSeed不为0时，如果key为String类型，则采用其他计算hash方式
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
复制代码

HashMap对key，value为null的处理

1. HashMap只会保存一个key为null的的数据，且其保存在table[0]中
2. HashMap未对value为null的数据做任何限制及处理。

扩容操作

java.util.HashMap#resize

void resize(int newCapacity) {
    // 保存一个旧table的引用
    Entry[] oldTable = table;
    // 旧table容量
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) { // 旧table容量已达到允许最大值 -> 无法扩容。增大扩容阈值并返回
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity]; // 初始化一个新的table
    // 将旧table中的节点移动到新的table中
    // 根据刚才对initHashSeedAsNeeded()的分析 -> 只有在newCapacity >= Integer.MAX_VALUE时，才会启用hashSeed
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 在完成节点数据转移后，将newTable赋值给HashMap的table引用变量
    table = newTable;
    // 重新设置扩容阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    // 扩容结束
}
复制代码

java.util.HashMap#transfer

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        // 遍历旧table数组中的每个节点
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 为便于理解 此处先假设所有的index都不需要更改（实际情况中为要么不变，要么更改为当前index + capacity。
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
复制代码

transfer说明，为便于说明，假设此时旧的table以及新建的table->newTable如下图

假设此时我们对table[0]中的数据进行transfer。在while循环中，第一次循环，在代码执行到第9行时，结构如下图：

假设当前table[0]中所有的节点在新table中的index都为0，下面代码执行如图

e.next = newTable[i];
newTable[i] = e;
e = next;
复制代码

执行完第1行后

执行完第2行后

执行完第3行后

然后while继续循环知道最终完成效果如下：

从效果上可以发现，transfer会将之前链表上的元素逆序后存储在新table中的链表中，当然这种做法也会导致在多线程transfer时的线程安全问题（后续会详细说明）。

然后继续遍历处理table中的其他节点达到数据转移到new table中。

获取元素

java.util.HashMap#get

public V get(Object key) {
    if (key == null)
        // 如果key为null
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
复制代码

java.util.HashMap#getForNullKey

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    // 已经将key为null的元素存放在table[0]中
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

复制代码

java.util.HashMap#getEntry

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    // 计算hash，如果key为null则hash为0
    int hash = (key == null) ? 0 : hash(key);
    // 确定hash在table中的index
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        // 遍历table[index] 链表结构
        e != null;
        e = e.next) {
        Object k;
        if (e.hash == hash && // hash相等
            ((k = e.key) == key || (key != null && key.equals(k)))) // key相等==，或者key equals
            // 找到元素，返回e
            return e;
    }
    return null;
}
复制代码

这篇关于HashMap源码小读一（jdk7）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！