文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载导读本文以 CodeGuide 仓库中《数学离一个程序员有多近》一文为主体系统讲解数学与 Java 编程的内在联系——从 2004 年谷歌 101 公路招聘谜题到《编程之美》中1 出现的次数的 for 循环与数学算法对决再到 HashMap 扰动函数、ThreadLocal 斐波那契散列、梅森旋转算法等隐藏在 JDK 源码中的数学应用。读完本文你将理解数学如何支撑数据结构与算法设计并能结合仓库源码与中间件实例把散列、寻址等数学能力落地到数据库路由等真实场景中。一、前言代码是对数学逻辑的具体实现数学离程序员有多近ifelse 也好、for 循环也罢代码可以说就是对数学逻辑的具体实现。所以敲代码的程序员几乎就离不开数学难易不同而已。那数学不好就写不了代码吗不一样可以写代码可以写出更多的CRUD出来。但你不要总觉得是产品需求简单所以你的实现过程才变成了增删改查往往也是因为你还不具备可扩展、易维护、高性能的代码实现方案落地能力才使得你小小年纪写出了更多的CRUD与一锥子买卖的小作坊相比大厂和超级大厂更会注重数学能力。1. 2004 年谷歌的 101 公路数学招聘谜题2004 年在硅谷的交通动脉 101 公路上突然出现一块巨大的广告牌上面是一道数学题{e 的连续数字中最先出现的 10 位质数}.com。广告中的 e 是数学常数自然对数的底数无限不循环小数。这道题的意思就是找出 e 中最先出现的 10 位质数然后可以得出一个网址。进入这个网址会看到 Google 为你出的第二道数学题成功解锁这步 Google 会告诉你我们或许是志同道合的人你可以将简历发到这个邮箱我们一起做点改变世界的事情。计算 e 值可以通过泰勒公式推导出来e^x ≈ 1 x x^2/2! x^3/3! …… x^n/n!。推导计算过程还包括埃拉托色尼筛选法the Sieve of Eratosthenes、线性筛选法的使用。感兴趣的小伙伴可以用代码实现下。这道题把找质数这一数论问题直接转化为了一道招聘门槛也恰好印证了仓库中《程序员数学 v2.0》开篇的总结有数学才有编程之美代码是对数学逻辑的具体实现有了数学支撑才让编程逻辑具有灵魂详见 docs/md/algorithm/logic/math/math.md。二、把代码写好的四步数据结构、算法逻辑、设计模式、系统架构业务提需求、产品定方案、研发做实现。最终这个系统开发的怎么样是由三方共同决定的小傅哥用一个盖房子的比喻把代码工程的分层讲得非常透彻地基挖的不好楼就盖不高砖头摆放不巧楼就容易倒水电走线不妙楼就危险了格局设计不行楼就卖不掉这里的地基、砖头、水电、格局对应的就是数据结构、算法逻辑、设计模式、系统架构。从下到上相互依赖、相互配合只有这一层做好下一层才好做数据结构高矮胖瘦、长宽扁细数据的存放方式是一套程序开发的核心基础。不合理的设计往往是从数据结构开始的哪怕你仅仅是使用数据库存放业务信息也一样会影响到将来各类数据的查询、汇总等实现逻辑的难易。算法逻辑是对数据结构的使用合适的数据结构会让算法实现过程降低时间复杂度。可能你现在的多层 for 循环在合适的算法过程下能被优化为更简单的方式获取数据。注意算法逻辑实现并不一定就是排序、归并还有你实际业务的处理流程。设计模式可以这么说不使用设计模式你一样能写代码。但你愿意看到满屏幕的 ifelse 判断调用还是喜欢像膏药一样的代码粘贴来复制去设计模式这套通用场景的解决方案就是为你剔除掉代码实现过程中的恶心部分让整套程序更加易维护、易扩展。就是开发完一个月你看它你还认识系统架构描述的是三层 MVC还是四层 DDD。MVC 是我们经常用的大家都熟悉DDD 无非就是家里多了个书房把各自属于哪一个屋子的摆件规整到各自屋子里。那么乱放是什么效果呢就是自动洗屁屁马桶给按到厨房了再贵也格楞子好那么我们再延展下如果你的卫生间没有流出下水道咋办这个位置的数据结构就是设计缺失的而到后面再想扩展就难了吧所以研发在承接业务需求、实现产品方案的时候压根就不只是在一个房子的三居或者四居格局里开始随意码砖。没有合理的数据结构、没有优化的算法逻辑、没有运用的设计模式最终都会影响到整个系统架构变得臃肿不堪调用混乱。在以后附加、迭代、新增的需求下会让整个系统问题不断地放大当你想用重构时就有着千丝万缕般的调用关系——重构就不如重写了三、for 循环没算法快《编程之美》1 出现的次数问题在《编程之美》一书中有这样一道题求 1~n 中1 出现的次数。比如1~101 出现了两次。这一节我们分别用暴力 for 循环和数学规律算法两种方式实现直观对比它们的耗时差异。1. for 循环实现long startTime System.currentTimeMillis(); int count 0; for (int i 1; i 10000000; i) { String str String.valueOf(i); for (int j 0; j str.length(); j) { if (str.charAt(j) 49) { count; } } } System.out.println(1的个数 count); System.out.println(计算耗时 (System.currentTimeMillis() - startTime) 毫秒);使用 for 循环的实现过程很好理解就是往死了循环。之后把循环到的数字按照字符串拆解判断每一位是不是数字是就 1。这个过程很简单但是时间复杂度很高——对 1 千万个数逐一遍历、逐位拆解计算量呈线性甚至超线性增长。2. 算法逻辑实现其实我们能发现这个 1 的个数在 100、1000、10000 中是有规则的循环出现的。11、12、13、14 或者 21、31、41、51以及单个的 1 出现。最终可以得出通用公式abcd...(abc1)*1(ab1)*10(a1)*100(1)*1000...abcd 代表位数。另外在实现的过程还需要考虑比如不足 100 等情况例如 98、1232 等。实现过程long startTime System.currentTimeMillis(); int num 10000000, saveNum 1, countNum 0, lastNum 0; int copyNum num; while (num ! 0) { lastNum num % 10; num / 10; if (lastNum 0) { // 如果是0那么正好是少了一次所以num不加1了 countNum num * saveNum; } else if (lastNum 1) { // 如果是1说明当前数内少了一次所以num不加1而且当前1所在位置 // 有1的个数就是去除当前1最高位剩下位数的个数。 countNum num * saveNum copyNum % saveNum 1; } else { // 如果非1非0.直接用公式计算 // abcd...(abc1)*1(ab1)*10(a1)*100(1)*1000... countNum (num 1) * saveNum; } saveNum * 10; } System.out.println(1的个数 countNum); System.out.println(计算耗时 (System.currentTimeMillis() - startTime) 毫秒);这段算法的核心思想是逐位统计从个位到最高位用saveNum1、10、100……标记当前统计的位权lastNum取当前位的数字num是去掉当前位后的高位copyNum保留原始值用于计算低位部分。分三种情况累加当前位 lastNum累加规则说明0countNum num * saveNum高位出现 1 的次数就是num * saveNum1countNum num * saveNum copyNum % saveNum 1高位贡献之外还要加上当前位为 1 时的低位部分其他countNum (num 1) * saveNum直接用公式(num 1) * saveNum例如计算 1~10个位为 0贡献1 * 1 1十位为 1贡献0 * 10 10 % 10 1 1合计2与1 和 10 中出现两次完全吻合。整个算法的时间复杂度只有 O(log n)与 n 的大小无关。在《编程之美》一书中还不只这一种算法感兴趣的小伙伴可以查阅但自己折腾实现后的兴奋感更强哦3. 耗时曲线对比按照两种不同方式的实现逻辑来计算 1000、10000、10000 到一个亿求 1 出现的次数对比两种方式的耗时曲线for 循环随着数量的不断增大后已经趋近于无法使用了。算法逻辑依靠的是计算公式所以无论增加多少基本都会在 1~2 毫秒内计算完成。那么你的代码中是否也有类似的地方如果使用算法逻辑配合适合的数据结构是否可以替代一些 for 循环的计算方式来使整个实现过程的时间复杂度降低。四、Java 中的算法运用藏在 JDK 源码里的数学在 Java 的 JDK 实现中有很多数学知识的运用包括数组、链表、红黑树的数据结构以及相应的实现类 ArrayList、LinkedList、HashMap 等。当你深入地了解这些类的实现后会发现它们其实就是使用代码来实现数学逻辑而已就像你使用数学公式来计算数学题一样。接下来就介绍几个隐藏在代码中的数学知识。1. HashMap 的扰动函数扰动函数公式static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }描述以上这段代码是 HashMap 中用于获取 hash 值的扰动函数实现代码。HashMap 通过哈希值与桶定位坐标那么直接获取哈希值就好了这里为什么要做一次扰动呢作用为了证明扰动函数的作用可以使用 10 万单词计算哈希值分布在 128 个格子里之后把这 128 个格子中的数据做图表展示。从实现数据可以看到在使用扰动函数后曲线更加平稳了。那么也就是扰动后哈希碰撞会更小。用途当你有需要把数据散列分散到不同格子或者空间时又不希望有太严重的碰撞那么使用扰动函数就非常有必要了。比如你做的一个数据库路由在分库分表时也是尽可能的要做到散列的。为什么需要扰动从源码层面看HashMap 默认初始容量是DEFAULT_INITIAL_CAPACITY 1 416而 hashCode 的取值范围是[-2147483648, 2147483647]有将近 40 亿的长度谁也不能把数组初始化的这么大。所以获取的哈希值需要与数组长度做取模运算得到一个下标值。(h key.hashCode()) ^ (h 16)把哈希值右移 16 位正好是它长度的一半再与原哈希值做异或运算这样就混合了原哈希值中的高位和低位增大了随机性让数据元素更加均衡地散列减少碰撞。这段源码在仓库 面经手册 · 第3篇《HashMap核心知识扰动函数、负载因子、扩容链表拆分深度学习》 中有完整的推导、实验数据与 Excel 图表素材说明更深入的插入、查找、扩容源码分析可以参考 面经手册 · 第4篇《HashMap数据插入、查找、删除、遍历源码分析》。扰动函数在数据库路由中的真实落地仓库 基于 Hash 散列数据库路由组件设计 一文把 HashMap 的扰动函数直接移植到了分库分表的路由计算上// 扰动函数加强散列 int idx (size - 1) (dbKeyAttr.hashCode() ^ (dbKeyAttr.hashCode() 16)); // 库表索引 int dbIdx idx / dbRouterConfig.getTbCount() 1; int tbIdx idx - dbRouterConfig.getTbCount() * (dbIdx - 1);在这套路由组件中一条数据被 AOP 切面拦截后先通过扰动函数计算散列索引再拆分出库索引与表索引最后通过ThreadLocal传递数据源信息DBContextHolder.setDBKey/setTBKey。这就是学完源码造火箭的典型案例HashMap 源码里的数学方法直接决定了分库分表后数据能否均匀散列否则数据全部集中在某个库的某张表就失去了分库分表的意义。2. 斐波那契Fibonacci散列法ThreadLocal 的神奇 0x61c88647描述在 ThreadLocal 类中的数据存放使用的是斐波那契Fibonacci散列法 开放寻址。之所以使用斐波那契数列是为了让数据更加散列减少哈希碰撞。具体来自数学公式的计算求值公式f(k) ((k * 2654435769) X) Y对于常见的 32 位整数而言也就是f(k) (k * 2654435769) 28。作用与 HashMap 相比ThreadLocal 的数据结构只有数组并没有链表和红黑树部分。而且经过测试验证斐波那契散列的效果更好也更适合 ThreadLocal。用途如果你的代码逻辑中需要存储类似 ThreadLocal 的数据结构又不想有严重哈希碰撞那么就可以使用斐波那契Fibonacci散列法。其实除此之外还有除法散列法、平方散列法、随机数法等。神秘的数字是怎么来的查看 ThreadLocal 源码设置元素时有一段计算哈希值的代码private static final int HASH_INCREMENT 0x61c88647; private static int nextHashCode() { return nextHashCode.getAndAdd(HASH_INCREMENT); }其实这是一个哈希值的黄金分割点也就是0.618。计算方式如下// 黄金分割点(√5 - 1) / 2 0.6180339887 1.618:1 1:0.618 System.out.println(BigDecimal.valueOf(Math.pow(2, 32) * 0.6180339887).intValue()); // -1640531527学过数学都应该知道黄金分割点是(√5 - 1) / 2取 10 位近似0.6180339887。之后用2^32 * 0.6180339887得到的结果是-1640531527也就是 16 进制的0x61c88647。这个数呢也就是这么来的。也就是说Josh Bloch和Doug Lea两位大神选择使用斐波那契数列计算哈希值是为了更好地散列、减少哈希碰撞。详细的黄金分割推导、散列验证代码与开放寻址原理在仓库 面经手册 · 第12篇《面试官ThreadLocal 你要这么问我就挂了》 中有完整展开仓库 算法逻辑 · 斐波那契 一文还给出了循环、递归、比奈公式三种斐波那契计算方式并对比了除法散列、乘法散列、斐波那契散列等不同散列算法的适用场景。值得思考的边界斐波那契散列虽然让 ThreadLocal 的数据分布极其均匀但仓库 斐波那契篇 特别指出——它并不能用于数据库路由算法因为斐波那契散列不满足严格的雪崩标准SAC而数据库路由通常采用的是整数模除法散列。这也说明数学方法没有绝对的优劣只有适用场景的匹配。3. 梅森旋转算法Mersenne Twister// Initializes mt[N] with a simple integer seed. This method is // required as part of the Mersenne Twister algorithm but need // not be made public. private final void setSeed(int seed) { // Annoying runtime check for initialisation of internal data // caused by java.util.Random invoking setSeed() during init. // This is unavoidable because no fields in our instance will // have been initialised at this point, not even if the code // were placed at the declaration of the member variable. if (mt null) mt new int[N]; // ---- Begin Mersenne Twister Algorithm ---- mt[0] seed; for (mti 1; mti N; mti) { // 注原文此处为 ^按位异或即 // mt[mti] (MAGIC_FACTOR1 * (mt[mti-1] ^ (mt[mti-1] 30)) mti); mt[mti] (MAGIC_FACTOR1 * (mt[mti-1] ^ (mt[mti-1] 30)) mti); } // ---- End Mersenne Twister Algorithm ---- }梅森旋转算法Mersenne Twister是一个伪随机数发生算法。由松本真和西村拓士在 1997 年开发基于有限二进制字段上的矩阵线性递归。可以快速产生高质量的伪随机数修正了古典随机数发生算法的很多缺陷。最为广泛使用 Mersenne Twister 的一种变体是 MT19937可以产生 32 位整数序列。描述梅森旋转算法分为三个阶段——获得基础的梅森旋转链、对于旋转链进行旋转算法、对于旋转算法所得的结果进行处理。用途梅森旋转算法是 R、Python、Ruby、IDL、Free Pascal、PHP、Maple、Matlab、GNU 多重精度运算库和 GSL 的默认伪随机数产生器。从 C11 开始C 也可以使用这种算法。在 Boost C、Glib 和 NAG 数值库中作为插件提供。五、程序员数学入门从概念到验证的学习路径与接触到一个有难度的知识点学起来辛苦相比是自己不知道自己不会什么就像上学时候老师说你不会的就问我。我不会啥我从哪问一样一样的代码是对数学逻辑的实现简单的逻辑调用关系是很容易看明白的。但还有那部分你可能不知道的数学逻辑时就很难看懂了。比如扰动函数、负载因子、斐波那契Fibonacci等这些知识点的学习都需要对数学知识进行验证否则也就学个概念背个理论。书到用时方恨少在下还是个宝宝1. 从《程序员数学入门》到《程序员数学 v2.0》科技博主 Jeremy Kun 花了 4 年时间写成一本书**《程序员数学入门》**。这本书为程序员提供了大量精简后的数学知识包括多项式、集合、图论、群论、微积分和线性代数等。同时在 wiki 部分还包括了抽象代数、离散数学、傅里叶分析和拓扑学等。作者表示如果你本科学过一些数学知识那么本书还是挺适合你的不会有什么难度。书中的前三章是基础数学内容往后的难度依次递增。而在 CodeGuide 仓库中小傅哥同样整理了一份**《程序员数学 v2.0》**见 docs/md/algorithm/logic/math/math.md全书约 5 章 28 节涵盖 4 类 14 种数据结构链表、数组、队列、堆栈、哈希表、堆、字典树、二分搜索树、平衡二叉树、2-3 树、红黑树、并查集、图、布隆过滤器以及数学部分 14 章二进制、阶乘、斐波那契、RSA、割圆术、傅立叶变换等。仓库内可直接查阅的数学章节包括《程序员数学斐波那契》——为什么不能用斐波那契散列做数据库路由算法《程序员数学》v2.0 总览数据结构篇数据结构总览含链表、数组、队列、栈、哈希表、堆、字典树、树、AVL、2-3 树、红黑树、图、并查集、布隆过滤器等系列文章2. 推荐的学习路径对于想深入学习的读者建议按下面的顺序循序渐进先动手验证把本文1 出现的次数的两种实现、ThreadLocal 斐波那契散列、HashMap 扰动函数这三段代码全部亲手跑一遍用数据说服自己再读源码对照 HashMap 面经手册第 3 篇 与 ThreadLocal 面经手册第 12 篇把散列、寻址、开放定址的原理吃透最后落地场景阅读 基于 Hash 散列的数据库路由组件设计 与 路由组件 roadmapdb-router把数学散列能力真正用到分库分表、抽奖系统等业务中间件中。六、总结Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians.单纯的只会数学写不了代码能写代码的不懂数学只能是 CRUD 码农。数学知识帮助你设计数据结构和实现算法逻辑代码能力帮你驾驭设计模式和架构模型。多方面的知识结合和使用才是码农和工程师的主要区别也是是否拥有核心竞争力的关键点。学习知识有时候看不到前面的路有多远但哪怕是个泥坑只要你不停地蠕动、折腾、翻滚也能抓出一条泥鳅。知识的路上是发现知识的快乐还是学会知识的成就感不断地促使你前行。回到最初的问题数学离一个程序员有多近答案就藏在每一次哈希计算、每一次循环优化、每一处数据散列里。从谷歌的 101 公路广告牌到 HashMap 的扰动函数再到 ThreadLocal 的黄金分割数——数学不是程序员的选修课而是写出高性能、可扩展、易维护代码的地基。不妨从本文的三段代码开始亲手验证一次数学的力量。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐《Hello 算法》哈希算法ハッシュアルゴリズム精讲从哈希函数设计到素数取模与内置哈希实现《Hello 算法》哈希算法ハッシュアルゴリズム精讲从哈希函数设计到素数取模与内置哈希实现 本篇基于《Hello 算法》日文版「ハッシュアルゴリズム」章节教程文档示例工程教育pytorch-fid深度解析揭秘Fréchet距离在图像生成评估中的应用pytorch fid深度解析揭秘Fréchet距离在图像生成评估中的应用 pytorch fid是一个基于PyTorch实现的Fréchet Incepti人工智能模型评测计算机视觉LaMa图像修复入门克隆后一条命令修复整批图片LaMa图像修复入门克隆后一条命令修复整批图片 LaMa是基于傅里叶卷积的大掩码图像修复模型WACV 2022解决大面积缺失区域糊、断裂的问题。读完人工智能计算机视觉深度学习图像处理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
