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操作维护使用顺序...
介绍trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。说白了，Trie树是一种N叉树，除根节点外，每个节点都保存了这...
介绍二叉查找树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也分别为二叉查...