hashMap底层源码浅析_vlambda技术博客

vlambda
2021-01-04

hashMap底层源码浅析

hashmap是我们经常使用的一个工具类。那么知道它的一些原理和特性吗？

特性

HashMap是一种基于散列算法实现的快速查找的键值对结构。底层实现是链表数组。
允许空键和空值（但空键只有一个，且放在第一位）
元素是无序的(这里的无序是指的插入和读取的顺序不一致)
JDK 8 后又加了底层加上了红黑树优化过长的链表以及并行遍历。

概述

HashMap可以分析的地方很多，网上也有许多文章，本文仅从以下几个方面进行分析：

基础变量
插入(动态扩容，延迟插入，红黑树转换，可以说的地方很多)
并行遍历(jdk8的新特性，快速失败，栅栏机制)

需要了解的基础成员变量

变量名	中文注释
size	此映射中包含的键-值映射的数目。
DEFAULT_INITIAL_CAPACITY	默认容量 16
MAXIMUM_CAPACITY	允许的最大容量
loadFactor	负载因子
threshold	当前 HashMap 所能容纳键值对数量的最大值，超过这个值，则需扩容

这些变量有什么用？答案是扩容

其中threshold就是临界值，当实际K-V个数超过threshold时，HashMap会将容量扩容，threshold＝容量*加载因子。

这些变量如何传入:
HashMap有四个构造方法

public HashMap() 默认构造方法，默认初始容量为16，加载因子为0.75f
public HashMap(int initialCapacity) 指定初始容量的构造方法，加载因子为默认的0.75f
public HashMap(int initialCapacity, float loadFactor) 指定初始容量和默认加载因子的初始方法
public HashMap(Map<? extends K, ? extends V> m) 以子map为入参，构造新的hashmap

扩容：threshold＝容量*加载因子。

插入

网上的讲解也有许多。就简单说一下

hashMap有两个概念对于插入很重要，一个叫做bucket（桶），一个叫做node/entry（元素）

桶与元素他们的关系是怎样的:
对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。一旦插入时key的hahs相同(也叫做hash寻找冲突,或者哈希碰撞)，就会把两个hash值相同的元素存储在一个桶里面。
总而言之，就是一个hashMap包含许多桶，一个桶里面包含了许多元素

接下来看一下插入的api:
hashmap的插入api非常简单，就是一个put

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with {@code key}, or
 *         {@code null} if there was no mapping for {@code key}.
 *         (A {@code null} return can also indicate that the map
 *         previously associated {@code null} with {@code key}.)
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

从这里可以看到他是调用的putVal方法，在通过断点进入

/**
     * Implements Map.put and related methods.
     *
     * @param hash hash for key hash值
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value  如果为真，不要改变现有的值
     * @param evict if false, the table is in creation mode.    如果为false，表示表处于创建模式。
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

源码过长，我将结合网上的博客以及自己的理解将源码抽取并且翻译了成容易理解的伪代码 https://blog.csdn.net/hsee2006/article/details/104784557/

putVal:总流程  
{
    //声明了一个局部变量 tab,局部变量 Node 类型的数据 p,int 类型 n,i
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 初始化桶数组 table，也就是说table是在有数据加载时延迟初始化的
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找当前要插入的数据应该在哈希表中的位置,如果没找到,代表哈希表中当前的位置是空的,否则就代表找到数据了
    // 如果找到数据就赋值，就说明hash冲突了，将旧的值给临时变量p
    {
        if ((p = tab[i = (n - 1) & hash]) == null)
            //  说明没有冲突,直接赋值
            tab[i] = newNode(hash, key, value, null);
        else {
            //  处理hash寻址冲突的代码，解决的同一个位置的新数据和旧数据的共存问题
            代码片段1(后面)
        }
    }
    ++modCount;//   增加当前的操作长度，可以用于线程不安全时的快速失败机制
    if (++size > threshold)//   触发扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

注:这里的 (n-1)&hash 是一种高效的除模取余运算
- 传统的方式进行求余运算。需要先将10进制转成2进制到内存中进行计算，然后再把结果转换成10进制
- 而位运算是直接在内存中进行，不需要经过这些转换
- 但是位运算只能用于除数是2的n次方的数的求余

代码片段1:
{
    /*
        这里会经过三个判断:
        1，如果一来是key冲突，就直接替换值
        2, key不一样，且为是红黑树，则调用红黑树的插入方法
        3, 直接对链表进行写入，如果链表过长会转换结构为红黑树,或者key冲突就直接替换
    */
    //  这个e是一会将会被写入的数据的临时变量
    Node<K,V> e; K k;
    //  如果键的值以及节点 hash 等于链表中的第一个键值对节点时，说明key冲突，则将 e 指向该键值对
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)//   面对树直接插入
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        // 对链表进行遍历，并统计链表长度
        for (int binCount = 0; ; ++binCount) {
            // 链表中不包含要插入的键值对节点时，则将该节点接在链表的最后
            if ((e = p.next) == null) {//如果当前节点的下一个是空的,就代表没有后面的数据了,直接给赋值，这里是真正的赋值操作
                p.next = newNode(hash, key, value, null);
                // 如果链表长度大于或等于树化阈值(8)，则进行将链表优化为红黑树或者进行扩容操作
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            //  如果当前遍历到的数据和要插入的数据的 key 是一样,和上面之前的一样,赋值给变量 e,下面替换内容
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            //  开始下一次遍历
            p = e;
        }
    }
    // 判断要插入的键值对是否存在 HashMap 中
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        //  钩子函数:一般不会使用
        afterNodeAccess(e);
        return oldValue;
    }
}

