Java深入研究HashMap实现原理

MannaYang / 94 / 2023-09-25 10:51:09

ChatGPT 可用网址,仅供交流学习使用,如对您有所帮助,请收藏并推荐给需要的朋友。
https://ckai.xyz

承接上篇《Java深入研究Collection集合框架》文章中的HashMap、ConcurrentHashMap源码分析,在Java中常用的四个实现Map接口的类,分别是HashMap、TreeMap、LinkedHashMap以及继承自Dictionary抽象类的Hashtable,下面简单概述下各实现类的特点 :

HashMap

根据键的hashcode存储数据,允许null键/值(null键只允许一条,value可以有多条null),非synchronized、元素无序,顺序也可能随时改变,底层基于链表+红黑树实现【JDK1.8】

TreeMap

实现SortedMap接口,可以根据键排序,默认按键值升序排序,也可以指定排序的比较器,在使用时key必须实现Comparable接口,TreeMap在Iterator遍历是排过序的

LinkedHashMap

属于HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序

Hashtable

常用功能跟HashMap类似,不支持null键/值,synchronized线程安全,Hashtable默认的初始大小为11,之后每次扩充,容量变为原来的2n+1.HashMap默认的初始化大小为16.之后每次扩充,容量变为原来的2倍,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁

HashMap重要的常量定义

DEFAULT_INITIAL_CAPACITY =16 默认容量
MAXIMUM_CAPACITY =1 << 30 最大容量
DEFAULT_LOAD_FACTOR = 0.75f 默认负载因子
TREEIFY_THRESHOLD=8 链表转换红黑树的阀值
UNTREEIFY_THRESHOLD=6 红黑树转换链表的阀值
MIN_TREEIFY_CAPACITY=64 桶中bin最小hash容量,如果大于这个值会进行resize扩容操作,
此值至少是TREEIFY_THRESHOLD的4倍

HashMap构造函数

首先看初始化容量、负载因子的有参函数源码

    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;
        this.threshold = tableSizeFor(initialCapacity);
    }

常规的边界判断、赋值操作,通过tableSizeFor方法计算初始容量

HashMap put方法源码分析

    方法调用
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    传入key的hash计算
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    实际调用方法
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //局部node节点tab
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //将初始化的table赋值给tab并判null,如果为空则进行tab初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //根据hash计算tab[i]位置,判断如果为空则调用newNode()存储新的node<K,V>中
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //根据hash值和equals判断key,如果key相同就把老的node赋值给变量e
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //key不同,判断是否时红黑树,如果是则调用putTreeVal()放在树中
            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) {
                        //没有下一个元素,则把当前元素传入newNode()作为下一个元素
                        p.next = newNode(hash, key, value, null);
                        //链表长度超过阈值TREEIFY_THRESHOLD=8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//转换成红黑树
                        break;
                    }
                    //判断key相同则赋值替换
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //判断value是否替换
            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;
    }
  • resize实现
    当put时,如果bucke占用程度已经超过了DEFAULT_LOAD_FACTOR参数初始比例,就把bucket扩充为2倍,之后重新计算index,再把节点放到新的bucket中,源代码说明如下

    Initializes or doubles table size. If null, allocates in accord with initial capacity target held in field threshold. Otherwise, because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table

    实现方法在【JDK1.7】和【JDK1.8】中有差异(1.8引入红黑树),感兴趣可以研究JDK源码对reszie()的实现

