Algorithm

概念 优先级队列（Priority Queue）是一种特殊的队列，队列中每个元素都附有一个"优先级"。出队时，不再遵循普通队列的 FIFO（先进先出）原则，而是优先级最高（或最低）的元素先出队。 直观类比：医院的急诊室——无论谁先到，病情最重的患者优先就诊。 核心特性 插入（insert / enqueue）：将元素连同优先级一起加入队列 取最值（peek）：查看优先级最高的元素，不移除 取出最值（poll / dequeue）：取出并移除优先级最高的元素 不保证全局有序：内部结构只保证堆顶（最值）正确，其余元素顺序不确定 内部实现：二叉堆 绝大多数语言的标准库都用**二叉堆（Binary Heap）**实现优先级队列。 堆的结构 用完全二叉树表示，通常以数组存储 最小堆（Min-Heap）：父节点 ≤ 子节点，根为最小值 最大堆（Max-Heap）：父节点 ≥ 子节点，根为最大值 数组索引关系（从 0 开始）： 节点 索引 父节点 (i-1) / 2 左子节点 2*i + 1 右子节点 2*i + 2 核心操作：上浮与下沉 上浮（Sift Up）：插入新元素时，将其放在数组末尾，然后与父节点比较，不满足堆性质则交换，直到满足为止。 下沉（Sift Down）：取出堆顶后，将末尾元素移到堆顶，然后与子节点比较，不满足堆性质则与较小（或较大）的子节点交换，直到满足为止。 时间复杂度 操作 时间复杂度 插入 $O(\log n)$ 取出最值 $O(\log n)$ 查看最值 $O(1)$ 建堆（heapify） $O(n)$ 两种变体 最小优先级队列（Min Priority Queue） 优先级数值最小的元素最先出队。例如：Dijkstra 最短路径算法中，每次选取距离最小的节点。 最大优先级队列（Max Priority Queue） 优先级数值最大的元素最先出队。例如：任务调度中，优先执行优先级最高的任务。 ...

