• 基本场景
• hash算法和单调性
• consistent hashing算法的原理
  • 环形hash空间
  • 把对象映射到hash空间
  • 把cache映射到hash空间
  • 把对象映射到cache
  • 考察cache的变动
    • 移除cache
    • 添加 cache
• 虚拟节点
  • 平衡性
• 总结

转帖：一致性哈希算法

Consistent Hashing算法早在1997年就在论文《Consistent hashing and random trees》 (https://dl.acm.org/citation.cfm?id=258660)中被提出，目前在cache系统中应用越来越广泛。

基本场景

比如你有N个cache服务器（后面简称cache），那么如何将一个对象object映射到N个cache 上呢，你很可能会采用类似下面的通用方法计算object的hash值，然后均匀的映射到到N个cache；
hash(object)%N
一切都运行正常，再考虑如下的两种情况；

• 一个cache服务器m down掉了（在实际应用中必须要考虑这种情况），这样所有映射到cache m的对象都会失效，怎么办，需要把cache m从cache中移除，这时候cache是N-1台，映射公式变成了hash(object)%(N-1)。
• 由于访问加重，需要添加cache，这时候cache是N+1台，映射公式变成了hash(object)%(N+1)

意味着什么？这意味着突然之间几乎所有的cache都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器；
再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的 hash算法也做不到。
有什么方法可以改变这个状况呢，这就是Consistent Hashing。

• 题目描述
• 解法
  • 解法1
  • 解法2
  • 解法3
  • 解法4:如果N非常非常大
  • 解法5
• 网络上其他文章
• 参考

题目描述

有很多个无序的数，怎么选出其中最大的若干个数？
即，从n个数中选出最大的K个数。

解法

解法1

先假设元素的数量不大，例如在几千个左右，在这种情况下，我们就排序吧。
在这里，快速排序或堆排序都是不错的选择，他们的平均时间复杂度都是$O(n\log_2n)$，然后取出前K个，O(K)。
总的时间复杂度仍然是$O(n\log_2n)$。
可以注意到，即便是K=1的情况，上面的算法复杂度仍然是$O(n\log_2n)$，而显然，我们可以通过n-1此的比较和交换得到结果，不需要对整个数组进行排序。
要避免做后面n-K个数的排序，可以使用部分排序算法，选择排序和冒泡排序都是不错的选择。
把n个数中的前K个数排序出来，复杂度是O(n*K)。
哪一个更好呢？$O(n\log_2n)$和O(n*K)？这取决于K的大小，在K<$\log_2n$的情况下，可以选择部分排序。

解法2

回忆一下快速排序，快排中的每一步，都是将数据分为两组，其中一组的任何数都小于另一组中的任何数，不断地对数据进行分割直到不能再分即完成排序。
假设n个数存储在数组S中，从S中找出一个元素X，它把数组分为比它大的和比它小的两部分，假设比它大的一部分数组是$S_{max}$，比它小的部分是$S_{min}$。
这时有两种可能：

1. $S_{max}$中元素不足K个，说明$S_{max}$中的所有数和$S_{min}$中最大的K-|$S_{max}$|个元素就是数组S中最大的K个数；
2. $S_{max}$中元素的个数大于或等于K，则需要返回$S_{max}$中最大的K个元素。

这样递归下去，问题的规模不断地变小，平均时间复杂度O(n * $\log_2K$)。

• 概述
• 解题思路
  • 选择价值最大的物品，放入背包。
  • 选择重量最轻的物品，放入背包。
  • 单位重量价值最大的物品，放入背包。
• 程序代码
  • 伪代码
  • Java代码
  • C++代码

概述

给定N个物品和一个容量为C的背包，物品i的重量是Wi，其价值为Vi，背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大，但不能超过总容量。在背包问题中可以将物品的一部分装入背包（物品可以拆分的装入背包），但不能重复装入。

解题思路

用贪心法求解背包问题的关键是如何选定贪心策略，使得按照一定的顺序选择每个物品，并尽可能的装入背包，直到背包装满。
至少有三种看似合适的贪心策略。

选择价值最大的物品，放入背包。

因为这可以尽可能快的增加背包的总价值，但是，虽然每一步选择获得了背包价值的极大增长，但背包容量却可能消耗的太快，使得装入背包的物品个数减少，从而不能保证目标函数达到最大。

选择重量最轻的物品，放入背包。

因为这可以装入尽可能多的物品，从而增加背包的总价值。但是，虽然每一步选择使背包的容量消耗的慢了，但背包的价值却没能保证迅速的增长，从而不能保证目标函数达到最大。

单位重量价值最大的物品，放入背包。

最大价值和最大重量两种贪心策略或者只考虑背包价值的增长，或者只考虑背包容量的消耗，而为了求得背包问题的最优解，需要在背包价值增长和背包容量消耗二者之间寻找平衡。正确的贪心策略是选择单位重量价值最大的物品。
例如：有三个物品，其重量分别为{20,30,10}，价值分别为{60,120,50}，背包的容量为50，应用三种贪心策略装入背包的物品和获得的价值如下图所示：

• 概述
• 解题思路
  • 有2种解题方法
    • 迭代方法
    • 递归方法
• 程序代码
  • 迭代方法
    • 伪代码
    • C++版本
    • Java版本
  • 递归方法

概述

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间$s_i$和一个结束时间$f_i$，且$s_i$<$f_i$。如果选择了活动i，则它在半开时间区间[$s_i$, $f_i$)内占用资源。若区间[$s_i$, $f_i$)与区间[$s_j$, $f_j$)不相交，则称活动i与活动j是相容的。也就是说，当$s_i$≥$f_j$或$s_j$≥$f_i$时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

解题思路

假定活动已按结束时间的单调递增顺序排序（小到大排序）：f1 ≤ f2 ≤ f3 ≤....≤ fn-1 ≤ fn
用i代表第i个活动，s[i]代表第i个活动开始时间，f[i]代表第i个活动的结束时间。按照从小到大排序，挑选出结束时间尽量早的活动，并且满足后一个活动的起始时间晚于前一个活动的结束时间，全部找出这些活动就是最大的相容活动子集合。
事实上系统一次检查活动i是否与当前已选择的所有活动相容。若相容活动i加入已选择活动的集合中，否则，不选择活动i，而继续i位置的下一个活动与集合A中活动比较相容性（集合A中的活动也就是上次比较的活动）。若活动i与之相容，则i成为最近加入集合A的活动，并取代活动j的位置（迭代方法）。

有2种解题方法

迭代方法

每次总是选择具有最早完成时间的相容活动加入集合A中（默认第1个加入集合A中）。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间（因为添加到集合A中的时间最短，剩余的时间就长）。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
迭代方法的计算过程如下图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。
若被检查的活动i的开始时间$s_i$小于最近选择的活动j的结束时间$f_i$，则不选择活动i，否则选择活动i加入集合A中。

迭代方法的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

• 引言
• 概念
• 基本思想
  • 重要特性
  • 存在问题
  • 最大特点
• 步骤

引言

平时购物找钱时，为了使找回零钱的硬币数最少，从最大面值的币种开始，按递减的顺序考虑币种，先尽量用大面值的币种，当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就贪心算法。这种方法在这里总是最优的，是因为银行对其发行的硬币种类和硬币面值的巧妙安排。
如果面值分别为1,5,11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应该找1个11单位的硬币和4个1单位的硬币，总共找回5个硬币。但最优的解答是3个5单位面值硬币。
贪心算法并不是一个具体的算法，而是一种算法的思想，或者说是解决问题一种思路。
永远没有最好的算法，只有最适合的算法，我们选用贪心算法的原因就是因为它能够满足当前的需要并且比其他算法更加简单。

概念

贪心算法并不是整体最优考虑，它所做出的选择只是在某种意义上的局部最优（总是做出在当前看来是最好的选择）。这种局部最优选择并不能保证总能获得全局最优解，但它通常可以获得较好的近似最优解。
贪心算法在解决问题的策略上是仅根据当前已有的信息做出选择，而且一旦做出选择，不管将来有什么结果，这个选择不会改变。
贪心算法一般在开始策略选择前会进行排序，排好序后就进行最优化选择。

• 概述
• 解题思路
• 程序代码
  • 代码1
  • 代码2

概述

以一个M×N的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。

解题思路

可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径。

• 概述
• 解题思路
• 程序代码

概述

掌握调度问题的处理方法，实现最佳调度问题的回溯解决。

解题思路

一个深度为N的M叉树。
基本思路：

• 搜索从开始结点（根结点）出发，以DFS搜索整个解空间。
• 每搜索完一条路径则记录下besttime和bestx[]序列
• 开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。
• 如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。
• 此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。

• 概述
• 解题思路
  • 解题思路
• 程序代码
  • 代码1
  • 代码2
  • 代码3
  • 代码4
  • 代码5
  • 代码6

概述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上（反斜线），问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n × n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

• 引言
• 概念
• 基本思想
• 步骤

引言

寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。
不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。
对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。

概念

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法（一种选优搜索法，按选优条件向前搜索，以达到目标）。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为：回溯法，而满足回溯条件的某个状态的点称为：“回溯点”。
回溯法实际是穷举算法，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。
许多复杂的，规模较大的问题都可以使用回溯法，回溯算法有“通用解题方法”的美称，其采用了一种“走不通就掉头”思想作为其控制结构，用它可以求出问题的所有解和任意解。
它的应用很广泛，很多算法都用到回溯法，例如，迷宫，八皇后问题，图的m着色总是等都用到回溯法，当然其中还使用了其他策略。

• 问题
• 解题
  • 分治法
    • 思路
    • 三种情况
    • C版本
    • Java版本
      • 1
      • 2
  • 动态规划法
    • C版本
    • Java版本
      • 1
      • 2

问题

概念：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为：Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n。
一个数组a[]：需要求最大子段和的数组；
一个数组b[]：数组a子段和的数组，{a[0]，a[0]+a[1]，a[0]+a[1]+a[2]...........}；
例如，当(a[1],a[2],a[3],a[4],a[5],a[6])=(-2,11,-4,13,-5,-2)时，最大子段和为20。

解题

分治法

思路

如果将所给的序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段的最大子段和，则a[1:n]的最大子段和：
a[]:1..........................n
分段处理:1..........n/2........n

三种情况

• a[1:n]的最大子段和与a[1:n/2]的最大子段和相同（左边的子段和）
• a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同（右边的子段和）
• a[1:n]的最大子段和为a[i]+…+a[j]，并且1<=i<=n/2,n/2+1<=j<=n。（子段和=左边子段和+右边子段和）

对于（1）和（2）两种情况可递归求得，但是对于情况（3），容易看出a[n/2],a[n/2+1]在最大子段中。
第3种情况：我们可以在a[1:n/2]中计算出s1=max(a[n/2]+a[n/2-1]+…+a[i]),0<=i<=n/2，并在a[n/2+1:n]中计算出s2= max(a[n/2+1]+a[n/2+2]+…+a[i]),n/2+1<=i<=n。则s1+s2为出现情况（3）的最大子段和。