数据结构算法 - HashMap 源码解析

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 数据结构算法 - HashMap 源码解析

思考题:

equals 和 == 的区别,hashCode 与它们之间的联系?

HashMap 的长度为什么是 2 的幂次?

五个线程同时往 HashMap 中 put 数据会发生什么?

Hashmap中的hash冲突到底指的是什么?

Hashmap进行put操作的时候,会对key值进行比较吗?

HashMap中是采用的键值对的方式存储,那么put操作的时候是直接比较key值,相等覆盖,不等新增,怎么会出现线程不安全的情况?

HashMap什么情况下进行扩容?


一、初窥HashMap


HashMap是应用更广泛的哈希表实现,而且大部分情况下,都能在常数时间性能的情况下进行put和get操作。

要掌握HashMap,主要从如下几点来把握:

jdk1.7中底层是由数组(也有叫做“位桶”的)+链表实现;

jdk1.8中底层是由数组+链表/红黑树实现可以存储null键和null值,

线程不安全初始size为16,

扩容:newsize = oldsize*2,size一定为2的n次幂扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容)当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀.


1.8中HashMap结构图解:

4.png


Hashmap中的hash冲突到底指的是什么?


简单的说,我们向hashmap中put数据时,首先会根据key值的hashcode的值去bucket数组中进行快速选址找到对应的桶,当出现hashcode相等的情况,就是出现了hash冲突。


很多小朋友可能还是很迷惑,为什么叫Hash冲突呢,出现了hash冲突会导致什么问题?

首先一点,不同的key值会计算出相同的hashcode,这是产生hashcode根本的原因。

出现了hash冲突,就会导致,多个不同的key值,对应同一个桶。


那么为什么不让每个key值都计算出唯一的hashcode呢?

如果这样,我向hashmap中存1万个值,我的bucket数组的长度就有1万,每次根据key去取值的时候,要从这1万个数组元素中去取,查询效率可想而知。

这里的hashcode值,可以简单的想象成是根据key值和bucket数组的长度计算的模(可以理解成余数),根据这个模,找到存放entry的数组对应的index。(实际中更加复杂)

如果当前桶中是空的,则直接添加。

插入的时候,不会比较key值,只会比较key的hash值。


那么hashMap中是怎么解决hash冲突的呢?

hashmap中通过链表和红黑树来解决hash冲突。


为什么说HashMap是线程不安全的?

在接近临界点时,若此时两个或者多个线程进行put操作,都会进行resize(扩容)和reHash(为key重新计算所在位置),而reHash在并发的情况下可能会形成链表环。

个人见解:

在多个线程向hashmap中同一个空位插入数据时,刚好出现hash冲突,可能会出现相互覆盖的情况。


什么时候会进行扩容,会导致什么问题?


源码:

/**
     * The default initial capacity - MUST be a power of two.
     * 初始容积的大小16,必须是2的平方。这和操作系统的位移计算有关
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  /**
     * The load factor used when none specified in constructor.
     * 负载因子,可以理解成扩容的阈值
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
   /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     *  当链表的长度大于这个值时,将链表转化为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;


核心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 <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
       //如果table为空或者长度为0,先进行扩展resize
        if ((tab = table) == null || (n = tab.length) == 0)
           //初次扩容n等于8
            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;
            //如果链表尾部元素的hash值和插入元素的hash值相等,且key的内存地址相等或key值相等,则e = p;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
               //如果p为树节点,则向红黑树中添加新节点e
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//如果p不是树节点
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //尾部节点的next添加新节点
                        p.next = newNode(hash, key, value, null);
                        //如果链表长度大于等于8,则转为红黑树
                        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;
        #当链表的长度,大于threshold = loadFactor * 容量  时,进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }


如果存在Hash碰撞就会以链表的形式保存,把当前传进来的参数生成一个新的节点保存在链表的尾部(JDK1.7保存在首部)。而如果链表的长度大于8那么就会以红黑树的形式进行保存。


扩容机制核心方法Node<K,V>[] resize():

HashMap扩容可以分为三种情况:


第一种:使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table,并且thershold为0。因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是16。同时threshold = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12。


第二种:指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold,接着

threshold = 当前的容量(threshold)* DEFAULT_LOAD_FACTOR。


第三种:HashMap不是第一次扩容。如果HashMap已经扩容过的话,那么每次table的容量以及threshold量为原有的两倍。


这边也可以引申到一个问题就是HashMap是先插入数据再进行扩容的,但是如果是刚刚初始化容器的时候是先扩容再插入数据。

目录
相关文章
|
10天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
73 29
|
10天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
62 29
|
10天前
|
存储 机器学习/深度学习 人工智能
C 408—《数据结构》易错考点200题(含解析)
408考研——《数据结构》精选易错考点200题(含解析)。
81 27
|
10天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
68 25
|
10天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
56 23
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
47 2
|
2月前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
67 20
|
2月前
|
存储 缓存 Java
HashMap源码剖析-put流程
更好地掌握 `HashMap` 的内部实现原理,提高编写高效代码的能力。掌握这些原理不仅有助于优化性能,还可以帮助解决实际开发中的问题。
61 13
|
2月前
HashMap源码浅分析与解读
阿华代码解读,不是逆风就是你疯HashMap 和TreeMap都继承于Map,Map是一个接口在实现这个接口的时候,需要实例化TreeMap或者HashMap。
|
3月前
|
监控 Java 应用服务中间件
高级java面试---spring.factories文件的解析源码API机制
【11月更文挑战第20天】Spring Boot是一个用于快速构建基于Spring框架的应用程序的开源框架。它通过自动配置、起步依赖和内嵌服务器等特性,极大地简化了Spring应用的开发和部署过程。本文将深入探讨Spring Boot的背景历史、业务场景、功能点以及底层原理,并通过Java代码手写模拟Spring Boot的启动过程,特别是spring.factories文件的解析源码API机制。
128 2

推荐镜像

更多