专栏首页每日分享java架构小知识HashMap中add()方法的源码学习

HashMap中add()方法的源码学习

一、HashMap底层数据结构

  • JDK1.7及之前:数组+链表
  • JDK1.8:数组+链表+红黑树

HashMap中实际是维护了一个Node数组,用来存储数据,下面看一下Node源码:

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

简单介绍一下Node中的属性:

1:hash值

2:key-键

3:value-值

4:nest-这个属性值的类型是Node类型,意思是当前节点的下一个节点,从这个属性可以看出在数组的结构上又结合和链表,至于红黑树会在添加数据的时候动态往红黑树转变

二、HashMap add()

  分析一波add()源码,上代码:

//hash值和元素的hashCode()方法相关
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是否为null,如果是,则哈希表未初始化,就对其初始化,初始化大小会默认定位16,当数组储存量 length > table.length*0.75 时,数组会扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(n - 1) & hash 使用数组长度和hash值做与运算,计算出当前节点应该储存的位置,如果该位置没有元素,就存储元素
        //(n - 1) & hash 运算相当于 hash % n,但是hash后按位与 n-1,比%模运算取余要快
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            
                
            /*
                存入的元素和以前的元素比较哈希值
                    如果哈希值不同,会继续向下执行,把元素添加到集合
                    如果哈希值相同,会调用对象的equals()方法比较
                        如果返回false,会继续向下执行,把元素添加到集合
                        如果返回true,说明元素重复,不存储
            */
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果数组中的链表已经转为树结构,则使用树类型的put
            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;
                    }
                    // 如果hash值相同,equals也返回true,则表示为相同对象,直接e = p.next覆盖
                    // 如果hash值相同,equals不同,则判定为不一样的对象,则追加新节点到尾部
                    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
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 空方法,没实现,LinkedHashMap的时候有用到
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果新增一个元素后,大小超过了 容量 * 负载因子,则需要扩容
        if (++size > threshold)
            resize();
        // 空方法,没实现
        afterNodeInsertion(evict);
        return null;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 并发编程的基础

      对于并发编程这块知识点的掌控一直不是很好,基本都是停留在使用synchronized阶段,于是决定开一博客专题记录知识点。

    会说话的丶猫
  • 线程池的实现原理分析

    在 Java 中,如果每个请求到达就创建一个新线程,创建和销毁线程花费的时间和消耗的系统资源都相当大,甚至可能要比在处理实际的用户请求的时间和资源要多的多。如果...

    会说话的丶猫
  • java设计模式-单例模式

    其定义为:单例模式,是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例的特殊类。通过单例模式可以保证系统中,应用该模式的一个类只有一个实例。即一个类...

    会说话的丶猫
  • JDK容器学习之HashMap (一) : 底层存储结构分析

    底层数据结构 首先通过源码,类中的field如下, transient Node<K,V>[] table; transient Set<Map.Entry<...

    一灰灰blog
  • BAT面试必问HashMap源码分析

    HashMap 主要用来存放键值对,它基于哈希表的Map接口实现,是常用的Java集合之一。

    美的让人心动
  • 程序猿的日常——HashMap的相关知识

    背景知识 ? 哈希冲突 哈希是指通过某种方法把数据转变成特定的数值,数值根据mod对应到不同的单元上。比如在Java中,字符串就是通过每个字符的编码来计算、数字...

    用户1154259
  • hash冲突解决和javahash冲突解决

    线性,平方显然很容被人猜出规律,所以最终是随机,那么是不是存在随机会出现取模的值相等的情况?

    ydymz
  • Java内功系列-HashSet是如何保证元素不重复的

    我们都知道HashSet存放的元素是不允许重复的,那么HashSet又是是如何保证元素不可重复的,你知道吗?

    一个程序员的成长
  • hashMap怎么保证hash一致性的

    学Java的都知道hashMap的底层是“链表散列”的数据结构也也可以说是hash表。在put的实话先根据key的hashcode重新计算hash值的,而我们又...

    凯哥Java
  • 大数据计数原理1+0=1这你都不会算(一)No.47

    hello哈,大家是不是好久没见到我啦?我也是一直在摸索小伙伴们喜欢看到什么东西,不喜欢看什么东西,还请大家多多支持。为了表示感谢。小蕉在这给你们一鞠躬,二鞠躬...

    大蕉

扫码关注云+社区

领取腾讯云代金券