Alrisha

在 HashMap 中，table 容量初始值为 16 。且每次插入新元素后，如果需要扩容，都是通过 << 1 运算将容量乘以 2。那么什么时候会出现容量可能不是 2 的幂次方的情况呢？ 通过 putAll 方法将一个 Map 的所有元素添加到另一个 Map 中。这时 HashMap 的容量不仅很大概率不是 2 的幂次方，而且不一定能够通过一次 << 1 运算得到合适的容量。例如，原始 Map 容量为 4，添加的 Map 容量为 8，那么扩容后容量 $table.length = 4 << 1 = 8$，而需要的容量为 12，远不能满足需求。 通过 IO 流反序列化 HashMap 。基本问题和 putAll 一样，都是一次左移无法满足需求 那么 HashMap 就应该设计一个算法，计算这种一次左移无法得到的容量大小。这个问题换句话来说，就是： 给定一个 int 类型的整数 n，如何求出不小于它的最接近的 2 的整数幂 m，比如给定 10 得出 16，给定 25 得出 32？ 直观地，我们会想到通过对数换底公式 $log_ ...

HashMap 是 Java 中常用的一种数据结构，它实现了 Map 接口，用于存储键值对。HashMap 的底层实现原理是数组和链表/红黑树，通过哈希函数将键映射到数组中的某个位置，如果位置上已经有元素，则使用链表进行存储。 HashMap 的扩容机制是 HashMap 中的重要的算法，它通过调整 HashMap 的容量来控制 HashMap 的大小，以减少空间浪费和提高查询效率。一般来说，每次扩容，HashMap 存储链表/红黑树的数组的长度都会变为 2 倍。在 HashMap 实现中，这个数组是一个成员变量 table。 为什么要这么设计？我们首先要知道一个好的 Hash 函数至少应该满足什么条件： 均匀分布 ：经过哈希函数的计算，每个元素应该尽可能均匀地分布到数组中。具体地说，要保证每个 table 下标都有可能命中 快速计算 ：哈希函数的计算应该尽可能高效 离散分布 ：哈希函数的计算结果应该尽可能的离散，减少碰撞。具体地说，要保证每个 table 下标中的元素数量都差不多 带着这些条件，我们看看 Java 的 HashMap 具体是怎么实现的。 以下源 ...

什么是 OAuth 2.0 ？为什么我们需要它？OAuth 2.0 是一个开放标准，允许用户授权第三方应用访问他们存储在另外的服务提供者上的信息，而不需要将用户名和密码提供给第三方应用。 一个最简单的例子就是支付宝的免密支付。例如我在订阅微博会员按月自动续费服务时，需要获得支付宝授权，因为本质上这个操作是用户在 A 服务（微博）上授权 B 服务（支付宝）的数据，而 A B 服务之间并没有直接的信任关系。 那么问题来了，在支付宝的研发侧视角看，我应该怎么确保这个微博用户真的请求了他自己的支付宝账户数据？微博对我而言是一个不可信的第三方，我怎么知道它没有伪造请求？这需要我们有一种机制来确保用户的授权请求是合法的，这也就是 OAuth 2.0 的主要作用。 OAuth 2.0 架构摘自 RFC 6749： 资源映射，以上文支付宝授权为例： 资源拥有者：C 端用户 客户端：微博 认证服务器：支付宝认证服务器/第三方可信认证服务器 资源服务器：支付宝服务接口 资源：支付宝用户信息、支付宝免密续费服务等 具体流程如下： 用户打开客户端以后，客户端要求用户给予授权。 用户同意给予 ...

有这样一个场景，我在 Windows 主机 A 上，想要通过 SSH 连接到 Windows 主机 B 上的 WSL。 1234主机A (Windows) -----> 主机B (Windows) | V WSL (在主机B上) Google 了一圈，找到了一个比较靠谱的方案（原文）： Latest WSL2 has systemctl support and can automatically map sshd’s connection to the Windows host. No need to redirect port. Make sure Windows OpenSSH works. In windows, run wsl --update to make sure use latest WSL. In WSL, run sudo apt-get install openssh-server to in ...

时间来到 5 月份，经历了 10 家公司 21 场面试的洗礼，我持续两个月的高强度暑期实习面试也总算可以说是告一段落了。这篇文章的主要目的是记录我这两个月以来的面试经历和总结感悟，既为我后续的职业规划做参考，也希望能稍微帮上一些有缘看到它的朋友。如果各位对我的简历感兴趣，也可以点击页面右上角的“关于”查看。 以下部分是我对我这几轮实习面试总体的总结，如果希望直接看具体面经请点这里。 总结 公司 岗位/部门 进度 备注 阿里云 ECS 弹性计算 ❌ 主动拒了二面 提前批，和中间件部门冲突 腾讯 TEG 广告工程部 ❌ 一面挂 腾讯 TEG 腾讯网络研发部 ✔ OC 阿里云 云原生中间件 ❌ 三面挂 美团 优选事业部 ❌ 一面挂 美团 SaaS ✔ OC 淘天 阿里妈妈 ❌ 三面挂 快手 基础平台 ❌ 一面挂 阿里控股 资采产品技术部 ❌ 主动拒了 HR 面 阿里云 创新业务中心 ✔ OC 蚂蚁 - ❌ 简历挂 蚂蚁认为我的简历适合做架构和中间件，但是蚂蚁的架构部门今年似乎不怎么招实习生了（也很有可能是我还不够格 ...