代码片段2:

并行遍历

并行遍历是java8给jdk多加的一个接口,用来做并行遍历的,它的使用方式如下:

public static void main(String[] args) {
    //  构造一个map
    HashMap map=new HashMap(1,4);
    //  插入值
    for (int i = 0; i < 6; i++) {
        map.put(i,"值_"+i);
    }
    //  得到并行遍历器
    Spliterator spliterator = map.entrySet().spliterator();
    System.out.println("开始分块元素的遍历");

    //  开始分割遍历器
    Spliterator s1 = spliterator.trySplit();
    //  执行原先的遍历器
    System.out.println("执行第一块区域的元素遍历:");
    spliterator.forEachRemaining(item-> System.out.println(item));
    //  执行被分出去的遍历器
    System.out.println("执行第二块区域的元素遍历:");
    s1.forEachRemaining(item-> System.out.println(item));
    System.out.println("执行完毕");
}

结果如下:
开始分块元素的遍历
执行第一块区域的元素遍历:1=值_1
3=值_3
5=值_5
执行第二块区域的元素遍历:0=值_0
2=值_2
4=值_4
执行完毕

由这段代码我们可以看出jdk8新加的这个特性的好处,相比传统的Iterator方法，该方法可以更加高效的处理并行读取map数据,可以将数据分割为多个迭代器，然后传入不同的线程，利用多核更好的处理好海量数据。

那么map是怎么做到这一点的？源码如下:

hashMap的内部类:EntrySet
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    ...
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
    }
    ...
}

由此我们发现实质是利用了里面的一个内部类EntrySpliterator

static final class EntrySpliterator<K,V>
    extends HashMapSpliterator<K,V>
    implements Spliterator<Map.Entry<K,V>> {
    EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                     int expectedModCount) {
    super(m, origin, fence, est, expectedModCount);
    }
}

其中的继承的这个Spliterator接口非常有意思。
我查了下资料,发现它是jdk官方提供的一个并行遍历接口:
Spliterator接口是Java为了并行遍历数据源中的元素而设计的迭代器，这个可以类比最早Java提供的顺序遍历迭代器Iterator，但一个是顺序遍历，一个是并行遍历。

为什么有了Iterator还需要spliterator呢?

从最早Java提供顺序遍历迭代器Iterator时，那个时候还是单核时代，但现在多核时代下，顺序遍历已经不能满足需求了，如何把多个任务分配到不同核上并行执行，才是能最大发挥多核的能力，所以Spliterator应运而生!

如果感兴趣的可以读一下这篇博客
了解Java Spliterator 这篇文章就够了

为什么有了hahsMap还会重写spliterator呢?

如果深入源码会发现，spliterator类有自己实现的默认分割遍历，但是hashMap却重写了一套分割算法。
原来Spliterator的一个特点是每次将元素拆分出去一半。对于HashMap，由于hashMap底层是链表，如果要完全精确到元素，势必会造成算法的复杂和性能的低下。
因此，Spliterator在HashMap的实现过程中，直接是按bucket进行处理，这样会导致每次拆分的数据并不均匀。HashMap中实际上是按照bucket的数量平均拆分，只是可能每个bucket上面Node的数量可能不一致，另外有的bucket可能为空。

我们来看一下spliterator的重写中几个比较重要的概念以及重写

