算法 -- IT技术博客大学习 -- 共学习共进步！

本文将会从实际应用场景出发，介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景，借此介绍一致性哈希算法以及这个算法如何解决此问题；接下来会对这个算法进行相对详细的描述，并讨论一些如虚拟节点等与此算法应用相关的话题。

• WEB超链分析算法研究

万维网WWW（World Wide Web）是一个巨大的，分布全球的信息服务中心，正在以飞快的速度扩展。1998年WWW上拥有约3.5亿个文档[14]，每天增加约1百万的文档[6]，不到9个月的时间文档总数就会翻一番[14]。WEB上的文档和传统的文档比较，有很多新的特点，它们是分布的，异构的，无结构或者半结构的，这就对传统信息检索技术提出了新的挑战。传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档，也有基于目录分...

• 数学冷知识：不断取英文表达的字符数，最后总会得到数字4

这道题的答案有几个字母？答案：four。有趣的是，这是唯一的答案。如果令函数 f(n) 表示正整数 n 的英文表达中有多少个字母， n=4 是该函数的唯一不动点。

• 能否在等边三角形点阵中画一个正方形？

这是一个非常有趣的问题：能否在一个无限大的等边三角形点阵中选取四个点，使得这四个点恰好构成一个正方形？这个问题有一个非常简单巧妙的解法，你能想到吗？答案：不行。为了证明这一点，首先注意到，如果...

• 概率选取的实现

常常有这样的功能需求: 每次从一批候选项中随机选取其中一项, 要求每一项的出现都有一定的概率. 比如说, 有如下候选项和对应的概率: A:10%, B:5%, C:25%, D:60%. 现在, 把每一项的概率用一个正整数(概率值)来表示, 不使用百分率, 整数的总和不一定等于100, 可以是任意大小, 实际概率 = 概率值/总和 * 100% 概率选取的算法如下: 依次(顺序可随机)将各项按概率值从原点开始放在一维坐标上首尾相连, 这样, 每一项对应一个取值区间在...

• 浅谈MySQL索引背后的数据结构及算法

本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。

• Erlang supervisor的dynamic行为分析

在热升级的时候，针对supervisor管理的进程，需要知道它是由那个模块apply执行的。这样才能在模块代码发生变更的时候，好判断出该进程是否要做点升级的准备。所以规格书不仅仅是给supervisor模块用的，也给release handler模块用。其中的modules部分就是描述那些模块和这个进程有关系。对于gen_server, gen_fsm behaviour的模块来讲，它的进程由只有它自己spawn_link来的，所以很好理解填规格的时候，模块部分填他自己就好。但是gen_event这样的模块，由于一个事件通常会注册好几个模块，而且是动态的，所以规格书就不知道填什么，只好填dynamic. 在热升级需要知道模块的时候，即刻发消息现查询那些模块和这个进程相关。

• 数据分析中常用的数据模型

一、抽样分析模型建模方法首先确定统计的时间段，暂定为15天；从数据库中随机抽取若干名用户作为分析样本建立分析模型，模型图中假定抽样人数为100人，15天内最高使用量为200最少为15，在横坐标轴依次画出每人的使用量立柱图；然后向右侧画出最高点和最低点的水平引线；然后垂直划线连接水平线，得到上下交点之间的线段，分别在线段的中点和三分点处水平画出“中分线”“上分线”“下分线”。分析方法根据立柱图的分布比率确定...

• 简析搜索引擎中网络爬虫的搜索策略

随着互联网的兴起及发展，人们获取信息的途径由传统方式逐渐被网络替代。起初人们主要通过浏览网页来获取所需信息，但随着Web不断庞大用这种方式来寻找自己所需的信息变得越来越困难。现在大多数的人很大程度上依赖于搜索引擎来帮助自己获取有用信息，因此搜索引擎技术作为最典型的Web信息获取技术其发展直接影响人们获取信息的质量。自从1994 年4 月世界上第一个Web 检索工具Web Crawler 问世以来，目前较流行的搜索引擎已有...

• IMO2011趣题：总存在一条将会遍历所有点的直线