组合数 C(n, k)表示从 n 个元素中选择 k 个元素的组合数，其公式为： $$C(n, k) = \frac{n!}{k!(n-k)!}\tag{1}$$ 其中”!”表示阶乘，即 $n! = n * (n-1) * (n-2) * … * 1$。 然而，直接使用这个公式编写代码计算组合数可能会导致溢出，因为阶乘的值增长非常快。因此，我们通常使用更有效的方法来计算组合数。 k 分数分解我们可以通过变换公式 (1) 得到一个新的适合程序运算的公式，计算过程如下： $$C(n, k) = \frac{n!}{k!(n-k)!} \= (\frac{1}{1} * \frac{1}{2} * \frac{1}{3} * … * \frac{1}{k}) * \frac{n!}{(n-k)!}$$ 展开 $\frac{n!}{(n-k)!}$ 得到： $$C(n, k) = (\frac{1}{1} * \frac{1}{2} * \frac{1}{3} * … * \frac{1}{k}) * [(n-k+1) * (n-k+2) * … ...

本文章系列未来计划持续更新，把我在学习/实习/工作中遇到的相关实际案例记录在这里 系列综述： 服务器突然变得卡顿，怎么办？（1）综述 本文内容基于美团技术博客文章 《Java 中 9 种常见的 CMS GC 问题分析与解决》 算是转载性质的章节。尽管在美团博客中提到的是 CMS GC，但是对于其他 GC 实现也是很有参考意义的。 另外我也推荐一篇最近在看的关于 ZGC 的文章 《ZGC 介绍》 ，这篇文章很好的让我了解了 JDK 最新的 GC 实现方法和思想。 关于 Java 主要的三大 GC 实现的介绍，可以看以下的系列文章，我认为都是干货满满的： 新一代 Java 垃圾回收神器：ZGC 为什么 G1 能够替代 CMS 回收器？ 彻底弄懂了 CMS 收集器原理，这个轮子造的真值！ 真的是 GC 引发的问题吗？首先需要确定的是，在一次 GC 问题处理的过程中，如何判断是 GC 导致的故障，还是系统本身引发 GC 问题？ 在一个系统故障问题中，我们通常会得到下面四个表象指标： GC 耗时增大 线程 Block 增多 慢查询增多 CPU 负载高 一般来说，可 ...

本文章系列未来计划持续更新，把我在学习/实习/工作中遇到的相关实际案例记录在这里 系列目录： 综述：本文章 Java GC 导致的卡顿：https://alrisha.cn/2024/04/bd9408a6.html 这是一道经典的面试场景题，但也可以说是实际开发过程中最经常遇到的问题之一。实际上，这个问题问的是当服务器出现不可用情况时，应当如何快速排查、定位问题并解决问题。 可能的卡顿原因对于卡顿原因，一般来说可以从以下几个大方考虑： CPU : 当 CPU 占用过高时，服务器自然会发生卡顿。 CPU 密集型任务 ：如果运行的服务是 CPU 密集型的任务，那么 CPU 资源占用是不可避免的，此时为了确保服务器自身的可用性，可以对这个 CPU 密集型任务做一定的 CPU 资源隔离（限制核数、限制抢占的时间片等） 并发竞争 ：如果发生比较严重的多线程竞争行为，线程频繁切换上下文也会导致 CPU 占用过高 持续占用 ：忙等待、死循环、JVM Full GC 等操作，会导致线程长时间占用并浪费 CPU 资源，具体也体现为 CPU 占用过高 恶意软件 ：（小概率 ...

“实现三个线程交替打印 ABC”是一道面试经典问题。网络上实际上也有了很多的解决方案，包括通过 synchronized 、Semaphore 、ReentrantLock 或是 CyclicBarrier 等方式实现。 这里我总结一下这些方案的特点，并提出几种我自己的代码实现。 以下实现实际上在原问题上更近一步：结果必须输出特定数量的 ABC 字符串 问题分析综合所有方案来看，本问题本质上是对一个状态机进行建模，也即不同的线程需要实现如下状态转换过程： 1A -> B -> C -> A -> B -> C -> A ... 我们知道，线程并行时执行顺序是不确定的，因此需要通过锁机制确保以上的状态转移过程。思路应该是： 线程 A 首先获取锁 L 打印 A，此时线程 B 和 C 获取不到锁 L 被阻塞； 线程 A 打印任务结束，释放锁 L，此时 线程 B 需要拿到锁 L 打印 B ，我们需要确保线程 C 不能在此时获取锁； 线程 B 打印结束，线程 C 拿到锁 L ，线程 A 不能在此时获取锁； 以此类推… 因此，主要难点实际上在于，如何保 ...

解决伪共享(False-Sharing)问题：最大化利用你的 CPU 缓存这篇文章是先前我在分布式 ID 生成算法 SnowFlake 及其 Go 实现中提到的伪共享（False-Sharing） 问题的延伸，主要是为了更好地理解并解决伪共享问题，以便通过最大化使用 CPU 缓存来增强性能。 什么是伪共享？当代 CPU 普遍采用多级缓存的架构，例如： 1L1 Cache -> L2 Cache -> L3 Cache -> RAM -> Disk 其中，缓存读写速度（以及硬件成本）依次递减，而容量则依次递增。当 CPU 访问某个内存地址时，会先从 L1 Cache 开始查找，如果没有找到，再从 L2 Cache 查找，以此类推。如果在 L1 Cache 中找到了，那么就会直接返回，否则就会将 L2 Cache 中的数据拷贝到 L1 Cache 中，再返回。 想要让程序运行的更快，就需要尽可能地利用低级别的缓存。CPU 缓存是由缓存行组成的，一个缓存行一般是 64 个字节，CPU 读取数据是以缓存行为单位的读取，这意味着即使是读 1 个字节的数据，CPU 也要读 ...