精选文章

通过Hugo搭建静态网站

静态网站简介 link notifications A static website has fixed content It does not require programming languages to build one. It is the easiest form of website to create. Static websites are build of HTML, CSS, and JavaScript. 引用W3Schools对静态网站的定义——静态网站具有固定内容，不需要编程语言来构建，它是最容易创建的一种网站形式，由HTML、CSS和JavaScript构建而成。静态网站不需要设置数据库也不需要编写任何服务器程序，只需编写前端页面，然后部署到类似于Nginx之类的Web服务器分发静态文件即可。常见的静态网站构建框架有以下几种： Hugo Hexo Docsify 不同的博客框架都有各自的优缺点，其中Hugo号称全世界最快的静态网站构建框架，背后使用Go作为处理语言，适合用于生成拥有大量复杂页面的静态网站，本文基于Hugo以及Hinode主题为例，解析如何编写属于自己的静态网站，最后通过Netlify云服务提供商免费将自己的静态网站发布到互联网上。

2024年6月18日星期二阅读更多

HashMap

HashMap link哈希映射旨在解决快速查找和访问一个集合中的元素的问题。常用于数据库索引、基于磁盘的数据结构以及数据压缩算法，在密码学上常用于密码的存储。对于哈希我们关注以下概念：键(key)：键可以是整形、字符串甚至是更复杂的复合类型，用于输入哈希函数生成哈希索引。哈希函数(hash function)：输入键并生成键对应的哈希索引，该索引用于哈希表寻址。哈希表(hash table)：哈希表通常为一个列表数组，存储与键对应的值。负载系数(load factor)：哈希表的负载系数为哈希表元素个数与哈希表大小的比值。默认值为0.75。哈希具有如下优点：增删和搜索的时间复杂度为$O(1)$ JDK中的HashMap实现 link我们通过几个问题回答一下实现原理：哈希映射是怎么存储的? link哈希映射采用哈希表存储，哈希表每个槽(Solt)为一个集装箱(Bin),取哈希表容量与键的哈希值比值的余数获取哈希表索引进行存储。哈希映射以2整数次方大小创建哈希表，根据公式$h \mod 2^n = h \& (2^n-1)$取余运算可以转化为按位与运算，$(2^n-1)$代表n位二进制数的最大值，按位与该值等同于取原值的后$n$位二进制数，和取余是等价的。位运算的速度相对更快，哈希映射源码中使用位运算i = (n - 1) & hash来计算哈希表集装箱位置，提高运算效率。当哈希表的元素个数超过负载系数规定的阈值时进行哈希表扩容，每次扩容为原来的2倍。源码中使用位运算newThr = oldThr << 1生成新的阈值。哈希映射是如何解决哈希冲突的? link当集装箱元素个数小于阈值时采用链表存储数据，当元素个数大于阈值时采用红黑树存储数据。树化阈值TREEIFY_THRESHOLD默认为8。哈希映射是如何在红黑树中插入一个键的? link哈希映射优先使用键的哈希值进行比较，若哈希值不可比较（哈希冲突）则检查键类型是否实现Comparable接口并进行比较，若仍不可比较则使用决胜局算法tieBreakOrder比较。在采用决胜局算法比较前会先调用红黑树搜索算法查找，以确认待插入键不在数据集内。

2025年5月21日星期三阅读更多

最近文章

有向无环图

有向无环图(Directed Acyclic Graph) linkgraph TB subgraph Directed Acyclic Graph direction TB A((0)) B((1)) C((2)) --> D D((3)) --> B E((4)) --> A F((5)) --> A F --> C E --> B end 拓扑排序 link在有向无环图(DAG)中，若一条边确定由A指向B，则遍历结果中A将始终排在B的前面的排序方式称为拓扑排序。它的核心思想是跟踪顶点的入度(In Degree), 当入度为0时可以访问当前节点(代表当前顶点的前驱顶点已经访问完毕)，访问当前节点之后对邻接顶点的入度减1，循环迭代直至所有节点入度为0。我们可以使用队列存储入度为0的顶点，当对邻接顶点入度减少到0是入队，队列为空时代表所有节点入度为0。 Python C++ Java 若希望找到所有的拓扑排序，需要配合递归和回溯思想。每次遍历取入度为0且未被发现的顶点v，更新v的的邻接顶点的入度，添加v到路径列表path，然后进行归查找。函数在达到递归最深层时(所有节点被发现)，准备返回时判断path的长度等于顶点数量则输出路径到结果。当递归返回时需要恢复v邻接顶点的入度，并将v从l中移除。 Python C++ Java

2025年6月15日星期日阅读更多

闭环

闭环检测算法(Cycle Detecte) link闭环检测算法是从DFS或BFS中修改而来的。DFS或BFS需要针对图中的每个孤岛进行遍历，而闭环检测算法则在此基础上添加一个数组用于存储沿路顶点信息。 Python C++ Java

2025年6月15日星期日阅读更多

并查集

并查集(Union-Find Set) link并查集用于快速判断两个对象是否处于同一组中。假设一个实例场景，一个人的朋友的朋友同样认为是该人的朋友，若给定两个人判断两人是否是朋友关系，在该场景中并查集就可以发挥作用。并查集实现 link Python C++ Java

2025年6月13日星期五阅读更多

最短路径算法

