萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

HashMap源码学习(持续更新)

发表于 2022-09-28 | 分类于 Java SE | 0 | 阅读次数 74

成员变量

待补充

成员方法

put方法

/**
 * 外部调用
 * @param key 传入的key
 * @param value 传入的value
 * @return 如果传入的key值有对应的value存在,则返回旧值,否则返回null
 */
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}


/**
 * 计算hash
 * @param key 传入的key
 * @return 计算过后的hash值
 */
static final int hash(Object key) {
    int h;
    // key为空返回0,否则将hashCode和自身的高16位进行异或后的结果返回
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * put核心逻辑方法
 * @param hash key的hash值
 * @param key 键
 * @param value 值
 * @param onlyIfAbsent 当为true时将不改变已存在的value的值
 * @param evict 当为false时,hash表处于创建模式
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // tab指向table
    Node<K,V>[] tab; 
    // p为hash命中的数组节点
    Node<K,V> p; 
    // n为tab的长度,i为哈希表的下标范围0~length-1
    int n, i;
    // 给tab赋值并判断table是否为空,如果为空将其初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 初始化table然后给n赋值
        n = (tab = resize()).length;
    // 开始put核心逻辑
    // hash值对表长度取余计算出数组下标,然后判断是否hash碰撞
	if ((p = tab[i = (n - 1) & hash]) == null)
        // 没有碰撞,直接给当前数组节点赋值
        tab[i] = newNode(hash, key, value, null);
    else {
        // 开始hash碰撞后的处理
        // e为需要覆盖的节点,它和p不同,p是在哈希数组中的节点,
        // 但是e可能是链表或者树中的节点都有可能,而且它要被覆盖掉
        Node<K,V> e;
        // k为hash碰撞节点的key
        K k;
        // 判断:碰撞节点p的哈希值和当前传入的hash值是否相等?key的地址是否相同或者key的equals方法比较是否为true?
        // 说白了就是判断key是否相同
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果条件成立,则说明key是同一个key,需要将value覆盖掉,后续只要将老值返回即可
            e = p;
        // 如果当前节点是一颗红黑树
        else if (p instanceof TreeNode)
            // 将当前节点强转成红黑树然后调用红黑树的方法将节点接在树上,如果覆盖返回的e就是老节点,如果不覆盖,返回的e就是null
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 当前节点不是树而是正常的Node节点,就需要将当前值和链表中的值一一对比key,
        // 相当于重复if中的操作,如果链表中不存在相同的key,就需要在链表末尾创建一个新节点
        else {
            // 循环遍历链表
            for (int binCount = 0; ; ++binCount) {
                // 将next节点赋值给e,并判断节点是否为空,如果为空就创建新节点接在下边
                if ((e = p.next) == null) {
                    // 创建新节点接在下边
                    p.next = newNode(hash, key, value, null);
                    // 判断链表节点个数是否大于树化的阈值
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        // 树化
                        treeifyBin(tab, hash);
                    break;
                }
                // 比较当前节点和传入的key是否一样
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    // 如果一样直接退出(注意e的value在后续会被覆盖)
                    break;
                // 指针后移
                p = e;
            }
        }
        // 官方注释:existing mapping for key. 译为存在映射的key。意思就是当前坑位有人,需要给他覆盖掉
        if (e != null) {
            // 先把当前的(也就是旧节点)值拿出来
            V oldValue = e.value;
            // 只有当onlyIfAbsent为fales并且节点不为空才覆盖
            if (!onlyIfAbsent || oldValue == null)
                // 将value覆盖掉
                e.value = value;
            afterNodeAccess(e);
            // 返回老值
            return oldValue;
        }
	}
    ++modCount;
    // 当HashMap的长度大于阈值
    if (++size > threshold)
        // 扩容
        resize();
    afterNodeInsertion(evict);
    // 没有碰撞时返回为null
    return null;
}
# Java
力扣第24题-两两交换链表中的节点
力扣第25题-K个数组反转链表
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

83 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持