存档

文章标签 ‘数学之美’

信息指纹 [数学之美学习笔记]

2011年10月27日 没有评论

---

Hash与信息指纹有什么关系?为什么要用信息指纹?

最近在整理布隆过滤器相关资料的时候,觉得有必要提一下信息指纹和MD5.

不得不承认,自己以前使用hash的方法弱爆了,借《数学之美》的文章记录一下从哈希到信息指纹的缘由。

回忆一下以前使用hash的时候:

情景一:


Java: HashTable<string,int> ht = new HashTable<string,int> ();

C++: map<string,int> m;

其实平时这样用也无所谓,但是数据量大了,string就不好办了。

情景二:

以前自己写过一个爬虫,当时存储URL的时候直接就是以字符串的形式存储的,测试时有的url非常长,当时虽然感觉挺费空间的,但还是偷懒了,逃避困难逃避改变导致了今天的幼稚,所以直面问题,加紧充电,爬虫的重写也在最近的计划中,MD5,布隆过滤器应该都能用到。

入正题,hash为什么要用信息指纹?请看下面的例子

任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的“指纹”。

在爬虫中网址的消重上,需要在哈希表中纪录已经访问过的网址(URL)。假设现在要存储在哈希表中如果以字符串的形式直接存储网址,既费内存空间,又浪费查找时间。

阅读全文...

布隆过滤器(Bloom Filter)

2011年10月23日 没有评论

---

最初知道布隆过滤器是通过数学之美了解的,后来学习算法时,09年在西交BBS算法版上偶然看到一篇帖子,讲海量数据处理的,也提到了布隆过滤器,后来的学习过程中发现网上转载的相关文章铺天盖地,参差不一,大部分是一个概述性的东西,要真正为我所用还需要一个深入的思考和细致的分析,本博力求做到这样的思考和分析,对bloom filter做一个详细的总结,所涉参考文献也将一并给出,欢迎讨论。

本帖希望在了解bloom filter的基础上能分析解决实际问题,并实现其代码加深理解,拟包含以下几方面:

欢迎关注并讨论。

阅读全文...