菜鸟笔记
开链式哈希表
简单说明 hashtable适用于需要频繁插入、删除、查找的场合、在这些场合中hashtable都可以常数平均时间完成、然而之所以hashtable的效率这么高、是因为在以上这些操作时都是通过hash function直接定位元素在表中的位...
算法笔记
惊艳的算法—— 唯一ID生成器snowflake
分布式全局唯一ID生成器 很多场景需要使用全局唯一ID，用来标识唯一一条消息，唯一一笔交易，唯一一个用户，唯一一张图片等等。 传统数据库表的自增主键是很简单的一种实现方式，前提是你没有分库，也没有分表，如果你分表了，id就会重复，失去唯一性...
惊艳的算法 一致性哈希
背景 随着时代的发展，数据量与日俱增，相比纵向扩展单机的性能，人们更倾向于横向扩展，将多台一般的廉价机器组成集群来充当超级计算机，节省了大量的成本，代价是极大地增加了系统的复杂性。为了应对这些复杂性，一批又一批分布式领域的技术相继诞生，其中...
那些惊艳的算法-布隆过滤器
问题 假设你现在要处理这样一个问题，你有一个网站并且拥有很多访客，每当有用户访问时，你想知道这个ip是不是第一次访问你的网站。这是一个很常见的场景，为了完成这个功能，你很容易就会想到下面这个解决方案： 把访客的ip存进一个hash表中，每当...
时间轮算法
从定时任务说起 自然界中定时任务无处不在，太阳每天东升西落，候鸟的迁徙，树木的年轮，人们每天按时上班，每个月按时发工资、交房租，四季轮换，潮涨潮落，等等，从某种意义上说，都可以认为是定时任务。 大概很少有人想过，这些“定时”是怎样做到的。当...
跳跃表实现
跳跃表： 跳跃表与链表结构相似，只是引入“分层”的概念，从上到下的每一层都是一个链表。 借个图： 从图中可观察到跳跃表有以下的性质： 1.每个节点有多个层，每层都有一个指向同层的下一节点的指针 2.每层的链表都是一个有序链表，根据给定的ke...
海量数据中第 K 位元素 & 求 top K 的数据
题目 在一个由 n 个元素组成的集合中，按从小到大顺序排序的话，第 K 个顺序统计位即指第 K 个数，当 K = n 时即最大值，当 K = 1 时即最小值。先给定一个无序的元素集合，求集合中第 K 统计位的值是多少？ 同理，若求 top ...
什么是递归函数？
递归函数 递归 递归就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。递归函数必须有结束条件。 当函数在一直递推，直到遇到墙后返回，这个墙就是结束条件。 所以递归要有两个要素，结束条件与递推关系 ...
路径规划-CH算法
概述 CH(Contraction Hierarchies)是道路网络最短路径算法之一，其应用收缩(contract)节点的方法将节点分层，显著提高了最短路径的搜索速度。 CH算法涵盖数据预处理和路径搜索两个方面，预处理通过收缩节点生成路网...
Dijkstra算法及其C++实现
什么是最短路径问题 如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 单源最短路径问题是指对于给定的图$G=(V, E)$，求源点$v_0$到其它顶点$v_t...