Golang实现LFU缓存
既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。这里我们使用一个HashMap实现Get操作的O...
既然上一篇写了LRU，那这一篇我们就来搞一下LFU吧。LFU，Least Frequently Used，最近最少使用，其核心思想是，“如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小”。本文基于 LeetCode 460. LFU 缓存 进行，解法不是最优，但是实现了Get和Put操作的时间复杂度均为O(1)。这里我们使用一个HashMap实现Get操作的O...
LRU，Least Recently Used的缩写，即“最近最少使用”，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。这里，我们基于 LeetCode 146. LRU 缓存 ，使用Golang实现，并使其Get、Put操作的时间复杂度均为O(1)。思路很简单，使用HashMap保存Cache，保证其Get的复杂度为O(1)，使用一个双向链表，保证Put操作维护使用顺序...
最近开始学习Raft算法，就简单记录一下吧。(本文及后续相关文章的实现基于 MIT 6.824 Lab 2: Raft 2022 进行。)背景知识复制状态机一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。图 1 ：复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令...
Dijkstra算法迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。本文将使用Java实现使用Dijkstra算法对带权有向图的最短路径查找。关于图的创建及其相关操作，可移步：数据结构之图及其遍历（Java实现）本文使用的带权有向图：算法详解Dijkstra算法，是...
图的定义什么是图在计算机科学中，图是一种抽象数据类型，用于实现数学中图论的无向图和有向图的概念。 图的数据结构包含一个有限的集合作为节点集合，以及一个无序对或有序对的集合作为边的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。 图的数据结构还可能包含和每条边相关联的数值，例如一个标号或一个数值。邻接矩阵邻接矩阵是一种方阵，用来表示有限图。它的每个元素代表各点之间是否有...