HashMapSpliterator对于spliterator的部分实现
static class HashMapSpliterator<K,V> {
    // 需要遍历的 Map 对象
    final MyHashMap<K,V> map;
    // 当前正在遍历的节点
    Node<K,V> current;          // current node
    // 当前迭代器开始遍历的桶索引
    int index;                  // current index, modified on advance/split
    // 当前迭代器遍历上限的桶索引
    // fence的英语代表栅栏（zha lan）的意思，这里代表边界
    int fence;                  // one past last index
    // 需要遍历的元素个数
    int est;                    // size estimate
    // 期望操作数，用于多线程情况下，如果多个线程同时对 HashMap 进行读写，
    // 那么这个期望操作数 expectedModCount 和 HashMap 的 modCount 就会不一致，这时候抛个异常出来，称为“快速失败”
    int expectedModCount;       // for comodification check
    
    MapSpliterator(MyHashMap<K,V> m, int origin,
                       int fence, int est,
                       int expectedModCount) {
        this.map = m;
        this.index = origin;
        this.fence = fence;
        this.est = est;
        this.expectedModCount = expectedModCount;
    }

    // 获取栅栏
    final int getFence() { // initialize fence and size on first use
        int hi;
        // 第一个分割迭代器会执行下面 if 内的代码,因为构造传入的fence值为-1
        if ((hi = fence) < 0) {
            MyHashMap<K,V> m = map;
            est = m.size;// 获取需要遍历的元素个数
            expectedModCount = m.modCount;//获取当前修改的数量
            Node<K,V>[] tab = m.table;//得到数据
            hi = fence = (tab == null) ? 0 : tab.length;//  如果为null就是0
        }
        return hi;
    }

    // 获取当前迭代器需要遍历的元素个数
    public final long estimateSize() {
        getFence(); // force init
        return (long) est;
    }
    
}

这段代码体现了两个概念
栅栏机制以及快速失败(后面会讲解,先把概念放在这里放在这里)

然后再看EntrySpliterator的实现

static final class EntrySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<Map.Entry<K,V>> {
        EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }

        //  分割遍历器
        public EntrySpliterator<K,V> trySplit() {
            //  hi代表上边界
            //  mid代表限制值+当前索引号对折一半
            //  >>>用来代表一半对折(如果是奇数的话，会先减一再次对折)
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            //  构建出一个新的分割器的同时,将自己的上下边界也进行修改
            return (lo >= mid || current != null) ? null :
                new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }

        //  遍历剩下的元素
        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                //  这段代码没有什么好说的，就是遍历桶，然后把桶里面的元素给读取出来进行函数式处理
                Node<K,V> p = current;
                current = null;
                do {
                    //如果p为空则移动到下一个bucket
                    if (p == null)
                        p = tab[i++];
                    else {
                        //遍历链表 调用外部函数处理
                        action.accept(p);
                        p = p.next;
                    }
                    //  进行读取边界控制判断,不会读取到另外的分割器的边界数据
                } while (p != null || i < hi);
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        //  对单个元素进行遍历，前进一次。这里就不分析了
        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            ...
        }

        public int characteristics() {
            ...
        }
    }

快速失败

总所周知，hahsMap是线程不安全的，为了避免在在线程不安全时使用了hahsMap，java官方提供了一种检测机制。

fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生fail-fast，即抛出 ConcurrentModificationException异常。

其中，并行遍历就利用了这个机制

在EntrySpliterator类的forEachRemaining方法的该段代码就体现了快速失败机制的原理:
public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
    ...
    //  获取预期数据量
    if ((hi = fence) < 0) {
        mc = expectedModCount = m.modCount;
        hi = fence = (tab == null) ? 0 : tab.length;
    }
    else
        mc = expectedModCount;
    if (tab != null && tab.length >= hi &&
        ...
        //  比较预期数据量以及实时数据量
        if (m.modCount != mc)
            throw new ConcurrentModificationException();
    }
}

也就是在遍历时将期望数据量(expectedModCount)和当前实际数据量进行比较(modCount)
如果不相等，就说明在遍历过程中，有其他线程在对数据进行修改，就会报错

注意:fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。(比如数据的却发生了变化，但是数据量却是相等的情况下)

以上，就是hahsMap的底层源码浅析，实际上hashMap所运用到的技巧远不止如此，如果想要提升，推荐直接看jdk源码以及其他人的相应解析博客。

本文链接：https://blog.csdn.net/qq_35824590/article/details/111769203

end

长按识别图中二维码

关注获取更多资讯

不点关注，我们哪来故事？

点个再看，你最好看

vlambda博客
学习文章列表