Java：HashMap源码分析（JDK 1.7）

爱被打了一巴掌 2022-05-27 09:21 172阅读 0赞

## HashMap源码分析 ##

注：JDK 1.7  
首先先总体概括下吧，在1.7中，HashMap是由数组+链表的形式组成的（1.8中当HashMap达到一定大小后会使用红黑树），具体如下。

/* 数组部分：table 链表部分：Entry<K,V>类含有一个指向Entry<K,V>类对象 的next “指针” */
    static final Entry<?,?>[] EMPTY_TABLE = {};
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
    static class Entry<K,V> implements Map.Entry<K,V> { 
            final K key;
            V value;
            Entry<K,V> next;
            int hash;
            ……
    }

![这里写图片描述][70]  
对实际存储方式有一个大致了解后就可以从初始化阶段讲起了。

## 初始化 ##

在创建HashMap对象时（比如`HashMap<String,Object> param = new HashMap<String,Object>()`）会首先调用如下构造函数，这里会指定初始化时table（即HashMap）的大小和table（即HashMap）需要进行扩容时的预警大小的比例值。  
默认大小`static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16`  
扩容预警大小`static final float DEFAULT_LOAD_FACTOR = 0.75f;`

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

然后会调用另一个构造函数，并且会初始化3个成员变量。  
loadFactor 为判断HashMap是否需要扩容的预警值大小的比例值，此处为0.75  
threshold 为HashMap的大小值，此处为16（2^4），需要扩容的预警值大小 = 0.75 \* 16 = 12，  
至此，初始化完成。

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    transient int hashSeed = 0;
    private transient Set<Map.Entry<K,V>> entrySet = null;
    
    public HashMap(int initialCapacity, float loadFactor) {
        ......//因为这里这段是判断initialCapacity,
        //loadFactor大小的一些异常处理，所以直接省略
        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }
    /** * Initialization hook for subclasses. This method is called * in all constructors and pseudo-constructors (clone, readObject) * after HashMap has been initialized but before any entries have * been inserted. (In the absence of this method, readObject would * require explicit knowledge of subclasses.) */
    void init() {
    }

创建完了HashMap，就插入一些数据吧。

## put(K key, V value) 函数 ##

涉及到的相关源代码

1,2,3,4
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        /*扰动函数，计算key类型的hashcode值后对其进行扰动， 目的为配合indexfor函数将值散列的更加均匀*/
        int hash = hash(key);  
        int i = indexFor(hash, table.length); //
        /*计算出传入的key值应该对应的位置，因为会出现hash值相同的情况， HashMap的处理方式是开放式HashMap，即使用链表方式存储hash值相同时的值， 这里就是在查询当前输入的key是否已经存在，如果存在的话就覆盖， 并返回之前的value值*/
        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;
            }
        }
        //如果当前输入的key值在原table中不存在，则进行添加
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    1.
    //初始化大小，扩容预警值大小等等
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
    
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }   
    2.
    //扰动函数，为了让key值分布的更加均匀，分散
    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);
    }
    3.
    //计算数组下标值
    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);
    }
    5.
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
    6.
    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++;
    }
    static class Entry<K,V> implements Map.Entry<K,V> {
        /** * Creates new entry. */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

1.当table 为空数组时，执行inflateTable(threshold)函数（threshold此时为16）。  
可以看到inflateTable函数中`table = new Entry[capacity];`，这里table变为了一个大小为16的Entry数组，并且threshold 又被重新赋值为扩容预警值大小，这里为12。  
2.赋值结束后将会计算输入的key值的hash值（`int hash = hash(key)`），会使用到key对应类型的hashCode()函数。所以当想要往HashMap中插入自定义类型的key值的话就需要实现一个hashCode()函数。这里对hashCode返回值进行了一大推的位运算，实际目的是为了最终在计算数组下标值时尽可能的散列数据。在1.8中优化了hash()函数，将原来的一堆位运算修改为只进行一次位运算：

static final int hash(Object key){
        int h;
        return (key == null) ？0 : (h = key.hashCode())^(h >>> 16);
    }

因为从1.8的优化代码比较好理解，实际上这一段代码与1.7的本质上没有区别，无非是减少了位运算次数。所以这里的hash函数用1.8的代码来讲。  
我们知道hashCode()函数返回的是int值（`public native int hashCode();`）  
Java中int值的大小为\[－2^31，2^31-1\]，即存储大小为32位。`(h = key.hashCode())^(h >>> 16)`后的值的后16位相当于融合了原来hash值的高16位与低16位特性。然后问题来了这里如果直接使用hash值，那么总数会有\[－2^31，2^31-1\]，40亿左右的映射控件，但是我们的table（HashMap）初始容量只有16，是装不下\[－2^31，2^31-1\]那么多映射的，所以我们需要对hash值进行取模操作。  
![这里写图片描述][70 1]  
3.indexFor函数，返回`h & (length-1)`，此时length值为table.length。可知经过与运算后返回的值的范围为\[0，length-1\]。即将\[－2^31，2^31-1\]的hash值映射到了\[0，length-1\]下标值中，可以看出实际上是以hash值的低几位来决定下标值的，但是如果直接使用hashCode值而不进行扰动操作的话，这低几位的hashCode值重复干扰的可能性非常大，因此才会引入扰动函数（具体指hash函数里的那些位操作）。这样返回的hash值的低几位也会包含高几位的特性，一定程度上会降低重复干扰。1.8中修改为只进行一次位运算来扰动，所以这里的重复干扰实际也是很拼人品的∠( ᐛ 」∠)\_。经过hash的扰动后，可以使得key以更加散列的形式储存在table中，如果key的hash值重复干扰严重的话就会出现大量的链表存储，而链表形式的信息和数组形式的信息哪一种查询起来更方便快捷相信不用多讲。  
这里其实也说明了为什么HashMap大小一定是2的幂次方。  
因为计算下标映射时的`h & (length-1)`，如果table（HashMap）大小不是2的幂次方，会有部分下标值无法正常使用。

/** * The default initial capacity - MUST be a power of two. */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

4.当计算出对应的下标值后，就可以开始插入了，等等，如果HashMap中已经存在相同key值的信息呢？所以这里需要先对表进行遍历，查询是是否存在相同的key值信息。当查询到有时，就将当前新的value值覆盖储存，并返回旧value值。当没有时，执行插入操作。

5.`addEntry(hash, key, value, i)`  
首先如果table中key-value键值对数大于等于threshold值（之前threshold 被重新赋值为当前table大小*扩容预警值系数 = 16*  0.75 = 12 = 当前扩容预警大小为12）并且当前key计算得出的下标值对应的数组下标位置不为空时，将会进行扩容操作。这部分等下讲。先把put操作跑完。

/** * The number of key-value mappings contained in this map. */
    transient int size;

6.`createEntry(hash, key, value, bucketIndex)`  
创建新的Enter，旧的Enter放到新的Enter的next下，对照上面给出的源码。

至此插入完成。

## 扩容 ##

现在来讲下扩容的事，已上面put里出现的扩容情况说明  
相关源代码

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //如果现在的大小等于最大容量时，将threshold设置为最大值，防止之后再次触发扩容操作
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        //新建table存放重新计算位置的值
        Entry[] newTable = new Entry[newCapacity];
        //重新计算之前的值的地址
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        //重新计算扩容预警值大小threshold 32*0.75 24
        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<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //重新计算位置
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i]; //null
                newTable[i] = e;
                e = next;
            }
        }
    }