Raft 一致性算法 raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Paxos。但Paxos是：少数真正理解的人觉得简单，尚未理解的人觉得很难，大多数人都是一知半解。 raft的论文，两位研究者也提到，他们也花了很长的时间来理解Paxos，他们也觉得很难理解，于是研究出了raft算法。 raft是一个共识算法 (consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币 (比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集 (replication），在带着问题学习分布式系统之中心化复制集一文中介绍了中心化复制集的相关知识。raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。 本文基于论文In Search of an Understandable Consensus Algorithm对raft协议进行分析，当然，还是建议读者直接看论文。 本文地址：https://www.cnblogs.com/xybaby/p/10124083.html raft算法概览 回到顶部 Raft算法的头号目标就是容易理解 (UnderStandable），这从论文的标题就可以看出来。当然，Raft增强了可理解性，在性能、可靠性、可用性方面是不输于Paxos的。 Raft more understandable than Paxos and also provides a better foundation for building practical systems 为了达到易于理解的目标，raft做了很多努力，其中最主要是两件事情： 问题分解 状态简化 问题分解是将"复制集中节点一致性"这个复杂的问题划分为数个可以被独立解释、理解、解决的子问题。在raft，子问题包括，leader election， log replication，safety，membership changes。而状态简化更好理解，就是对算法做出一些限制，减少需要考虑的状态数，使得算法更加清晰，更少的不确定性 (比如，保证新选举出来的leader会包含所有commited log entry） Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log. The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines. A leader can fail or become disconnected from the other servers, in which case a new leader is elected. ...

“SkipList, 跳表, 跳跃表” SkipList SkipList(跳表)这种数据结构是由 William Pugh 于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList 的设计初衷是作为替换 平衡树 的一种选择。 我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。 但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，SkipList 需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。 SkipList还有一个优势就是实现简单，SkipList的实现只花了2个小时，而红黑树，我可能得2天。 时隔将近三十多年，SkipList 这种数据结构仍在许多途径有用武之地，比如Redis, 还有Google的著名项目 Bigtable, leveldb 原理及实现 其实跳表就是在普通单向链表的基础上增加了一些索引，而且这些索引是分层的，从而可以快速地查的到数据。 比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤: 从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level==2这层)，查找到21这个节点，由于21 > 19, 所以结点不往前走，而是level由2降低到1 然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现21>19, 所以level由1降低到0 在结点17上，level==0索引到19,查找完毕。 如果在level==0这层没有查找到，那么说明不存在key为19的节点，查找失败 https://zhuanlan.zhihu.com/p/33674267 skiplist, 红黑树 skiplist 的复杂度和红黑树一样，而且实现起来更简单。 在并发环境下红黑树在插入和删除时需要 rebalance，性能不如跳表。 http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

“平衡二叉树, 平衡树, AVL树” 平衡树, 平衡二叉树 AVL树 树堆 (Treap) 伸展树 (Splay tree) 红黑树 (Red–black tree) 加权平衡树 (Weight balanced tree) 2-3树 AA树 替罪羊树 AVL树 AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足 (所有节点的左右子树高度差的绝对值不超过1) 。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况 局限性 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。 AVL 树是一种平衡二叉树，得名于其发明者的名字 ( Adelson-Velskii 以及 Landis) 。 1: 定义 父节点的左子树和右子树的高度之差不能大于1，也就是说不能高过1层，否则该树就失衡了，此时就要旋转节点，在 编码时，我们可以记录当前节点的高度，比如空节点是-1，叶子节点是0，非叶子节点的height往根节点递增，比如在下图 中我们认为树的高度为h=2。 旋转 节点再怎么失衡都逃不过4种情况，下面我们一一来看一下。 ① 左左情况 (左子树的左边节点) 我们看到，在向树中追加“节点1”的时候，根据定义我们知道这样会导致了“节点3"失衡，满足“左左情况“，可以这样想，把这 棵树比作齿轮，我们在“节点5”处把齿轮往下拉一个位置，也就变成了后面这样“平衡”的形式，如果用动画解释就最好理解了。 ② 右右情况 (右子树的右边节点) 同样，”节点5“满足”右右情况“，其实我们也看到，这两种情况是一种镜像，当然操作方式也大同小异，我们在”节点1“的地方 将树往下拉一位，最后也就形成了我们希望的平衡效果。 ③左右情况 (左子树的右边节点) 从图中我们可以看到，当我们插入”节点3“时，“节点5”处失衡，注意，找到”失衡点“是非常重要的，当面对”左右情况“时，我们将 失衡点的左子树进行"右右情况旋转"，然后进行”左左情况旋转“，经过这样两次的旋转就OK了，很有意思，对吧。 ④右左情况(右子树的左边节点) 这种情况和“情景3”也是一种镜像关系，很简单，我们找到了”节点15“是失衡点，然后我们将”节点15“的右子树进行”左左情况旋转“， 然后进行”右右情况旋转“，最终得到了我们满意的平衡。 添加 如果我们理解了上面的这几种旋转，那么添加方法简直是轻而易举，出现了哪一种情况调用哪一种方法而已。 删除 删除方法跟添加方法也类似，当删除一个结点的时候，可能会引起祖先结点的失衡，所以在每次”结点“回退的时候计算结点高度。 https://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html https://blog.csdn.net/u010899985/article/details/80981053 https://cloud.tencent.com/developer/article/1177129

“二叉树” 二叉树 (Binary Tree) 二叉树 (Binary Tree) 是包含n个节点的有限集合，该集合或者为空集 (此时，二叉树称为空树) ，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。 二叉树中的节点至多包含两棵子树，分别称为左子树和右子树，而左子树和右子树又分别至多包含两棵子树。由上述的定义，二叉树的定义是一种递归的定义。 @startuml circle 1 circle 2 circle 3 circle 4 circle 5 circle 7 circle 10 circle 11 circle 14 1 -- 2 1 -- 3 2 -- 4 2 -- 5 3 -- 7 5 -- 10 5 -- 11 7 -- 14 @enduml 满二叉树 Full Binary Tree 对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。 ...

“延时队列” https://zhuanlan.zhihu.com/p/266156267 延迟队列 首先，队列这种数据结构相信大家都不陌生，它是一种先进先出的数据结构。普通队列中的元素是有序的，先进入队列中的元素会被优先取出进行消费； 延时队列相比于普通队列最大的区别就体现在其延时的属性上， 普通队列的元素是先进先出，按入队顺序进行处理， 而延时队列中的元素在入队时会指定一个延迟时间，表示其希望能够在经过该指定时间后处理。从某种意义上来讲，延迟队列的结构并不像一个队列，而更像是一种以时间为权重的有序堆结构。 应用场景 我在开发业务需求时遇到的使用场景是这样的，用户可以在小程序中订阅不同的微信或者 QQ 的模板消息，产品同学可以在小程序的管理端新建消息推送计划，当到达指定的时间节点的时候给所有订阅模板消息的用户进行消息推送。 这里不太懂…. 把要发送的模板消息加到延时队列里？ 如果仅仅是服务单一的小程序，那也许起个定时任务，或者甚至人工的定时去执行能够最便捷最快速的去完成这项需求，但我们希望能够抽象出一个消息订阅的模块服务出来给所有业务使用，这时候就需要一种通用的系统的解决方案，这时候便需要使用到延迟队列了。 除了上述我所遇到的这样的典型的需求以外，延迟队列的应用场景其实也非常的广泛，比如说以下的场景: 新建的订单，如果用户在 15 分钟内未支付，则自动取消。 公司的会议预定系统，在会议预定成功后，会在会议开始前半小时通知所有预定该会议的用户。 安全工单超过 24 小时未处理，则自动拉企业微信群提醒相关责任人。 用户下单外卖以后，距离超时时间还有 10 分钟时提醒外卖小哥即将超时。 对于数据量比较少并且时效性要求不那么高的场景，一种比较简单的方式是轮询数据库，比如每秒轮询一下数据库中所有数据，处理所有到期的数据，比如如果我是公司内部的会议预定系统的开发者，我可能就会采用这种方案，因为整个系统的数据量必然不会很大并且会议开始前提前 30 分钟提醒与提前 29 分钟提醒的差别并不大。 但是如果需要处理的数据量比较大实时性要求比较高，比如淘宝每天的所有新建订单 15 分钟内未支付的自动超时，数量级高达百万甚至千万，这时候如果你还敢轮询数据库怕是要被你老板打死，不被老板打死估计也要被运维同学打死。 按时间戳排序，每秒查询15分钟之内创建的订单? 这种场景下，就需要使用到我们今天的主角 —— 延迟队列了。延迟队列为我们提供了一种高效的处理大量需要延迟消费消息的解决方案。那么话不多说，下面我们就来看一下几种常见的延迟队列的解决方案以及他们各自的优缺点。 实现方案 Redis ZSet 我们知道 Redis 有一个有序集合的数据结构 ZSet，ZSet 中每个元素都有一个对应 Score，ZSet 中所有元素是按照其 Score 进行排序的。 那么我们可以通过以下这几个操作使用 Redis 的 ZSet 来实现一个延迟队列: 入队操作: ZADD KEY timestamp task, 我们将需要处理的任务，按其需要延迟处理时间作为 Score 加入到 ZSet 中。Redis 的 ZAdd 的时间复杂度是O(logN)，N是 ZSet 中元素个数，因此我们能相对比较高效的进行入队操作。 起一个进程定时 (比如每隔一秒) 通过 ZRANGEBYSCORE 方法查询 ZSet 中 Score 最小的元素，具体操作为: ZRANGEBYSCORE KEY -inf +inf limit 0 1 WITHSCORES ...

循环冗余校验 (CRC) 从奇偶校验说起 所谓通讯过程的校验是指在通讯数据后加上一些附加信息，通过这些附加信息来判断接收到的数据是否和发送出的数据相同。比如说RS232串行通讯可以设置奇偶校验位，所谓奇偶校验就是在发送的每一个字节后都加上一位，使得每个字节中1的个数为奇数个或偶数个。比如我们要发送的字节是0x1a，二进制表示为0001 1010。 采用奇校验，则在数据后补上个0，数据变为0001 1010 0，数据中1的个数为奇数个 (3个) 采用偶校验，则在数据后补上个1，数据变为0001 1010 1，数据中1的个数为偶数个 (4个) 接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。 奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。 奇偶校验就先介绍到这来，之所以从奇偶校验说起，是因为这种校验方式最简单，而且后面将会知道奇偶校验其实就是CRC 校验的一种(CRC-1)。 累加和校验 另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子: 我们要传输的信息为: 6、23、4 加上校验和后的数据包: 6、23、4、33 这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。 累加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为CRC校验在传输数据的形式上与累加和校验是相同的，都可以表示为: 通讯数据 校验字节 (也可能是多个字节) CRC 算法 CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。还以上面例子中的数据为例: 23、4 可以看做一个2进制数: 0000011000010111 00000010 假如被除数选9，二进制表示为: 1001 CRC即循环冗余校验码 (Cyclic Redundancy Check) : 是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查 (CRC) 是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性。 CRC32简介 CRC校验实用程序库 在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种。CRC的全称是循环冗余校验。 CRC32检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS (帧检错序列）采用的是CRC-CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。 crc golang m_data := []byte{0x01,0x02,0x03,0x04} //创建Byte切片 checksum := CheckSum(m_data) //调用计算CRC函数 CheckSum fmt.Printf("check sum:%X \n",checksum) https://blog.csdn.net/liyuanbhu/article/details/7882789 ...

算法效率, 算法分析 https://blog.csdn.net/zolalad/article/details/11848739 https://www.zhihu.com/question/21387264 算法的时间复杂度和空间复杂度 通常,对于一个给定的算法,我们要做两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。 一、事后统计的方法 这种方法可行,但不是一个好的方法。该方法有两个缺陷: 一是要想对设计的算法的运行性能进行评测,必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优势。 二、事前分析估算的方法 因事后统计方法更多的依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。 在编写程序前,依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素: (1). 算法采用的策略、方法；(2). 编译产生的代码质量；(3). 问题的输入规模；(4). 机器执行指令的速度。 一个算法是由控制结构 (顺序、分支和循环3种) 和原操作 (指固有数据类型的操作) 构成的,则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法,通常的做法是,从算法中选取一种对于所研究的问题 (或算法类型) 来说是基本操作的原操作,以该基本操作的重复执行的次数作为算法的时间量度。 时间复杂度 (1) 时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 (2) 时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。 另外,上面公式中用到的 Landau符号其实是由德国数论学家保罗·巴赫曼 (Paul Bachmann) 在其1892年的著作《解析数论》首先引入,由另一位德国数论学家艾德蒙·朗道 (Edmund Landau) 推广。Landau符号的作用在于用简单的函数来描述复杂函数行为,给出一个上或下 (确) 界。在计算算法复杂度时一般只用到大O符号,Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O,最初是用大写希腊字母,但现在都用大写英语字母O；小o符号也是用小写英语字母o,Θ符号则维持大写希腊字母Θ。 T (n) = Ο(f (n)) 表示存在一个常数C,使得在当n趋于正无穷时总有 T (n) ≤ C * f(n) 简单来说,就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T (n)的上界是C * f(n)。其虽然对f(n)没有规定,但是一般都是取尽可能简单的函数。例如,O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ,一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C,所以f(n)里一般不加系数。如果把T(n)当做一棵树,那么O(f(n))所表达的就是树干,只关心其中的主干,其他的细枝末节全都抛弃不管。 在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 按数量级递增排列,常见的时间复杂度有: 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),…, k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 ...

Round Robin 轮询调度算法 Round Robin Scheduling 轮询调度算法 轮询调度 (Round Robin Scheduling) 算法就是以轮询的方式依次将请求调度不同的服务器,即每次调度执行i = (i + 1) mod n,并选出第i台服务器。算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。 轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器,从1开始,直到N(内部服务器个数),然后重新开始循环。 轮询调度算法假设所有服务器的处理性能都相同,不关心每台服务器的当前连接数和响应速度。当请求服务间隔时间变化比较大时,轮询调度算法容易导致服务器间的负载不平衡。 所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。 作者: 小程故事多 链接: http://www.jianshu.com/p/92666209041a 來源: 简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 负载均衡调度算法默认是 round robin,也就是轮询调度算法。 算法本身很简单,轮着一个一个来,非常简单高效公平的调度算法。 突然发现了一直被忽视的问题,为啥叫 round robin ？ robin 明明是旅鸫,亦称美洲知更鸟,与轮询一点关系都没有。在查询资料后发现这个单词来源挺有意思的,这里分享给大家。 round robin 来源于法语ruban rond (round ribbon) ,意思是环形丝带。 在17、18世纪时法国农民希望以请愿的方式抗议国王时,通常君主的反应是将请愿书中最前面的两至三人逮捕并处决,所以很自然地没有人希望自己的名字被列在前面。为了对付这种专制的报复,人们在请愿书底部把名字签成一个圈 (如同一条环状的带子) ,这样就找不出带头大哥,于是只能对所有参与者进行同样的惩罚。 1731年,英国皇家海军最初使用了这个名词,以循环顺序签署请愿书,这样就没法找到带头大哥了。 非常贴切有木有,后端服务器轮着来处理请求,一个个都不要抢,都要出来接受处决。 https://zhuanlan.zhihu.com/p/84799744 常见的负载均衡算法包含: 轮询法 (Round Robin) 加权轮询法 (Weight Round Robin) 随机法 (Random) 加权随机法 (Weight Random) 平滑加权轮询法 (Smooth Weight Round Robin) 源地址哈希法 (Hash) 最小连接数法 (Least Connections) ———————————————— 版权声明: 本文为CSDN博主「志波同学」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接: https://blog.csdn.net/claram/article/details/90265243

缓存算法, LFU, LRU, FIFO 超时剔除 - expire 主动更新 - 开发控制生命周期 扩展: 缓存污染 - 缓存污染降低了缓存的使用率，把不常用的数据读取到缓存，同时会把常用的数据移出缓存，这样会直接降低系统的数据命中率 http://www.leexiang.com/cache-algorithm 缓存算法 原文: http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html 翻译: http://www.zavakid.com/25 引言 我们都听过 cache，当你问他们是什么是缓存的时候，他们会给你一个完美的答案，可是他们不知道缓存是怎么构建的，或者没有告诉你应该采用什么标准去选择缓存框架。在这边文章，我们会去讨论缓存，缓存算法，缓存框架以及哪个缓存框架会更好。 “缓存就是存贮数据 (使用频繁的数据) 的临时地方，因为取原始数据的代价太大了，所以我可以取得快一些。” 这就是 programmer one (programmer one 是一个面试者) 在面试中的回答 (一个月前，他向公司提交了简历，想要应聘要求在缓存，缓存框架，大规模数据操作有着丰富经验的 java 开发职位) 。 programmer one 通过 hash table 实现了他自己的缓存，但是他知道的只是他的缓存和他那存储着150条记录的 hash table，这就是他认为的大规模数据 (缓存 = hashtable，只需要在 hash table 查找就好了) ，所以，让我们来看看面试的过程吧。 面试官: 你选择的缓存方案，是基于什么标准的？ programmer one: 呃， (想了5分钟) 嗯，基于，基于，基于数据 (咳嗽……) 面试官: excese me ! 能不能重复一下？ programmer one: 数据？！ 面试官: 好的。说说几种缓存算法以及它们的作用 programmer one: (凝视着面试官，脸上露出了很奇怪的表情，没有人知道原来人类可以做出这种表情 ) ...

Redis, Memcache, Guava, Ehcache 中的算法 缓存那些事，一是内存爆了要用LRU(最近最少使用, Least Recently Used)、LFU(最少访问次数, Least Frequently Used)、FIFO的算法清理一些；二是设置了超时时间的键过期便要删除，用主动或惰性的方法。 在看所有的细节之前，可以看一篇相当专业的《缓存算法》，世界真宽阔，算法真奇妙。 LRU 简单粗暴的Redis 今天看Redis3.0的发行通告里说，LRU算法大幅提升了，就翻开源码来八卦一下，结果哭笑不得，这旧版的"近似LRU"算法，实在太简单，太偷懒，太Redis了。 在Github的Redis项目里搜索lru，找到代码在redis.c的freeMemoryIfNeeded()函数里。 先看2.6版的代码: 竟然就是随机找三条记录出来，比较哪条空闲时间最长就删哪条，然后再随机三条出来，一直删到内存足够放下新记录为止…….可怜我看配置文档后的想象，一直以为它会帮我在整个Redis里找空闲时间最长的，哪想到我有一百万条记录的时候，它随便找三条就开始删了。 好，收拾心情再看3.0版的改进: 现在每次随机五条记录出来，插入到一个长度为十六的按空闲时间排序的队列里，然后把排头的那条删掉，然后再找五条出来，继续尝试插入队列………嗯，好了一点点吧，起码每次随机多了两条，起码不只在一次随机的五条里面找最久那条，会连同之前的一起做比较…… 中规中矩的Memcached 相比之下，Memcached实现的是再标准不过的LRU算法，专门使用了一个教科书式的双向链表来存储slab内的LRU关系，代码在item.c里，详见memcached源码分析–LRU队列与item结构体，元素插入时把自己放到列头，删除时把自己的前后两个元素对接起来，更新时先做删除再做插入。 分配内存超限时，很自然就会从LRU的队尾开始清理。 同样中规中矩的Guava Cache Guava Cache同样做了一个双向的Queue，见LocalCache中的AccessQueue类，也会在超限时从Queue的队尾清理，见evictEntries()函数。 和Redis旧版一样的Ehcache/Hazelcast 看文档，居然和Redis2.6一样，直接随机8条记录，找出最旧那条，刷到磁盘里，再看代码，Eviction类 和 OnHeapStore的evict()函数。 再看Hazelcast，几乎一样，随机取25条。 这种算法，切换到LFU也非常简单。 小结 不过后来再想想，也许Redis本来就不是主打做Cache的，这种内存爆了需要通过LRU删掉一些元素不是它的主要功能，默认设置都是noeviction——内存不够直接报错的，所以就懒得建个双向链表，而且每次访问时都要更新它了，看Google Group里长长的讨论，新版算法也是社区智慧的结晶。何况，Ehcache和Hazelcast也是和它的旧版一样的算法，Redis的新版还比这两者强了。 后来，根据@刘少壮同学的提示，JBoss的InfiniSpan里还实现了比LRU更高级的LIRS算法，可以避免一些冷数据因为某个原因被大量访问后，把热数据挤占掉。 过期键删除 如果能为每一个设置了过期的元素启动一个Timer，一到时间就触发把它删掉，那无疑是能最快删除过期键最省空间的，在Java里用一条DeplayQueue存着，开条线程不断的读取就能做到。但因为该线程消耗CPU较多，在内存不紧张时有点浪费，似乎大家都不用这个方法。 所以有了惰性检查，就是每次元素被访问时，才去检查它是否已经超时了，这个各家都一样。但如果那个元素后来都没再被访问呢，会永远占着位子吗？所以各家都再提供了一个定期主动删除的方式。 Redis 代码在redis.c的activeExpireCycle()里，看过文档的人都知道，它会在主线程里，每100毫秒执行一次，每次随机抽20条Key检查，如果有1/4的键过期了，证明此时过期的键可能比较多，就不等100毫秒，立刻开始下一轮的检查。不过为免把CPU时间都占了，又限定每轮的总执行时间不超过1毫秒。 Memcached Memcached里有个文不对题的LRU爬虫线程，利用了之前那条LRU的队列，可以设置多久跑一次(默认也是100毫秒)，沿着列尾一直检查过去，每次检查LRU队列中的N条数据。虽然每条Key设置的过期时间可能不一样，但怎么说命中率也比Redis的随机选择N条数据好一点，但它没有Redis那种过期的多了立马展开下一轮检查的功能，所以每秒最多只能检查10N条数据，需要自己自己权衡N的设置。 Guava Cache 在Guava Cache里，同一个Cache里所有元素的过期时间是一样的，所以它比Memached更方便，顺着之前那条LRU的Queue检查超时，不限定个数，直到不超时为止。而且它这个检查的调用时机并不是100毫秒什么的，而是每次各种写入数据时的preWriteCleanup()方法中都会调用。 吐槽一句，Guava的Localcache类里面已经4872行了，一点都不轻量了。 Ehcache Ehcache更乱，首先它的内存存储中只有惰性检查，没有主动检查过期的，只会在内存超限时不断用近似LRU算法(见上)把内存中的元素刷到磁盘中，在文件存储中才有超时检查的线程，FAQ里专门解释了原因。 然后磁盘存储那有一条8小时左右跑一次的线程，每次遍历所有元素…..见DiskStorageFactory里的DiskExpiryTask。 一圈看下来，Ehcache的实现最弱。 文章持续修改，转载时请保留原链接: http://calvin1978.blogcn.com/articles/lru.html

Red-Black Tree, 红黑树, R-B Tree https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md 二叉查找树 由于红黑树本质上就是一棵二叉查找树，所以在了解红黑树之前，咱们先来看下二叉查找树。 二叉查找树 (Binary Search Tree) ，也称有序二叉树 (ordered binary tree) ,排序二叉树 (sorted binary tree) ，是指一棵空树或者具有下列性质的二叉树: 若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 任意结点的左、右子树也分别为二叉查找树。 没有键值相等的结点 (no duplicate nodes) 。 因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O (lgn) . (至于n个结点的二叉树高度为lgn的证明，可参考算法导论 第12章 二叉查找树 第12.4节) 。 但二叉树若退化成了一棵具有n个结点的线性链后，则此些操作最坏情况运行时间为O (n) 。后面我们会看到一种基于二叉查找树-红黑树，它通过一些性质使得树相对平衡，使得最终查找、插入、删除的时间复杂度最坏情况下依然为O (lgn) 。 红黑树 前面我们已经说过，红黑树，本质上来说就是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。 但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢？这就引出了红黑树的5条性质: 每个结点要么是红的，要么是黑的。 根结点是黑的。 每个叶结点 (叶结点即指树尾端NIL指针或NULL结点) 是黑的。 如果一个结点是红的，那么它的俩个儿子都是黑的。 对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 正是红黑树的这5条性质，使得一棵n个结点是红黑树始终保持了logn的高度，从而也就解释了上面我们所说的"红黑树的查找、插入、删除的时间复杂度最坏为O(log n)“这一结论的原因。 红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高！！！ 这里引用一下知乎上的回答: Answer 1: 如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度。 其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。 map的实现只是折衷了两者在search、insert以及delete下的效率。总体来说，RB-tree的统计性能是高于AVL的。 作者: Acjx 链接: http://www.zhihu.com/question/20545708/answer/58717264 Answer 2 这个总结比较好: 红黑树的 查询性能略微逊色于AVL树，因为他比avl树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的avl树最多多一次比较，但是，红黑树在插入和删除上完爆avl树， avl树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于avl树为了维持平衡的 开销要小得多 ...

抽奖概率-三种算法 http://www.cnblogs.com/younggun/p/3249772.html 一、逢"几"中奖 逢"几"中奖,即通过预估抽奖人数和奖品数来判断,“几”=(抽奖人数/奖品数)*N。这是一种最简单抽奖算法,适合抽奖人数众多,而且互相无联系的情况。如今大为流行的微博转发得奖就常常使用这种算法,即根据转发次数来决定奖品归属,透明而且具有激励性。 当然这个"几"也不单只次数,还可能是时间,逢某个时间点就可以抽中,不过这种方案可能产生无人中奖和很多人中奖的情况,时间点的安排很关键！这个时间点一旦公布出去,那就是秒杀,霍霍。。 逢"几"中奖有很多弊端,但是非常简单,很容易实现,被很多抽奖活动所采用,有些会公布抽奖规则,激励抽奖,有些则不会公布,其实后台运行的可能也是这个算法,简单高效又不失公平。在信息不透明的情况下,鬼知道你是第几个抽奖的,哈哈。。 二、概率抽奖 所谓概率抽奖是最容易想到的抽奖算法了,这个概率可以是一成不变的,也可以是一直在变化调整的,最难的是采用多大的概率,何种情况下采用何种概率。这个也没有什么通用的方案,不同的应用场景,所用的概率算法不同。下面介绍一种算法,根据奖品的过期日期来计算它当前时间的中奖率,当时间逐渐接近奖品过期时间时,中奖概率会逐渐发生变化,如果设为1表示线性衰减,2为平方衰减,以此类推。 importjava.util.Date; importjava.util.Random; publicclass LotteryTool { private double factor; private double probability; private Random rand; private LotteryTool(double probability, long expireTime, int reduce){ this.factor = (double) System.currentTimeMillis() / expireTime; this.probability = probability * Math.pow(factor, reduce); this.rand = new Random(System.currentTimeMillis()); } public static LotteryTool getInstance(double probability, longexpireTime, int reduce) { return new LotteryTool(probability, expireTime, reduce); } public boolean isLucky(long expected) { long token = generateLong(); expected = expected % (int) (1 / probability); ...

签名算法 我们使用非对称加密算法的时候，对于一个公钥-私钥对，通常是用公钥加密，私钥解密。 如果使用私钥加密，公钥解密是否可行呢？实际上是完全可行的。 不过我们再仔细想一想，私钥是保密的，而公钥是公开的，用私钥加密，那相当于所有人都可以用公钥解密。这个加密有什么意义？ 这个加密的意义在于，如果小明用自己的私钥加密了一条消息，比如小明喜欢小红，然后他公开了加密消息，由于任何人都可以用小明的公钥解密，从而使得任何人都可以确认小明喜欢小红这条消息肯定是小明发出的，其他人不能伪造这个消息，小明也不能抵赖这条消息不是自己写的。 因此，私钥加密得到的密文实际上就是数字签名，要验证这个签名是否正确，只能用私钥持有者的公钥进行解密验证。使用数字签名的目的是为了确认某个信息确实是由某个发送方发送的，任何人都不可能伪造消息，并且，发送方也不能抵赖。 在实际应用的时候，签名实际上并不是针对原始消息，而是针对原始消息的哈希进行签名，即： signature = encrypt(privateKey, sha256(message)) 对签名进行验证实际上就是用公钥解密： hash = decrypt(publicKey, signature) 然后把解密后的哈希与原始消息的哈希进行对比。 因为用户总是使用自己的私钥进行签名，所以，私钥就相当于用户身份。而公钥用来给外部验证用户身份。 常用数字签名算法有： MD5withRSA SHA1withRSA SHA256withRSA 它们实际上就是指定某种哈希算法进行RSA签名的方式。 DSA签名 除了RSA可以签名外，还可以使用DSA算法进行签名。DSA是Digital Signature Algorithm的缩写，它使用ElGamal数字签名算法。 DSA只能配合SHA使用，常用的算法有： SHA1withDSA SHA256withDSA SHA512withDSA 和RSA数字签名相比，DSA的优点是更快。 ECDSA签名 椭圆曲线签名算法ECDSA：Elliptic Curve Digital Signature Algorithm也是一种常用的签名算法，它的特点是可以从私钥推出公钥。比特币的签名算法就采用了ECDSA算法，使用标准椭圆曲线secp256k1。BouncyCastle提供了ECDSA的完整实现。 https://www.liaoxuefeng.com/wiki/1252599548343744/1304227943022626

字符串匹配算法总结 KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦！ 老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。 其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢？笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为？ 说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢？？琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。 下面贴上一位兄弟写的算法总结,很简单 (建议KMP部分就不用看了,看了费脑子) 。 参见: http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html 趁着做Presentation的功夫,顺便做一个总结 字符串匹配: -willamette 在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring) **-: ** Brute Force(BF或蛮力搜索) **算法: ** 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。 速度最慢。 那么,怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^ 注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。 **-: KMP算法 ** 首先介绍的就是KMP 算法。 原始论文: Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977. 这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible ( 业内人士一般简称TAOCP). 稍稍提一下,有个叫H.A.Simon 的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ 的Politics PhD ,可谓全才。 ...

共识算法,一致性算法, consensus algorithm PoW，PoS，DPoS，PBFT，Paxos，Raft 分布式一致性算法-Paxos、Raft、ZAB、Gossip https://zhuanlan.zhihu.com/p/130332285 ZAB算法 说明：ZAB也是对Multi Paxos算法的改进，大部分和raft相同 和raft算法的主要区别： 对于Leader的任期，raft叫做term，而ZAB叫做epoch 在状态复制的过程中，raft的心跳从Leader向Follower发送，而ZAB则相反。

二分法, binary search algorithm 二分法 一，学习别人的总结与讲解 本部分的参考见末尾，本部分文字是在其基础上的二度总结 (节约时间和精力）。 典型的二分法 算法：当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。 基本思想：假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较， 如果当前位置arr[k]值等于key，则查找成功； 若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]； 若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]， 直到找到为止,时间复杂度:O(log(n))。 上面的思想就是最最简单的二分法，即从一个排好序的数组之查找一个key值。 如下面的程序： int search(int *arr, int n, int key) { int left = 0, right = n-1; while(left<=right) { //慎重截止条件，根据指针移动条件来看，这里需要将数组判断到空为止 int mid = left + ((right - left) >> 1); //防止溢出 if (arr[mid] == key) //找到了 return mid; else if(arr[mid] > key) right = mid - 1; //给定值key一定在左边，并且不包括当前这个中间值 else left = mid + 1; //给定值key一定在右边，并且不包括当前这个中间值 } return -1; } 证明二分算法正确性 循环不变式： 如果key存在于数组中，始终只可能存在于当前的array[left,right]数组段中。 初始化： 第一轮循环开始之前，array[left,right]就是原始数组，这时循环不变式显然成立。 迭代保持： 每次循环开始前，如果key存在，则只可能在待处理数组array[left, ..., right]中。 对于array[mid]<key，array[left, ..., mid]均小于key，key只可能存在于array[mid+1, ..., right]中； 对于array[mid]>key，array[mid, ..., right]均大于key，key只可能存在于array[left, ..., mid-1]中； 对于array[mid]==key，查找到了key对应的下标，直接返回结果。 显然如果没找到key，下一次继续查找时我们设定的循环不变式依然正确。 死循环否？在前两种情况中，数组长度每次至少减少1 (实际减少的长度分别是mid-left+1和right-mid+1），直到由left==right变为left>right (数组段长度由1-0）—>截止了，所以一定不会死循环。 终止： 结束时发生了什么？left>right,被压缩的数组段为空，表示key不存在于所有步骤的待处理数组，再结合每一步排除的部分数组中也不可能有key，因此key不存在于原数组。因此我们得到了符合要求的解，此算法正确。 如果条件稍微变化一下，还会写吗？其实，二分法真的不那么简单，尤其是二分法的各个变种。 二分法的变种1 数组之中的数据可能可以重复，要求返回匹配的数据的最小 (或最大）的下标；更近一步，需要找出数组中第一个大于key的元素 (也就是最小的大于key的元素的）下标，等等。 这些，虽然只有一点点的变化，实现的时候确实要更加的细心。 下面列出了这些二分检索变种的实现 a. 找出第一个与key相等的元素的位置 快速思考四个问题： 1）通过什么条件来移动两个指针？与中间位置进行大小比较。 当arr[mid]<key时，当前位置一定不是解，解一定只可能在arr[mid+1,high]，即右边 当arr[mid]>key时，当前位置一定不是解，解一定只可能在arr[low,mid-1]，即左边 ...

一致性哈希算法与Java实现 一致性哈希算法, consistent hashing 概述 引出 登场 改进-虚节点 另一种改进 参考链接: 概述 在维基百科中，是这么定义的 一致哈希是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数 (大小) 的改变平均只需要对 K/n个关键字重新映射，其中K是关键字的数量， n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。 引出 我们在上文中已经介绍了一致性Hash算法的基本优势，我们看到了该算法主要解决的问题是: 当slot数发生变化时，能够尽量少的移动数据。那么，我们思考一下，普通的Hash算法是如何实现？又存在什么问题呢？ 那么我们引出一个问题: 假设有1000w个数据项，100个存储节点，请设计一种算法合理地将他们存储在这些节点上。 看一看普通Hash算法的原理: normal_hash 算法的核心计算如下 1 2 3 4 5 6 for item in range(ITEMS): k = md5(str(item)).digest() h = unpack_from(">I", k)[0] # 通过取余的方式进行映射 n = h % NODES node_stat[n] += 1 具体的完整实现请参考normal_hash.py，输出是这样的: Ave: 100000 Max: 100695 (0.69%) Min: 99073 (0.93%) 从上述结果可以发现，普通的Hash算法均匀地将这些数据项打散到了这些节点上，并且分布最少和最多的存储节点数据项数目小于1%。之所以分布均匀，主要是依赖Hash算法 (实现使用的MD5算法) 能够比较随机的分布。 然而，我们看看存在一个问题，由于该算法使用节点数取余的方法，强依赖node的数目，因此，当是node数发生变化的时候，item所对应的node发生剧烈变化，而发生变化的成本就是我们需要在node数发生变化的时候，数据需要迁移，这对存储产品来说显然是不能忍的，我们观察一下增加node后，数据项移动的情况: 1 2 3 4 5 6 7 8 9 for item in range(ITEMS): k = md5(str(item)).digest() h = unpack_from(">I", k)[0] # 原映射结果 n = h % NODES # 现映射结果 n_new = h % NEW_NODES if n_new != n: change += 1 详细实现代码在normal_hash_add.py输出是这样的: Change: 9900989 (99.01%) 翻译一下就是，如果有100个item，当增加一个node，之前99%的数据都需要重新移动。 这显然是不能忍的，普通哈希算法的问题我们已经发现了，如何对其进行改进呢？没错，我们的一致性哈希算法闪亮登场。 登场 我们上节介绍了普通Hash算法的劣势，即当node数发生变化 (增加、移除) 后，数据项会被重新"打散"，导致大部分数据项不能落到原来的节点上，从而导致大量数据需要迁移。 那么，一个亟待解决的问题就变成了: 当node数发生变化时，如何保证尽量少引起迁移呢？即当增加或者删除节点时，对于大多数item，保证原来分配到的某个node，现在仍然应该分配到那个node，将数据迁移量的降到最低。 一致性Hash算法的原理是这样的: consist_hash 1 2 3 4 5 6 7 8 9 10 for n in range(NODES): h = _hash(n) ring.append(h) ring.sort() hash2node[h] = n for item in range(ITEMS): ...

B树(B-tree), B+树(B+-tree),B树(B-tree) B树(B-tree), B+树(B+-tree), B*树(B*-tree) B树(B-tree) 一颗m阶的B树定义如下： 1）每个结点最多有m-1个关键字。 2）根结点最少可以只有1个关键字。 3）非根结点至少有Math.ceil(m/2)-1个关键字。 4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。 5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。 注意: 之前有看到有很多文章把B树和B-tree理解成了两种不同类别的树，其实这两个是同一种树; 概念： B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树 (查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构，让我们来看看他有什么特点; 规则： (1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则； (2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外 (注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）； (3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个 (注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2); (4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子; 最后我们用一个图和一个实际的例子来理解B树 (这里为了理解方便我就直接用实际字母的大小来排列C>B>A） B树的查询流程： 如上图我要从上图中找到E字母，查找流程如下 (1）获取根节点的关键字进行比较，当前根节点关键字为M，E<M (26个字母顺序），所以往找到指向左边的子节点 (二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）； (2）拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点； (3）拿到E和F，因为E=E 所以直接返回关键字和指针信息 (如果树结构里面没有包含所要查找的节点则返回null）； B树的插入节点流程 定义一个5阶树 (平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来; 遵循规则： (1）节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1 (这里关键字数>4就要进行节点拆分）； (2）排序规则：满足节点本身比左边节点大，比右边节点小的排序规则; 先插入 3、8、31、11 再插入23、29 再插入50、28 B树节点的删除 规则： (1）节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil (5/2） (这里关键字数<2就要进行节点合并）； (2）满足节点本身比左边节点大，比右边节点小的排序规则; (3）关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放； 特点： B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理 (磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度; 3、B+树 概念 B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别 规则 (1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加； (2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样； (3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。 (4）非叶子节点的子节点数=关键字数 (来源百度百科） (根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1 (来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）; ...

环形队列 环形队列, circle queue 环形缓冲区 (ring buffer）也称作循环缓冲区 (cyclic buffer）、圆形队列 (circular queue）、圆形缓冲区 (circular buffer） 环形队列是在实际编程极为有用的数据结构,它有如下特点。 它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。 因为有简单高效的原因，甚至在硬件都实现了环形队列. 环形队列广泛用于网络数据收发，和不同程序间数据交换 (比如内核与应用程序大量交换数据,从硬件接收大量数据) 均使用了环形队列. 一.环形队列实现原理 内存上没有环形的结构，因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢？它将转回到0位置来处理。这个的转回是通过取模操作来执行的。 因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。 为了方便读写，还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置，tail指向可以写的位置。 环形队列的关键是判断队列为空，还是为满。当tail追上head时，队列为满时，当head追上tail时，队列为空。但如何知道谁追上谁。还需要一些辅助的手段来判断. 如何判断环形队列为空，为满有两种判断方法。 一.是附加一个标志位tag 当head赶上tail，队列空，则令tag=0, 当tail赶上head，队列满，则令tag=1, 二.限制tail赶上head，即队尾结点与队首结点之间至少留有一个元素的空间。 队列空: head==tail 队列满: (tail+1)% MAXN ==head