HashMap 源码分析

前言

接着上一篇我们讲述了下碰撞和手写HashMap 这次我们来分析分析HashMap 源码分析

HashMap 源码分析

PUT 方法源码分析

img

代码语言：java复制

public V put(K key, V value) {
    // 判断数组为不为空
    if (table == EMPTY_TABLE) {
        
        // 如果数组为空,开始初始化数组
        inflateTable(threshold);
    }
    // 如果key为空,
    if (key == null)
        // 判断之前有没有过null的key, 如果有就平板, 没有就添加
        return putForNullKey(value);
    
    // 获取hash值
    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 && // 如果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;
}

初始容量问题

img

默认初始容量必须是 2 的指数次幂，如果不是 2 的指数次幂，会强行转化成 2 的指数次幂，采用向上接近的转换方式，假设初始容量为 14，不是 2 的指数次幂，向上比较接近的是 2 的 4 次方，所以初始容量会转化成 16。

img

img

为什么要保证 capacity 是 2 的次幂呢？在上面我们看出，计算角标的方式为按位与的形式，因为 length 永远是 2 的次幂，所以 length-1 通过二进制表示，永远都是尾端以连续 1 的形式表示，这样做的好处，& 运算速度快，至少比 % 取模运算块，能保证索引值肯定在 capacity 中，不会超出数组的长度，(n - 1) & hash，当 n 为 2 次幂时，会满足一个公式：(n - 1) & hash = hash % n。在源码中，计算数组位置。

img

img

取出 key 的 HashCode，进行一些异常和与操作，目的让得到的值更加 hash，减少 hash 碰撞。

img

在源码采用按位与的形式计算得出在数组当中的位置，在 HashMap 中并不是直接使用取模的方式控制在 1-15 之间，是采用位运算的方式，位运算的效率要高于取模，位运算效率最高，取模效率最差，

img

img

HashMap 扩容

HashMap 中扩容是根据阈值 threshold 来进行的，threshold 是根据当前 HashMap 中存了多少 element，threshold 的值等于容量 capacity * 扩容阈值比率0.75，DEFAULT_LOAD_FACTOR = 0.75，假设当前容量是 16，当容量到 16 * 0.75 = 12 时，扩容。

img

img

扩容过程

img

会创建一个新的数组，大小为原来的 2 倍，创建完毕后，开始转移数据。

img

代码语言：java复制

void transfer(Entry[] newTable, boolean rehash) {
    // 新数组的长度
    int newCapacity = newTable.length;
    
    // 遍历原来的数组,取出每一个元素
    for (Entry<K, V> e : table) {
        
        // 每取一个元素时, 判断为不为空
        while (null != e) {
            
            // 如果不为空, 再取出下一个节点位置,next记录
            Entry<K, V> next = e.next;
            
            if (rehash) {// 原key是否重新散列
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            
            // 计算出新的数组角标位置
            int i = indexFor(e.hash, newCapacity);
            
            // 把当前元素的下一个位置指向新数组的位置
            e.next = newTable[i];
            
            // 把当前元素设置到新数组当中
            newTable[i] = e;
            
            // 继续下一个节点操作
            e = next;
        }
    }
}

遍历原来的数组当中的每一个元素，链表当中同样也会遍历，采用的是一个嵌套循环，遍历出的数据再一次进行 hash，算出对应的 HashCode，存储到新数组指定的位置当中。

单线程转移示列图

0 人点赞