HashMap 源码解析Hey 大家好，我是 Shio👋。今天我们将深入探讨 Java 的HashMap源码, HashMap 是Java提供的存放键值对的容器, 其最大的特点是大多情况下可以通过O(1)的时间复杂度通过键来获取值 其底层是由数组 + 链表的组成的，链表主要是用拉链法解决Hash冲突 ， 在JDK1.8之后引入了树化机制 ，在达到一定条件后，会将链表转化为红黑树。 扰动函数HashMap通过调用键的hashCode()方法获取hash值，然后通过扰动函数，使hash值在最后和数组长度取余（(n - 1) & hash）后分布的更为均匀 扰动函数就是为了防止一些实现比较差的hashCode()， 使得使用扰动函数后， 减少哈希碰撞的概率。 static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^：按位异或 // >>>:无符号右移，忽略符号位，空位都以0补齐 return (key == nul ...

一个方法团灭 nSum 问题读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 1. Two Sumopen in new window 1. 两数之和open in new window 🟢 15. 3Sumopen in new window 15. 三数之和open in new window 🟠 167. Two Sum II - Input Array Is Sortedopen in new window 167. 两数之和 II - 输入有序数组open in new window 🟠 18. 4Sumopen in new window 18. 四数之和open in new window 🟠 - 剑指 Offer II 007. 数组中和为 0 的三个数open in new window 🟠 经常刷力扣的读者肯定知道鼎鼎有名的 twoSum 问题，不过除了 twoSum 问题，力扣上面还有 3Sum，4Sum 问题，以后如果想出个 5Sum，6Sum 也不是不可以。 总结来说，这类 nSu ...

算法时空复杂度分析实用指南我以前的文章主要都是讲解算法的原理和解题的思维，对时间复杂度和空间复杂度的分析经常一笔带过，主要是基于以下两个原因： 1、对于偏小白的读者，我希望你集中精力理解算法原理。如果加入太多偏数学的内容，很容易把人劝退。 2、正确理解常用算法底层原理，是进行复杂度的分析的前提。尤其是递归相关的算法，只有你从树的角度进行思考和分析，才能正确分析其复杂度。 鉴于现在历史文章已经涵盖了所有常见算法的核心原理，所以我专门写一篇时空复杂度的分析指南，授人以鱼不如授人以渔，教给你一套通用的方法分析任何算法的时空复杂度。 本文会篇幅较长，会涵盖如下几点： 1、Big O 表示法的几个基本特点。 2、非递归算法中的时间复杂度分析。 3、数据结构 API 的效率衡量方法（摊还分析）。 4、递归算法的时间/空间复杂度的分析方法，这部分是重点，我会用动态规划和回溯算法举例。 废话不多说了，接下来一个个看。 #Big O 表示法首先看一下 Big O 记号的数学定义： O(g(n)) = { f(n): 存在正常量 c 和 n_0，使得对所有 n ≥ n_0，有 0 ≤ ...

算法笔试「骗分」套路首先回答一个问题，刷力扣题是直接在网页上刷比较好还是在本地 IDE 上刷比较好？ 如果是牛客网笔试那种自己处理输入输出的判题形式，一定要在 IDE 上写，这个没啥说的，但像力扣这种判题形式，我个人偏好直接在网页上刷，原因有二： 1、方便 因为力扣有的数据结构是自定的，比如说 TreeNode，ListNode 这种，在本地你还得把这个类 copy 过去。 而且在 IDE 上没办法测试，写完代码之后还得粘贴到网页上跑测试数据，那还不如直接网页上写呢。 算法又不是工程代码，量都比较小，IDE 的自动补全带来的收益基本可以忽略不计。 2、实用 到时候面试的时候，面试官给你出的算法题大都是希望你直接在网页上完成的，最好是边写边讲你的思路。 如果平时练习的时候就习惯没有 IDE 的自动补全，习惯手写代码大脑编译，到时候面试的时候写代码就能更快更从容。 之前我面快手的时候，有个面试官让我 实现 LRU 算法，我直接把双链表的实现、哈希链表的实现，在网页上全写出来了，而且一次无 bug 跑通，可以看到面试官惊讶的表情😂 我秋招能当 offer 收割机，很大程度上就是因为手写算法 ...