下面这个精彩的问题来自于刚刚结束的 IMO 2011 中的第 2 题：设 S 是平面上包含至少两个点的一个有限点集，其中没有三点在同一条直线上。所谓一个“风车”是指这样一个过程：从经过 S 中单独一点 P 的一条直线 l 开始，以 P 为旋转中心顺时针旋转，直至首次遇到 S 中的另一点，记为点 Q 。接着这条直线以 Q 为新的旋转中心顺时针旋转，直到再次遇到 S 中的某一点，这样的过程无...

• 变量在内存中的位置

进程的逻辑内存空间共享库和 mmap 内存映射数据段 (全局static和本地static，全局变量) 代码段堆(malloc ，引用) 栈 (本地变量，所以这个会是个随机数) 测试用程序

• 关于tokyocabinet的memory db 的filesize与使用内存的关系

存储的数据占用的内存大小file size为2G；但是物理内存占用为3.8G；我承认程序本身会占用一部分内存，100MB了不得了吧，那么其余的1.7G都做什么用了呢？

• 关于tokyocabinet的list操作

如果有多个进程同时对一个mdb(其它的没看，不敢随便乱说)执行list操作，结果会怎样；或许你会显得当然地认为相互没有太大关系，至少我开始时这么认为的，但是在看源码的时候，发现有些不太对劲儿，我们先看一下源码.....

• Acoustid 算法大致流程整理

图片在此算法中扮演了一个很重要的角色，当人们“看到”音频时，它通常都是形如下面的波形图：但是这种图对分析起来没有什么太大用，更有效的一种表现形式是声谱图，它描述了特定频率的强度随着时间的变化：可以通过把原始视频切割为许多重叠的帧并在其上应用傅立叶变换(或者快速傅立叶变换)来得到这种图片。许多声纹识别算法都是利用这种图片来工作的，...

• Doclist压缩方法简介

本文是作者在学习doclist压缩时的一点总结，希望以尽可能简单明了的方式描述各个算法的思想和适用场景，帮助同学们理解和比较。本文并不涉及具体的算法实现，代码请大家自行google。这里需要强调的是“所谓的改进顺序”只是作者yy出来方便理解记忆，并不反应真实的压缩方法发展历程。

• 淘宝搜索：定向抓取网页技术漫谈

网络爬虫（web crawler）又称为网络蜘蛛（web spider）是一段计算机程序，它从互联网上按照一定的逻辑和算法抓取和下载互联网的网页,是搜索引擎的一个重要组成部分。一般的爬虫从一部分start url开始，按照一定的策略开始爬取，爬取到的新的url在放入到爬取队列之中，然后进行新一轮的爬取，直到抓取完毕为止。我们看一下crawler一般会遇到什么样的问题吧：抓取的网页量很大网页更新量也很大，一般的网站，比如新闻，电子商务网...

• 字符串匹配那些事（一）

本系列文章主要介绍几种常用的字符串比较算法，包括但不限于蛮力匹配算法，KMP算法，BM算法，Horspool算法，Sunday算法，fastsearch算法，KR算法等等。本文主要介绍KMP算法和BM算法，它们分别是前缀匹配和后缀匹配的经典算法。所谓前缀匹配是指：模式串和母串的比较从左到右，模式串的移动也是从左到右；所谓后缀匹配是指：模式串和母串的的比较从右到左，模式串的移动从左到右。看得出来前缀匹配和后缀匹配的区别就仅仅在于比较...

• Hopscotch Hashing

这是一种开放地址HASH，主要目的是为了提高查询速度。提高查询速度常用的思路是在插入的时候对数据作调整，让数据更紧凑。常用的方法在HASH表比较满的情况下，复杂度都很难保证。这个方法的特点是，它可以保证最坏情况下，查询的复杂度也是个常数。元素X算HASH后，应该存在I节点，则允许它存在【I，I+H)之间第一个空闲的节点，H一般去32，一是H比较小，用一个INT作BITMAP就可以表示它后面哪些元素是HASH到这里的。二是，H太...

• 趣题：不用相似怎么办？

我老早就写过一个经典的小学几何题。如果你还没看过这个问题，你一定要去看看。一个小学奥数老师曾经告诉我，当年带领学生参加这次竞赛时，领队老师们都没有想到这个问题的“小学生解法”，以至于开始质疑这道题是否超纲了。看到答案后，老师们大为折服――这个问题确实有一个无需任何几何知识的妙解。今天，同样的事情发生了。今天临时去...

• 数学常数e的含义

e是一个重要的常数，但是我一直不知道，它的真正含义是什么。...