可以看到每次扩容的大小为原来的2倍，这也符合上面提到的table（HashMap）的大小必须为2的幂次方。  
transfer函数会按照新的table大小重新计算之前table中的下标值，并重新存储。并且这里可以发现重新计算位置后链表中的储存顺序与之前相比变成倒过来了。在1.8中，由于会涉及到红黑树，所以对这一块进行了大量改写，改写后的将不会出现1.7中链表信息倒过来的这种情况。

## get(Object key) 函数 ##

相关源代码

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
    
        return null == entry ? null : entry.getValue();
    }
    
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
    
        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;
    }

怎么看怎么像put的一部分对吧，基本上和put中查重的部分一个样，如果key值不为空则计算hash值，然后根据hash值计算出下标值，然后检索改下标值对应的table数组下标位置处的链表，查询是否存在对应的key值，然后返回，非常简单。

## clear()函数 ##

相关源代码

public void clear() {
        modCount++;
        Arrays.fill(table, null);
        size = 0;
    }
    
    Arrays.class
    public static void fill(Object[] a, Object val) {
        for (int i = 0, len = a.length; i < len; i++)
            a[i] = val;
    }

很简单明了的全部置空

## isEmpty()函数 ##

相关源代码

public boolean isEmpty() {
        return size == 0;
    }
    
    /** * The number of key-value mappings contained in this map. */
    transient int size;

## remove(Object key)函数 ##

相关源代码

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
    
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        //如put中，计算key的hash值，对应的下标值，并暂存对应table下标位置的Entry对象
        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,上面put和get时都是for， 画风不一样了啊（逼死强迫症系列_(:з」∠*)_）， 那我也改成用注释来说明了∠( ᐛ 」∠)_，皮一下很开心。 */
        while (e != null) {
            //开始遍历
            Entry<K,V> next = e.next;
            Object k;
            //当hash相同，key相同时
            if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) {
                //对HashMap修改次数+1
                modCount++;
                //HashMap所存储的键值对-1
                size--;
                //只有在第一次遍历时prev == e
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                //切断引用链，依赖GC回收，返回该对象
                return e;
            }
            prev = e;
            e = next;
        }
    
        return e;
    }
    
    void recordRemoval(HashMap<K,V> m) {
    }

以上基本上包含了我们日常使用中比较常用的HashMap函数，当然HashMap函数一共也没几个就是了`_(:з」∠*)_`。

[70]: /images/20220527/b46a2b62518f413989dfb6affe1a74da.png
[70 1]: /images/20220527/34b26aaa5d884893b0fc75f9ef59ccad.png