IT技术博客大学习 共学习 共进步

算法

共 606 篇文章

IT 2014-12-30 12:29:21 / 累计浏览 12,537

HashMap解决hash冲突的方法

这篇讲的是 HashMap 如何巧妙处理哈希冲突。作者直接从 put 方法的源码切入,展示了当不同 key 通过哈希算法映射到同一个数组索引(即“桶”)时,HashMap 采用的“链表法”解决方案。 核心思路很清晰:当发生冲突时,新的键值对并不会替换旧的,而是像插入单链表一样,通过 `addEntry` 方法被添加到该桶的链表头部。文章特别指出,这个新插入的 Entry 对象会指向原先位于该桶的 Entry,从而形成一条单向链表。这就解释了为什么在冲突严重时,get 操作会从直接定位退化为需要遍历链表,最坏情况下复杂度会达到 O(n)。 文章还点出了一个关键的设计权衡——负载因子。默认的 0.75 是空间与查询效率之间的折中:过大会节省内存但查询变慢,过小则查询更快但更耗内存。 总的来说,这篇分析没有停留在概念层面,而是通过源码把链表如何形成、负载因子如何影响性能这些细节讲透了,适合想弄懂 Java 集合框架底层原理的开发者阅读。

IT 2014-12-28 23:42:59 / 累计浏览 11,880

面试题 – 为什么我的朋友圈不见了?

这篇文章从一个常见但棘手的分布式系统问题切入:当一个数据聚合服务需要从多个远程服务获取数据,而其中一个服务不可用时,架构师应该如何选择容错策略? 作者详细剖析了三种典型方案。方案一是直接忽略失败的部分数据(优雅降级),虽然损失最小,但可能导致用户体验不确定。方案二是遇到任何失败就返回整体错误(503),完全依赖调用方的缓存与容错能力,否则用户会看到白屏。方案三则是自定义返回格式,显式告知哪些数据加载成功、哪些失败,但这大大增加了前后端的复杂度。 文章并未止步于此,而是进一步引入了“未读数”这一常见功能,将问题场景变得更复杂:即使主数据列表因服务不稳定而缺损,如果能单独提供一个准确的未读数,用户体验和系统效率会如何变化?这使得对三种方案的权衡更加微妙。 整篇文章的核心价值,不在于给出唯一答案,而是系统性地呈现了架构师在“数据完整性”、“用户体验”、“系统复杂度”和“服务可靠性”之间必须进行的现实权衡。它启发我们思考,在微服务架构下,如何设计既健壮又不过度复杂的容错机制。

IT 2014-12-06 20:38:08 / 累计浏览 1,894

B-树

这篇讲的是经典数据结构B-树的核心设计与操作逻辑。文章开篇就点明了B-树与平衡二叉树的关键差异:通过允许节点容纳更多元素(几十到几百个)来大幅降低树的高度,从而在数据无法全部载入内存时,显著减少访问磁盘的次数,提升效率。 作者详细拆解了B-树的严格定义,特别是倾向于使用奇数阶(如2n+1)的统一性,以避免处理偶数阶时可能出现的不平衡情况。随后,文章通过具体的查找和插入示例,生动展示了B-树的工作原理。查找过程强调了其多路搜索的特性,而插入部分的剖析尤为细致,清晰地说明了节点未满、分裂以及元素移动(如将中间元素上提至父节点)等不同情况下的处理逻辑,解释了如何通过分裂和平衡操作来维持所有叶子节点处于同一层的核心性质。 整个讲解围绕着B-树如何保持平衡与高效展开,为其在数据库索引和文件系统等场景中作为底层核心数据结构的重要性,提供了坚实的技术基础。

IT 2014-12-06 01:10:38 / 累计浏览 4,473

为什么长尾数据的翻页技术实现复杂

这篇讲的是长尾数据翻页的技术复杂性。作者从Key-list类型数据(如好友列表、评论ID列表)的翻页需求出发,指出大部分数据长度较短时,简单的LIMIT offset方案尚可应对,但当数据量达到百万级且访问深页码时,该方案性能会急剧下降。 文章核心对比了两种翻页实现:“扶梯方式”(只提供上一页/下一页)与“电梯方式”(支持精确跳转至任意页)。作者解释,扶梯方式通过记录最后一条ID实现O(log n)复杂度的高效查询;而电梯方式因依赖LIMIT offset,在MySQL中需扫描前所有行导致O(n)的复杂度,且难以缓存。 面对更大数据规模,文章进一步讨论了分布式数据分片策略。按用户uid分片可高效读取,但数据冷热不均导致存储成本高昂;引入时间维度分片虽缓解存储压力,却带来了数据滚动自动化难、需额外二级索引等新问题。作者最后指出,现有方案均非理想,为后续探讨更优的长尾翻页设计埋下了伏笔。

IT 2014-12-04 13:27:46 / 累计浏览 3,472

短网址服务的构建

短网址服务从社交媒体兴起,核心是解决链接过长、不便传播的问题。这篇文章深入讲解了如何构建这样一个服务,其实质是一个将长URL映射为短字符串的函数。 作者首先澄清了核心原则:一个短码必须唯一对应一个长地址。随后,文章详细拆解了两种主流的生成方案。方案一利用数据库自增ID,通过精心设计的进制转换(剔除易混淆字符如L、I、0、O)将其编码为6位左右的短码,保证了可读性与生成效率。方案二则从URL的哈希值(如MD5)出发,通过位运算和字符映射将其截断、压缩成短串,提供了另一种无状态的思路。 文章不仅停留在理论层面,还给出了具体的算法代码片段。从设计考量到实现细节,完整展现了一个短网址服务背后的工程思维。

IT 2014-12-02 00:05:34 / 累计浏览 8,391

JSON和JSONP的区别

作者从JSON和JSONP这对常被混淆的概念出发,清晰地区分了它们的本质。JSON是一种轻量级、独立于语言的数据交换格式,它使用键值对和数组来描述数据,易于人读写和机器解析,几乎所有现代编程语言都支持它。 而JSONP则是一种利用HTML `