当前位置： 首页 > article >正文

JDK源码分析：HashMap

article 2024/11/14 15:27:54

介绍

HashMap 是 Java 开发工具包 (JDK) 中提供的一个关键类，它实现了 Map 接口，用于存储键值对（key-value pairs）。HashMap 是一种基于哈希表的 Map 实现，它允许使用任何对象作为键（key）和值（value），并且它不保证元素的顺序。

底层是一个Node单向链表结点数组。

以下是 HashMap 类的一些主要特点和用法：

主要特点

  1. 非同步：HashMap 不是线程安全的，如果多个线程同时修改 HashMap，可能会导致数据的不一致。如果需要线程安全的 Map，可以考虑使用 ConcurrentHashMap。

  2. 允许空键和空值：与某些其他 Map 实现不同，HashMap 允许使用 null 作为键或值。

  3. 基于哈希表：HashMap 的性能主要依赖于哈希表的实现。它使用键的 hashCode() 方法来确定元素在内部数组中的位置，从而实现快速的查找、插入和删除操作。

  4. 无序性：HashMap 不保证元素的顺序。如果需要保持插入顺序或访问顺序，可以考虑使用 LinkedHashMap。

  5. 性能优化：HashMap 使用哈希表来存储数据，它提供了快速的插入、删除和查找操作。然而，某些情况下，哈希表中的桶链表可能会变得很长，导致查找操作的效率降低。为了解决这个问题，Java 8 引入了红黑树（Red-Black Tree）作为哈希表中链表的替代方案。

    1. 红黑树是一种自平衡二叉查找树，它在插入和删除操作时会自动调整树的结构以保持平衡。这使得红黑树在最坏情况下的查找、插入和删除操作的时间复杂度都是 O(log n)，其中 n 是树中节点的数量。

    2. 在 HashMap 中，当链表的长度超过一定阈值（if (binCount >= TREEIFY_THRESHOLD - 1)，TREEIFY_THRESHOLD=8 ）时，链表会被转换为红黑树。这样可以提高查找操作的效率。同样地，当红黑树中的节点数量减少到一定程度时，红黑树会被转换回链表，以节省空间。

构造器

2983eebcf323c1100768ddf91acec93f.png

所有构造器最终指向一个底层方法：

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: " +
    //【1】                                  loadFactor);
    this.loadFactor = loadFactor;
    //【2】
    this.threshold = tableSizeFor(initialCapacity);
}


static final int tableSizeFor(int cap) {
    // 【2.1】
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    // 【2.2】
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}


public static int numberOfLeadingZeros(int i) {
    // HD, Count leading 0's
    if (i <= 0)
        return i == 0 ? 32 : 0;
    int n = 31;
    //【2.1.1】
    if (i >= 1 << 16) { n -= 16; i >>>= 16; }
    if (i >= 1 <<  8) { n -=  8; i >>>=  8; }
    if (i >= 1 <<  4) { n -=  4; i >>>=  4; }
    if (i >= 1 <<  2) { n -=  2; i >>>=  2; }
    return n - (i >>> 1);
}

源码分析：

  • 构造器可以分别指定initialCapacity初始化容量，以及loadFactor负载因子

  • 【1】loadFactor赋值

  • 【2】tableSizeFor：它接受一个整数参数 cap，表示期望的初始容量，并返回一个经过调整的、适用于 HashMap 的哈希表容量。

    另外，使用了无符号右移操作符 >>>，对于 -1，其二进制表示为全 1（在 32 位整数中）。无符号右移操作会将 -1 的二进制表示向右移动指定的位数，并在左侧填充 0。

【2.1】Integer.numberOfLeadingZeros(cap - 1)：这个方法计算 cap - 1 的二进制表示中前导零的数量。例如，对于 cap = 16，cap - 1 = 15，其二进制表示为 1111，没有前导零，所以返回值为 0。

【2.2】这是一个三元运算符链，确保返回的容量是大于等于期望容量的最小的 2 的幂，同时不超过 HashMap 的最大容量限制。

增删改查

添加&更新数据

f16bf8097c160e8a134d5c70a601ff28.png

下面我们挑选最基础的put(K,V)讲解源码

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}


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<K,V>[] tab; Node<K,V> p; int n, i;
        //【1】空哈希表则扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //【2】头结点为空，则新建一个节点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //【3】头节点不为空，下面处理
        else {
            Node<K,V> e; K k;
            //【4】检查头结点，是否正好待取出
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //【5】如果是红黑树，则增加树节点
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //【6】如果是链表，则进行下面处理
                for (int binCount = 0; ; ++binCount) {
                    //【7】遍历到末尾节点
                    if ((e = p.next) == null) {
                        //【8】新增一个节点加进去
                        p.next = newNode(hash, key, value, null);
                        //【9】如果链表长度=7，那么就要转红黑树了，因为这样的查找效率更高
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //【10】转成红黑树节点
                            treeifyBin(tab, hash);
                        break;
                    }
                    //【11】遍历到待取出节点，e就是要找的元素
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //【12】e是已经存在的元素，说明哈希冲突了
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    //【13】更新e节点的值
                    e.value = value;
                // 【14】HashMap#afterNodeAccess是一个空实现
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 【15】操作次数+1
        ++modCount;
        // 【16】如果哈希表数量已经满（size+1），则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
}
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }


    // Callbacks to allow LinkedHashMap post-actions
    void afterNodeAccess(Node<K,V> p) { }
    
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 【17】newCap在老的容器大小扩一倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                 // 【18】下次扩容阈值：在老的扩容阈值同样-大小扩一倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        //【19】初始化哈希表数组，容量为newCap
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //【20】遍历老的哈希表数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 【21】空节点，则填充填充元素（哈希低32位-按位与运算-确保在数组newCap下标范围内）
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                        // 【22】红黑树节点，则调用api进行叶子节点的插入
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { 
                        // 【23】普通Node节点，则进行链表节点插入
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
}