Dijkstra算法 linkDijkstra算法用于计算加权图中一个顶点到其他顶点的最短距离。 Dijkstra算法不支持权值包含负值的加权图，因为算法每次都是取距离最小的顶点更新其邻接顶点的，若邻接顶点存在一个负数边，当前顶点$v$到邻接顶点$u$的距离会比当前顶点的距离更小，导致下一迭代会从$u$开始又更新$v$的距离为一个更小的距离，算法陷入死循环。若所有边同时加上一个固定数值结果将不再正确，因为在所有到其他顶点的最短路径中，所包含的边数量并不一定一致。 Dijkstra算法实现 linkDijkstra算法的核心思想是初始化一个源顶点到其他顶点的距离映射表(源顶点到源顶点的距离为0，到其他节点为无穷大)，每次从集合中取出距离源顶点最小的顶点$v$，若由v到其邻接顶点的距离更短则更新邻接顶点的在集合中的距离值，直到所有顶点从集合中取出来。我们可以通过最小堆快速取出距离最小的顶点，通过哈希映射来维护顶点的距离值。值得注意的是，使用编程语言提供的最小堆一般不支持动态调整堆中元素的大小，我们只需重复插入距离更短的顶点即可，并不会影响我们取出的最小值。时间复杂度：$O(E*\log V)$，在$O(1)$复杂度内建立最小堆Heap，堆中至多$O(E)$个顶点，至多进行$O(E)$次pop()操作和$O(E)$次push()操作，而pop()和push()的时间复杂度均为为$O(\log E)=O(\log V^2)=O(\log V)$。HashMap在良好的哈希函数下能做到$O(1)$复杂度的插入和更新操作。空间复杂度：$O(V)$，我们使用了一个Heap和一个HashMap额外存储顶点信息。 Python C++ Java Floyd Warshall算法 linkFloyd Warshall算法用于计算加权图所有顶点间的最短距离。Floyd Warshall算法可以计算是包含负值的加权图，但不支持闭环为权重之和为负数的加权图。 Floyd Warshall算法实现 link 时间复杂度：$O(V^3)$，算法中包含三个相互嵌套的循环。空间复杂度：$O(V)$, 我们使用了一个HashTable存储各顶点间的距离。 Python C++ Java Bellman Ford算法 link前面讨论的Dijkstra算法有一个限制条件是图中不能包含权重为负数的边，因为再次访问已访问的顶点，否则将导致死循环。Bellman Ford算法不是从最短距离节点开始更新邻接顶点的最短路径，而是通过遍历所有边并更新从边对端的最短路径，他可以解决Dijkstra算法不能计算包含权重为负数的边的问题。图中不能包含权重之和为负数的闭环，因为围绕环绕一圈，距离就会变小，最短路径不存在。

2025年6月12日星期四阅读更多

最小生成树算法

最小生成树算法(MST Algorithm) link生成树(Spanning Tree)是无向连通图中所有顶点以及部分边所构成的一个树状无向无环连通图。生成树的权重等于生成树中所有边的权重之和，权重最小的生成树被称为最小生成树。生成树的特点：生成树的顶点数量与原图一致。$V_{mst} = V_{g}$ 生成树的边的数量等于原图顶点数量减1。$E_{mst} = V_{g} -1$ 生成树必须是连通的。生成树必须是无环的。生成树可能有多个。最小生成树的特点：当图中所有边的权重都相等时，所有的生成树都是最小生成树，权重都相等。图中权重最小的边一定包含在所有最小生成树中，最大的边一定不包含在最小生成树中。若图中顶点分成两个不相交集合，集合间相连的边中权重最小的边一定包含在最小生成树中。若图中形成环，如果一个边的权重严格大于其他边，则该边不会包含在任一最小生成树中。若图中所有边的权重都是唯一的，则最小生成树只有一种情况。生成树是最小连通图，对最小生成树移除边将成为非连通图。生成树是最小无环图，往最小生成树添加边将导致环的产生。 Kruskal’s Algorithm实现 linkKruskal’s Algorithm是一个常用的寻找无向连通图最小生成树的算法。它的核心思想是对边进行权重排序，从权重最小的边开始遍历，若边不构成闭环则添加到新图中，否则对该边进行忽略。值得注意的是，生成树边的数量满足关系式$E_{mst} = V_{g} -1$，最后一个边不需要处理（从这里可以看出权重最大的边一定不会包含在最小生成树中）。Kruskal算法的关键在于闭环检测，在选取边的时候若该边的两个端点同属于一个集合即发生了闭环，我们可以使用并查集快速判断两个元素是否处在同一集合下。 Python C++ Java Prim’s Algorithm实现 linkPrim’s Algorithm是另外一个寻找无向连通图最小生成树的算法，它利用了生成树的不相交割集间权重最小的边一定包含在最小生成树中这条性质。核心思想是创建一个集合$S$用于跟踪已加入最小生成树的顶点，每次迭代选取$S$和$V-S$间的最小权重边加入到新图，并将其对端顶点加入到$S$，循环迭代直到所有顶点加入到$S$。$S$与$V-S$相连的边由最小权重边的对端顶点的邻接顶点中产生，一般使用小根堆来跟踪这些边并快速提取最小权重边。

2025年6月10日星期二阅读更多

HashSet

HashSet link哈希集合旨在解决快速判断一个元素是否在一个数据集中的问题。哈希集合使用红黑树或哈希映射作为底层数据存储结构，提供高效的查询性能。 HashSet实现 link Python C++ LinkedHashSet实现 link Python C++

2025年6月9日星期一阅读更多