HashMap get方法源码分析

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    //hash值同put操作
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //判断tab节点是否为空,根据hash算出下标
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //在第一个node中查找
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //如果有下一个元素
            if ((e = first.next) != null) {
                //如果是树,调用getTreeNode()在红黑树中查找
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    //循环链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap put、get方法思路总结

put方法大致思路

  1. 根据键值key做hash计算,得到插入数组下标,如果tab[i]为null,直接newNode插入新节点
  2. 如果tab[i]不为null,判断tab[i]首个元素和key是否相同,相同就把老元素赋值给局部变量
  3. 如果比较的key不同,判断是否为TreeNode(红黑树),如果是,调用putTreeVal()插入树中
  4. 如果不是TreeNode,对链表做遍历,链表长度超过阈值TREEIFY_THRESHOLD=8转换成红黑树

get方法大致思路

  1. 判断tab节点是否为空,根据hash算出下标
  2. 在第一个node节点中查找,如果有直接return first
  3. 如果没有,判断是否有下一个元素,如果有判断是否为TreeNode,如果是则在树中查找
  4. 如果不是,循环链表查找

equals()和hashCode()的作用

通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果比较的key相同,则利用key.equals()方法去链表或树中去查找对应的节点

<br/>

ConcurrentHashMap实现原理

ConcurrentHashMap在Java 8中取消了Segment分段锁的数据结构,采用数组+链表+红黑树的数据结构,而对于锁的粒度,调整为对每个数组元素加锁(Node节点),简化定位节点的hash算法,这样带来的弊端是hash碰撞会增大,因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。这样一来,查询的时间复杂度就会由原先的O(n)变为O(logN)

关于CAS算法

CAS的全称叫"Compare And Swap",也就是比较并交换,使用时主要涉及到三个操作数,内存值V预期值A新值B,如果在执行时发现内存值V预期值A相匹配,那么他会将内存值V更新为新值B,相反处理器就不会执行任何操作

核心属性

    //用于table[]的初始化和扩容操作,-1表示正在初始化,-N表示有N个线程正在扩容,非负数时,表示初始化table[]的大小,已经初始化则表示扩容阈值,默认为table[]容量的0.75倍
    private transient volatile int sizeCtl;
    //表示默认的并发级别,也就是table[]的默认大小
    private static finalint DEFAULT_CONCURRENCY_LEVEL = 16;
    //默认的负载因子
    private static final float LOAD_FACTOR = 0.75f;
    //链表转红黑树的阀值
    static final int TREEIFY_THRESHOLD = 8;
    //红黑树转链表的阀值,
    static final int UNTREEIFY_THRESHOLD = 6;
    //哈希表的最小树形化容量
    static final int MIN_TREEIFY_CAPACITY = 64;

构造函数

    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;

        //主要是初始化map容量size、concurrencyLevel并发级别
    }

put操作

    //常规put入口
    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        //不允许空键空值
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());//计算key hash
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();//常规初始化tab[]
            //根据hash值与运算确认下标并将节点赋值给f,然后判null
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //如果为空,采用CAS算法将新值插入Node节点
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break; // no lock when adding to empty bin
            }
            //hash值==-1,说明正在扩容
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);//扩容后返回最新tab[]
            else { 
                V oldVal = null;
                synchronized (f) {//获取数组同步锁,
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {//hash大于0,说明是链表
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {//链表遍历
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;//key相同,进行value替换,退出循环
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    //创建新的节点插入链表尾部
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {//如果是红黑树
                            Node<K,V> p;
                            binCount = 2;
                            //// 调用红黑树的插值方法插入新节点
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                        else if (f instanceof ReservationNode)//空节点,占位符
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                    //链表转换红黑树阈值判断
                    if (binCount >= TREEIFY_THRESHOLD)
                        //与HashMap类中转换红黑树有区别,当hash表长度小于MIN_TREEIFY_CAPACITY属性值时尝试扩容操作,相反进行树形化
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

ConcurrentHashMap的put()操作大致流程

  • 初始化map容量size、concurrencyLevel并发级别
  • 对键、值非null判断,计算hash值,判断table[]是否创建,没有就初始化
  • 如果table[i]为null,采用CAS算法将新值插入Node节点
  • 如果不为null,判断hash值是否为-1,如果是则调用helpTransfer()扩容
  • 如果hash值不为-1,就在链表尾部或者和红黑树中插入节点
  • 最后对链表转红黑树阈值做判断,当hash表长度小于MIN_TREEIFY_CAPACITY属性值时尝试扩容操作,相反进行树形化

get操作

    public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());//计算key hash
        //判断table[]是否为null,根据下标确认table[i]节点并做非null约束
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            //比较头部元素是否相同,相同则直接返回该键对应的值
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            //如果头结点的 hash 小于 0,说明正在扩容,或者该位置是红黑树
            else if (eh < 0)
                //e.find可对比查看ForwardingNode类的find()、TreeBin类的find()源码
                return (p = e.find(h, key)) != null ? p.val : null;
            //遍历链表
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

ConcurrentHashMap的get()操作大致流程(不加锁)

  • 计算key的hash值,判断table[]是否为null,同时根据下标判断table[i]是否为null
  • 如果table[i]则比较链表头部元素是否相同,如果是直接返回该键位置所对应的值
  • 如果hash不相同,判断是否是红黑树或是正在扩容操作,如果是则在树中查找
  • 如果不是红黑树或是正在扩容操作,则遍历链表查找

Java8对ConcurrentHashMap实现改进

  • 不采用segment而采用node,锁住node来实现减小锁粒度,加入红黑树机制
  • 换回Synchronized关键字,替换ReentrantLock分段锁
  • 设计了MOVED状态,允许多线程进行帮助扩容操作
  • 使用CAS操作来确保node的一些操作的原子性,这种方式代替了锁
  • 采用sizeCtl的不同值来代表不同含义,起到了控制的作用

以上涉及JDK源码部分均来自 JDK 1.8


Java深入研究HashMap实现原理
作者
MannaYang
许可协议
CC BY 4.0
发布于
2023-09-25
修改于
2024-04-22
Bonnie image
尚未登录