源码分析：

44dec0b21d2626f970d49036b139fdc5.png

移除数据

89b4cd2802ba040145786afe4acff405.png

源码：

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}


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


final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null 
        && (n = tab.length) > 0 
        && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //【1】检查是否命中哈希表元素
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //【2】
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                //【3】
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    //【4】节点是链表，说明有多个元素哈希出现了，索引下标冲突，链表遍历寻找
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }


        //【5】找到Node节点
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
             //【6】红黑树节点
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //【7】普通节点 
            else if (node == p)
                // 【8】p是哈希表元素，链表只有一个元素node，即node==p，那让p直接指向node节点的下一个元素即可了
                tab[index] = node.next;
            else
                //【9】p是node的前驱节点，也是链表元素之一，让p指向node的下一个元素即可
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

源码讲解：

11d2cf9ff35f12d2d7ea4ec347ea5fda.png

获取操作

0f5b35442f49d903de62a165467a668b.png

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}


final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // 【1】
    if ((tab = table) != null 
        && (n = tab.length) > 0 
        && (first = tab[(n - 1) & hash]) != null) {
        
        // 【2】always check first node
        if (first.hash == hash 
            && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 【3】
        if ((e = first.next) != null) {
            // 【4】节点是红黑树节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                // 【5】节点是链表-节点逐个比较
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

源码分析：

  • 【1】检查哈希表是否存在且长度大于0，以及哈希桶中是否有节点

  • 【2】总是检查第一个节点，提高查找性能

  • 【3】头结点有数据

  • 【4】头结点指向的是TreeNode树节点类型，调用红黑树的查找方法

  • 【5】头结点指向的是链表类型，顺序遍历节点，逐个比较

设计思想

1、源码的tab[index = (n - 1) & hash]，目的是什么？

这段代码的核心思想是利用位运算来计算索引。具体来说，(n - 1) & hash这个表达式的作用是将hash的高位舍弃，只保留与n - 1的位数相同的低位。这样可以确保计算出的索引值在0到n - 2之间，因为n - 1的二进制表示中所有位都是1。

为什么要这样做呢？这是因为HashMap的容量n通常是2的幂次方，即n = 2^k。在这种情况下，n - 1的二进制表示中所有位都是1，这样可以充分利用哈希值的低位信息，减少哈希冲突的概率。

总结一句：哈希值的不同低位信息被用来计算不同的索引位置，有助于减少哈希冲突。

2、HashMap的哈希表扩容时机是什么？

HashMap中的元素数量超过其容量（capacity）与负载因子（load factor）的乘积时。

3、HashMap的哈希桶节点什么时候从Node链表转为红黑树？

当HashMap准备插入一个新元素，而当前桶（bucket）已经是一个链表，添加完这个元素之后，链表长度会达到阈值（默认为8），此时会触发扩容。

转为红黑树是为了提高桶元素的访问效率。


http://www.kler.cn/a/290223.html

相关文章：

  • AutoCad 无界面开发
  • mongoDB的安装及使用
  • 【mySql 语句使用】
  • python装饰器的使用以及私有化
  • Linux 进程线程间通信总结
  • Linux相关习题-gcc-gdb-冯诺依曼
  • kubeadm部署 Kubernetes(k8s) 高可用集群【V1.28 】
  • net、udp、tcp
  • Linux之多线程概念
  • mongodb在Java中条件分组聚合查询并且分页(时间戳，按日期分组，年月日...)
  • OpenCV绘图函数（11）计算文本字符串在特定字体、尺寸和厚度下的大小的函数getTextSize()的使用
  • 模型从 HuggingFace 转存到 ModelScope
  • 【ubuntu使用笔记】Ubuntu Desktop 访问SMB共享文件夹
  • Spring声明式事务使用详情（知识点+案例）
  • 【Java】封装
  • 《Zookeeper 的监听机制及原理解析》
  • 后台使用Motionbuilder
  • 聚类算法-Kmeans聚类
  • 【60天备战软考高级系统架构设计师——第八天：设计模式概述】
  • Spring Boot项目中结合MyBatis详细使用
  • “智能化自动化” 架构之4：中间建模脑的软件设计三大原则-依赖倒置控制反转和依赖注入
  • 在react中利用three.js 渲染模型 让鼠标拖拽是模型转动
  • redhat7.9安装zsh以及常用插件
  • 具有平面规则性的单目视觉惯性里程计
  • 反射API与AOP在微服务治理中的实践与思考
  • 飞利浦开放式耳机怎么样？南卡、飞利浦、QCY耳机真实测评