史上最全的Java容器集合之HashMap(源码解读)(二)

简介: 史上最全的Java容器集合之HashMap(源码解读)(二)

HashMap的成员方法

put方法

//向哈希表中添加元素
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
复制代码
  • 向用户开放的put方法调用的是putVal方法:
  • putVal方法需要判断是否出现哈希冲突问题:
  • 其中如果哈希值相等,key也相等,则是覆盖value操作;如果不是覆盖操作,则插入一个普通链表节点;
  • 遍历到尾部,追加新节点到尾部;
  • 在元素添加的过程中需要随时检查是否需要进行转换成红黑树的操作;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //tab存放当前的哈希桶,p用作临时链表节点  
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果当前哈希表是空的,代表是初始化
    if ((tab = table) == null || (n = tab.length) == 0)
    //那么直接去扩容哈希表,并且将扩容后的哈希桶长度赋值给n
    n = (tab = resize()).length;
    //如果当前index的节点是空的,表示没有发生哈希碰撞。直接构建一个新节点Node,挂载在index处即可。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//否则 发生了哈希冲突。
        Node<K,V> e; K k;
        //如果哈希值相等,key也相等,则是覆盖value操作
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//将当前节点引用赋值给e
        else if (p instance of 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;
                }
                //如果找到了要覆盖的节点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e不是null,说明有需要覆盖的节点,
        if (e != null) { // existing mapping for key
            //则覆盖节点值,并返回原oldValue
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //这是一个空实现的函数,用作LinkedHashMap重写使用。
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //如果执行到了这里,说明插入了一个新的节点,所以会修改modCount,以及返回null。
    ++modCount;
    //更新size,并判断是否需要扩容。
    if (++size > threshold)
    resize();
    //这是一个空实现的函数,用作LinkedHashMap重写使用。
    afterNodeInsertion(evict);
    return null;
}
复制代码

image.png

总结一下put过程

  • 第一步当然是先计算key的hash值(有过处理的 (h = key.hashCode()) ^ (h >>> 16))
  • 第二步调用putval方法,然后判断是否容器中全部为空,如果是的话,就把容器的容量扩容。
  • 第三步,把最大容量和hash值求&值(i = (n - 1) & hash),判断这个数组下标是否有数据,如果没有就把它放进去。还要判断key的equals方法,看是否需要覆盖。
  • 第四步,如果有,说明发生了碰撞,那么继续遍历判断链表的长度是否大于8,如果大于8,就继续把当前链表变成红黑树结构。
  • 第五步,如果没有到8,那么就直接把数据存在链表的尾部
  • 第六步,最后将容器的容量+1。

key.hashCode()是Key自带的hashCode()方法,返回一个int类型的散列值。我们大家知道,32位带符号的int表值范围从-2147483648到2147483648。这样只要hash函数松散的话,一般是很难发生碰撞的,因为HashMap的初始容量只有16。但是这样的散列值我们是不能直接拿来用的。用之前需要对数组的长度取模运算。得到余数才是索引值。

get方法

public V get(Object key) {
    Node<K,V> e;
    //传入扰动后的哈希值 和 key 找到目标节点Node
    return (e = getNode(hash(key), key)) == null ? null : e.value; 
}
复制代码

HashMap向用户分开放的get方法是调用的getNode方法来实现的

//传入扰动后的哈希值 和 key 找到目标节点Node
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //查找过程,找到返回节点,否则返回null
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            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;
}
复制代码

简单讲讲查询过程,还是比较简单的

  • 第一步,看下整个容器是否为空。
  • 第二步,如果不为空,再比较hash值的同时需要比较key的值是否相同e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))
  • 然后返回

contains

 HashMap没有提供判断元素是否存在的方法,只提供了判断Key是否存在及Value是否存在的方法,分别是containsKey(Object key)、containsValue(Object value)。 containsKey(Object key)方法很简单,只是判断getNode (key)的结果是否为null,是则返回false,否返回true。

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null; 
}
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    //遍历哈希桶上的每一个链表
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
            //如果找到value一致的返回true
            if ((v = e.value) == value || (value != null && value.equals(v)))
                return true;
            }
        }
    }
    return false; 
}
复制代码

