原始论文：一致性哈希 本来不打算放的。。被批评说太不严谨orz.. 说说自己的理解好了。。 大概就是。。。hash的时候。。一开始有n个桶。。你设计的函数是y=x%n...看起来美滋滋。。。 然后这时候突然一个桶不见了。。。如果按照之前设计的hash函数。。就变成了x%(n-1)... 这可能会造成大量的数据改变自己之前所在的桶。。。这是不可接受的。。。 或者是。。。当前的桶不够用了。。要增加一个桶。。。变成了x%(n+1)。。。也会出现类似情况。。。 我们的目的就是设计一种算法。。。使得当减少一个桶或者增加一个桶的时候。。。。变化尽可能小。。。 并且希望以后新放入的数据尽可能到新的桶中（？ 桶是简化的模型。。。实际应用上。。。一致 …

参考：[wiki_FHS](http://Filesystem Hierarchy Standard) 其实这东西。。。虽然有一个统一的标准。。。但是不同发行版。。。或者同一个发行版的不同版本。。。差异貌似都蛮大的。。。所以只是理论上各个目录的作用。。。可能和具体的发行版不符。。。 Linux 目录 在 Linux 下，我们看到的是文件夹（目录）： 在早期的 UNIX 系统中，各个厂家各自定义了自己的 UNIX 系统文件目录，比较混乱。Linux 面世不久后，对文件目录进行了标准化，于1994年对根文件目录做了统一的规范，推出 FHS ( Filesystem Hierarchy Standard ) 的 Linux 文件系 …

参考链接 简要概述原理： 每个文件都由各种不同代码组成，比如01代码。这类文件只有数字0与1组合。 压缩原理就是 【通过寻找其中的规律，简化数字的排列】。 比如 00000110001111111111 可以简化成 5个0,2个1,3个0,10个1的排列 100000000000 可以简化成数学的 10^10 至于@yskin 说 没见过2G压缩到十几兆的。 实际上在极限压缩方式下其实28.1G压到25.8M都可以。 <img src="https://pic1.zhimg.com/893534a767ddb047cc04dd66e2a43900_b.jpg" …

参考博客 计组块忘光了呜呜呜。。。来复习一波。。 1. LRU 1.1. 原理 LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。 1.2. 实现 最常见的实现是使用一个链表保存缓存数据，详细算法实现如下： 1. 新数据插入到链表头部； 2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 3. 当链表满的时候，将链表尾部的数据丢弃。 1.3. 分析 【命中率】 当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。 【复杂度】 实现简单。 【 …

I want to match those five numbers 3, 7, 8, 9, 87 through regular express. Here is my thought: - match those four numbers `3 7 8 9` var `^[3|7|8|9]$` - match number `87` var `^87$` Then combine them together, `(^[3|7|8|9]$|^87$)`. With some test, it seems correct. Is there any way to do that more efficiently? …

转自：http://blog.csdn.net/v_july_v/article/details/6279498 第一部分、十道海量数据处理面试题 1、海量日志数据，提取出某日访问百度次数最多的那个IP。 首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。 或者如下阐述（雪域之鹰）： 算法思想：分而治 …

题意：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数，要求时间复杂度为O(1) 思路：标题党去死一死好么。。。真是无趣。。。就是用两个栈封装成一个。。。一个栈s1正常搞。。。一个是辅助栈s2。。每次去存min(value,s2.top()); 。。。我还以为什么黑科技。。。 class Solution { public: stack<int>s1,s2; void push(int value) { s1.push(value); if (s2.empty()||value<s2.top()) s2.push(value); else s2.push(s2.top()); } void …

题意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 思路：二分。。。注意有重复元素。。。 class Solution { public: int minNumberInRotateArray(vector<int> a) { int siz = a.size(); int l = 0 ; int r = siz-1; while (r-l>1) { int mid = (l+r)>>1; if (a[mid]>a[r]) l …

虽然说感觉这届学弟蛮厉害...不知道能不能拿到校内资格。。。 以及没有太多时间训练... 不过只要假期实习的地方。。。加班不是很多的话。。。 大概。。。晚上+周末。。。还是可以补补多校的。。。？ 其实有的时候。。。只是自以为自己不在意了。。。 到真正重要的时候。。。便会毫不犹豫得去再干一年吧。。。 只求顺利拿个银牌。。。 去年沈阳真的太可惜了。。。。。。。太气了。。。。 但愿一切顺利。。。让我拿个银牌吧orz

思路： 一个元素入队的时候直接插入到stack1中。。。 一个元素出队的时候。。。如果stack2不为空。。stack2顶的元素就是要出队的。。 如果stakc2为空。。。就将stack1清空，按照元素出栈的顺序依次入栈到stack2 class Solution { public: void push(int node) { stack1.push(node); } int pop() { if (stack2.size()!=0) { int ret = stack2.top(); stack2.pop(); return ret; } while (!stack1.empty()) { int val = …