Algorithm

算法效率, 算法分析 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

抽奖概率-三种算法 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

共识算法,一致性算法, 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