判断一个value是否存在比判断key是否存在还要简单,就是遍历所有元素判断是否有相等的值。这里分为两种情况处理,value为null何不为null的情况,但内容差不多,只是判断相等的方式不同。这个判断是否存在必须遍历所有元素,是一个双重循环的过程,因此是比较耗时的操作。

remove方法

HashMap中“删除”相关的操作,有remove(Object key)和clear()两个方法。 其中向用户开放的remove方法调用的是removeNode方法,,removeNode (key)的返回结果应该是被移除的元素,如果不存在这个元素则返回为null。remove方法根据removeEntryKey返回的结果e是否为null返回null或e.value。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; 
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    // p 是待删除节点的前置节点
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果哈希表不为空,则根据hash值算出的index下 有节点的话。
    if ((tab = table) != null && (n = tab.length) > 0&&(p = tab[index = (n - 1) & hash]) != null) {
        //node是待删除节点
        Node<K,V> node = null, e; K k; V v;
        //如果链表头的就是需要删除的节点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;//将待删除节点引用赋给node
        else if ((e = p.next) != null) {//否则循环遍历 找到待删除节点,赋值给node
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash && ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //如果有待删除节点node,  且 matchValue为false,或者值也相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)//如果node == p,说明是链表头是待删除节点
                tab[index] = node.next;
            else//否则待删除节点在表中间
                p.next = node.next;
            ++modCount;//修改modCount
            --size;//修改size
            afterNodeRemoval(node);//LinkedHashMap回调函数
            return node;
        }
    }
    return null;
}
复制代码

 clear()方法删除HashMap中所有的元素,这里就不用一个个删除节点了,而是直接将table数组内容都置空,这样所有的链表都已经无法访问,Java的垃圾回收机制会去处理这些链表。table数组置空后修改size为0。

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}
复制代码

总结

HashMap是我写的最长的一篇文章,但是还有很多没有写完,比如它的迭代器(Map是否有序,这个下篇得讲),它的红黑树,实在写不动了,我太难了。也是我菜,红黑树,还没好好学一下,什么左旋,右旋头晕。哈哈 以后有机会会好好补这个坑的。

问大家几个问题

  • HashMap 的容量为啥是2的幂次方
  • HashMap 的扩容伐值为什么是0.75
  • HashMap 它的链表的插入是头插入还是尾插

给大家讲个故事 再Jdk1.7的时候 tomcat 的url上的请求参数 是用HashMap存的 因为它的查询是n(o),但是黑客可以找一些url的参数HashCode相同,几十万个,这样就导致查询非常慢,搞几下就可以把一个网站搞死,后面tomcat 还去找了jdk的人,但是让人家说这不是bug,最后tomcat就自己做了限制 哈哈。

大家如果能对着源码跟着过一遍也好,至少看过源码不是,我们知道HashMap 是线程不安全的,那线程安全的Map是啥,我们知道HashMap是无序的,有序的Map又是啥。各位一起加油吧,路慢慢慢其修远。

版本说明

  • 这里的源码是JDK8版本,不同版本可能会有所差异,但是基本原理都是一样的。

因为博主也是一个开发萌新 我也是一边学一边写 我有个目标就是一周 二到三篇 希望能坚持个一年吧 希望各位大佬多提意见,让我多学习,一起进步。

