常用HASH算法 代码 & 比较

  • 常用的字符串Hash函数还有ELFHash,APHash等等,都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数,这些函数几乎不可能找到碰撞。
  • 常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。

Continue reading “常用HASH算法 代码 & 比较”

B树和B+树的总结

B树

为什么要B树

磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。 Continue reading “B树和B+树的总结”

rsync的核心算法

rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync可拷贝/显示目录属性,以及拷贝文件,并可选择性的压缩以及递归拷贝。rsync利用由Andrew Tridgell发明的算法。这里不介绍其使用方法,只介绍其核心算法。我们可以看到,Unix下的东西,一个命令,一个工具都有很多很精妙的东西,怎么学也学不完,这就是Unix的文化啊。

本来不想写这篇文章的,因为原先发现有很多中文blog都说了这个算法,但是看了一下,发现这些中文blog要么翻译国外文章翻译地非常烂,要么就是介绍这个算法介绍得很乱让人看不懂,还有错误,误人不浅,所以让我觉得有必要写篇rsync算法介绍的文章。(当然,我成文比较仓促,可能会有一些错误,请指正) Continue reading “rsync的核心算法”

分布式系统的Raft算法

过去,Paxos一直是分布式协议的标准,但是Paxos难于理解,更难以实现,Google的分布式锁系统Chubby作为Paxos实现曾经遭遇到很多坑。

来自Stanford的新的分布式协议研究称为Raft,它是一个为真实世界应用建立的协议,主要注重协议的落地性和可理解性。

在了解Raft之前,我们先了解Consensus一致性这个概念,它是指多个服务器在状态达成一致,但是在一个分布式系统中,因为各种意外可能,有的服务器可能会崩溃或变得不可靠,它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议,一致性协议是为了确保容错性,也就是即使系统中有一两个服务器当机,也不会影响其处理过程。

为了以容错方式达成一致,我们不可能要求所有服务器100%都达成一致状态,只要超过半数的大多数服务器达成一致就可以了,假设有N台服务器,N/2 1 就超过半数,代表大多数了。

Paxos和Raft都是为了实现Consensus一致性这个目标,这个过程如同选举一样,参选者需要说服大多数选民(服务器)投票给他,一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。

Continue reading “分布式系统的Raft算法”

需找新的美猴王——约瑟夫环 猴王问题

猴王问题:
某森林中有n只猴子在商量猴王选举问题,所有的猴子都想当猴王,
因此大家商量了一个选举办法如下:
所有的猴子围成一圈,先从第一个猴子开始报数,报数到13的猴子就出列。
紧接着的下一个猴子,又从1开始进行新的一轮报数,报数到12的猴子再出列;
依此重复下去,每一轮报数都比上一轮的报数少1,直到报数减为1之后,又从13开始报数。
直到原列中只剩下一个猴子为止,这个猴子就是猴王。

 

试设计一个程序求出猴王。
Continue reading “需找新的美猴王——约瑟夫环 猴王问题”

海量数据处理:十道面试题与十个海量数据处理方法总结

第一部分、十道海量数据处理面试题

1、海量日志数据,提取出某日访问百度次数最多的那个IP。

      首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法, 比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大 的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

或者如下阐述(雪域之鹰):
算法思想:分而治之+Hash
1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理; 
2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址; 
3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;

Continue reading “海量数据处理:十道面试题与十个海量数据处理方法总结”

海量数据搜索算法优化-存储、查询、排序算法

海量数据库的应用,如国家的人口管理系统,户籍档案管理系统,在这样的海量数据库应用中,数据库的存储设计和结构优化(如索引优化)、数据库的查询优化及分页算法尤为重要!

随着互联网的日益普及,海量信息的增长,网格运算的到来,海量数据存储产品和海量数据存储技术方案的需求更为市场所需。

同时,实际的海量数据处理,更是涉及很多细节,包括海量数据存储(物理存储、逻辑存储、海量数据库的备份)、数据采集、海量数据查询(海量数据分页、海量数据排序)、海量数据安全和管理等。
 

Continue reading “海量数据搜索算法优化-存储、查询、排序算法”

Google校园招聘题: 程序员买房

Google的2011年校园招聘宣讲会分别在北大和清华举行,其中北大本来是350人的会场,去了大约600多人,爆满,那场面绝对是人山人海, 彩旗飘飘。经过了大约一个小时多的宣讲和问答,开始现场笔试环节,一共10个选择题和三个算法题,只有选择题答对了6个以上的人才有机会让面试官看你后面 的算法题。然后明天下午会通知笔试通过的人进行面试,Google的效率就像其搜索引擎一样迅速,效率可见一般。

其中前10个选择题中有一个特别雷人的,题如下:

现在北京有一套房子,价格200万,假设房价每年上涨10%,一个软件工程师每年固定能赚40万。如果他想买这套房子,不贷款,不涨工资,没有其他收入,每年不吃不喝不消费,那么他需要几年才能攒够钱买这套房子?

A, 5年

B, 7年

C, 8年

D, 9年

E, 永远买不起

Continue reading “Google校园招聘题: 程序员买房”

面试中常见的一些算法问题

Problem 1 : Is it a loop ? (判断链表是否有环?)

Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register?

方法:使用两个指针,从头开始,一个一次前进一个节点,一个前进2个节点,则最多2N,后两个指针可以重合;如果无环,则正常停止。同样的,可以找到链表的中间节点。同上。

Continue reading “面试中常见的一些算法问题”