Git原理之最近公共祖先读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 1644. Lowest Common Ancestor of a Binary Tree IIopen in new window🔒 1644. 二叉树的最近公共祖先 IIopen in new window🔒 🟠 1650. Lowest Common Ancestor of a Binary Tree IIIopen in new window🔒 1650. 二叉树的最近公共祖先 IIIopen in new window🔒 🟠 1676. Lowest Common Ancestor of a Binary Tree IVopen in new window🔒 1676. 二叉树的最近公共祖先 IVopen in new window🔒 🟠 235. Lowest Common Ancestor of a Binary Search Treeopen in new window 235. 二叉搜索树的最近公共祖先open in ...

东哥带你刷二叉树（后序篇）本文是承接 东哥带你刷二叉树（纲领篇） 的第四篇文章，主要讲二叉树后序位置的妙用，复述下前文关于后序遍历的描述： 前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。 那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。 多说无益，我们直接看题，这是力扣第 652 题「寻找重复的子树open in new window」： 652. 寻找重复的子树 | 力扣 open in new window | LeetCode open in new window |给你一棵二叉树的根节点 root ，返回所有 重复的子树 。对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复&n ...

东哥带你刷二叉搜索树（构造篇）读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 95. Unique Binary Search Trees IIopen in new window 95. 不同的二叉搜索树 IIopen in new window 🟠 96. Unique Binary Search Treesopen in new window 96. 不同的二叉搜索树open in new window 🟠 Info 在开头先打个广告，我的 手把手刷二叉树课程open in new window 按照公式和套路讲解了 150 道二叉树题目，只需一顿饭钱，就能手把手带你刷完二叉树分类的题目，迅速掌握递归思维，让你豁然开朗。我绝对有这个信心，信不信，可以等你看完我的二叉树算法系列文章再做评判。 之前写了两篇手把手刷 BST 算法题的文章，第一篇 讲了中序遍历对 BST 的重要意义，第二篇 写了 BST 的基本操作。 本文就来写手把手刷 BST 系列的第三篇，循序渐进地讲两道题，如何计算所有有效 BST。 第一道题是力扣第 ...

东哥带你刷二叉树（序列化篇）读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 297. Serialize and Deserialize Binary Treeopen in new window 297. 二叉树的序列化与反序列化open in new window 🔴 - 剑指 Offer 37. 序列化二叉树open in new window 🔴 - 剑指 Offer II 048. 序列化与反序列化二叉树open in new window 🔴 Info 在开头先打个广告，我的 手把手刷二叉树课程open in new window 按照公式和套路讲解了 150 道二叉树题目，只需一顿饭钱，就能手把手带你刷完二叉树分类的题目，迅速掌握递归思维，让你豁然开朗。我绝对有这个信心，信不信，可以等你看完我的二叉树算法系列文章再做评判。 本文是承接 东哥带你刷二叉树（纲领篇） 的第三篇文章，前文 东哥带你刷二叉树（构造篇） 带你学习了二叉树构造技巧，本文加大难度，让你对二叉树同时进行「序列化」和「反序列化」。 要说序 ...

归并排序详解及应用读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 315. Count of Smaller Numbers After Selfopen in new window 315. 计算右侧小于当前元素的个数open in new window 🔴 327. Count of Range Sumopen in new window 327. 区间和的个数open in new window 🔴 493. Reverse Pairsopen in new window 493. 翻转对open in new window 🔴 912. Sort an Arrayopen in new window 912. 排序数组open in new window 🟠 一直都有很多读者说，想让我用 框架思维 讲一讲基本的排序算法，我觉得确实得讲讲，毕竟学习任何东西都讲求一个融会贯通，只有对其本质进行比较深刻的理解，才能运用自如。 本文就先讲归并排序，给一套代码模板，然后讲讲它在算法问题中的应用。阅读本文前我希望你 ...