目录
相关文章
|
7天前
|
数据采集 运维 前端开发
【Java】全套云HIS源码包含EMR、LIS (医院信息化建设)
系统技术特点:采用前后端分离架构,前端由Angular、JavaScript开发;后端使用Java语言开发。
27 5
|
6天前
|
存储 Java 容器
HashMap 的基本操作【集合容器知识回顾 ⑤】
本文介绍了HashMap的基本操作,包括创建对象、添加、获取、删除和替换元素、获取所有key的集合、遍历HashMap,以及如何存储自定义类型键值对,并强调了当使用自定义对象作为键时需要重写equals和hashCode方法以确保正确的行为。
HashMap 的基本操作【集合容器知识回顾 ⑤】
|
2月前
|
Kubernetes Cloud Native Java
云原生之旅:从容器到微服务的演进之路Java 内存管理:垃圾收集器与性能调优
【8月更文挑战第30天】在数字化时代的浪潮中,企业如何乘风破浪?云原生技术提供了一个强有力的桨。本文将带你从容器技术的基石出发,探索微服务架构的奥秘,最终实现在云端自由翱翔的梦想。我们将一起见证代码如何转化为业务的翅膀,让你的应用在云海中高飞。
|
2月前
|
Kubernetes jenkins 持续交付
从代码到k8s部署应有尽有系列-java源码之String详解
本文详细介绍了一个基于 `gitlab + jenkins + harbor + k8s` 的自动化部署环境搭建流程。其中,`gitlab` 用于代码托管和 CI,`jenkins` 负责 CD 发布,`harbor` 作为镜像仓库,而 `k8s` 则用于运行服务。文章具体介绍了每项工具的部署步骤,并提供了详细的配置信息和示例代码。此外,还特别指出中间件(如 MySQL、Redis 等)应部署在 K8s 之外,以确保服务稳定性和独立性。通过本文,读者可以学习如何在本地环境中搭建一套完整的自动化部署系统。
58 0
|
11天前
|
设计模式 Java
结合HashMap与Java 8的Function和Optional消除ifelse判断
`shigen`是一位致力于记录成长、分享认知和留住感动的博客作者。本文通过具体代码示例探讨了如何优化业务代码中的if-else结构。首先展示了一个典型的if-else处理方法,并指出其弊端;然后引入了策略模式和工厂方法等优化方案,最终利用Java 8的Function和Optional特性简化代码。此外,还提到了其他几种消除if-else的方法,如switch-case、枚举行、SpringBoot的IOC等。一起跟随shigen的脚步,让每一天都有所不同!
27 10
结合HashMap与Java 8的Function和Optional消除ifelse判断
|
19天前
|
设计模式 Java 关系型数据库
【Java笔记+踩坑汇总】Java基础+JavaWeb+SSM+SpringBoot+SpringCloud+瑞吉外卖/谷粒商城/学成在线+设计模式+面试题汇总+性能调优/架构设计+源码解析
本文是“Java学习路线”专栏的导航文章,目标是为Java初学者和初中高级工程师提供一套完整的Java学习路线。
174 37
|
5天前
|
传感器 监控 数据可视化
【Java】智慧工地解决方案源码和所需关键技术
智慧工地解决方案是一种新的工程全生命周期管理理念。它通过使用各种传感器、数传终端等物联网手段获取工程施工过程信息,并上传到云平台,以保障数据安全。
26 7
|
6天前
|
存储 Java 容器
HashSet 的基本操作【集合容器知识回顾 ④】
本文介绍了HashSet的基本操作,包括创建和初始化、添加和删除元素、判断元素存在性、获取集合大小、遍历、求交集差集、转换为数组和其他集合类型、比较两个HashSet,以及如何将自定义对象作为HashSet的元素时重写hashCode和equals方法,最后总结了HashSet的性能特点和使用注意事项。
HashSet 的基本操作【集合容器知识回顾 ④】
|
6天前
|
存储 安全 Java
ArrayList的基本操作【集合容器知识回顾 ②】
这篇文章详细介绍了ArrayList的基本操作,包括创建对象、添加和删除元素、获取和更新元素、遍历、判断元素存在性、集合的空值检查、批量操作、转换为数组、截取子集合、查找元素索引、克隆拷贝、清空集合以及容量管理等,同时指出了使用ArrayList时的注意事项,如线程安全性、容量管理、删除元素的性能、遍历时的修改、空值处理和性能优化。
ArrayList的基本操作【集合容器知识回顾 ②】
|
6天前
|
存储 安全 Java
集合概览【集合容器知识回顾 ①】
这篇文章是关于Java集合框架的全面介绍,包括集合的层次结构、常见集合类的特点、如何学习集合框架、泛型的应用、基本操作以及一些常用的集合操作技巧和注意事项。
集合概览【集合容器知识回顾 ①】
下一篇
无影云桌面