Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，采用Bloom Filter的数据结构，可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍，不太懂的博友可以看看。
可以用来实现数据字典，进行数据的判重，或者集合求交集 继续阅读全文
大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。
下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。
本贴从解决这类问题的方法入手，开辟一系列专题来解决海量数据问题。拟包含 以下几个方面。
在这些解决方案之上，再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。
这是在网上找到的一道百度的面试题：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
【分析】：要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。所以我们可以基于这个思路分两步来设计该算法。下面分别给出这两步的算法： 继续阅读全文
1.为什么基类的析构函数是虚函数？
答：编译器总是根据类型来调用类成员函数。但是一个派生类的指针可以安全地转化为一个基类的指针。这样删除一个基类的指针的时候，C++不管这个指针指向一个基类对象还是一个派生类的对象，调用的都是基类的析构函数而不是派生类的。如果你依赖于派生类的析构函数的代码来释放资源，而没有重载析构函数，那么会有资源泄漏。所以建议的方式是将析构函数声明为虚函数。如果你使用MFC，并且以CObject或其派生类为基类，那么MFC已经为你做了这件事情；CObject的析构函数是虚函数。一个函数一旦声明为虚函数，那么不管你是否加上virtual 修饰符，它在所有派生类中都成为虚函数。但是由于理解明确起见，建议的方式还是加上virtual 修饰符。
2.Union和sturct区别（是以选择题形式出现，一个具体的例子）
答：1. struct和union都是由多个不同的数据类型成员组成, 但在任何同一时刻, union中只存放了一个被选中的成员, 而struct的所有成员都存在。在struct中，各成员都占有自己的内存空间，它们是同时存在的。一个struct变量的总长度等于所有成员长度之和。在Union中，所有成员不能同时占用它的内存空间，它们不能同时存在。Union变量的长度等于最长的成员的长度。 2. 对于union的不同成员赋值, 将会对其它成员重写, 原来成员的值就不存在了, 而对于struct的不同成员赋值是互不影响的。
继续阅读全文
STL算法学习，小结如下：
前提:
下载stl源码： http://www.sgi.com/tech/stl/download.html
打开网页： http://www.sgi.com/tech/stl/stl_index.html
一 函数对象： 因为很多的算法中多使用了函数对象
二元函数对象，V1和V2为输入，V3为结果 继续阅读全文
目前以lib后缀的库有两种，一种为静态链接库(Static Libary，以下简称“静态库”)，另一种为动态连接库(DLL，以下简称“动态库”)的导入库(Import Libary，以下简称“导入库”）。
静态库是一个或者多个obj文件的打包，所以有人干脆把从obj文件生成lib的过程称为Archive，即合并到一起。比如你链接一个静态库，如果其中有错，它会准确的找到是哪个obj有错，即静态lib只是壳子。
动态库一般会有对应的导入库，方便程序静态载入动态链接库，否则你可能就需要自己LoadLibary调入DLL文件，然后再手工GetProcAddress获得对应函数了。有了导入库，你只需要链接导入库后按照头文件函数接口的声明调用函数就可以了。
导入库和静态库的区别很大，他们实质是不一样的东西。静态库本身就包含了实际执行代码、符号表等等，而对于导入库而言，其实际的执行代码位于动态库中，导入库只包含了地址符号表等，确保程序找到对应函数的一些基本地址信息。 继续阅读全文
昨天花了一个晚上为《编程之美》，在豆瓣写了一篇书评《迟来的书评和感想──给喜爱编程的朋友》。书评就不转载到这里了，取而代之，在这里介绍书里其中一条问题的另一个解法。这个解法比较简短易读及降低了空间复杂度，或者可以说觉得比较「美」吧。
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义”距离”为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
C++中的虚函数的作用主要是实现了多态的机制。关于多态，简而言之就是用父类型别的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”，这是一种泛型技术。所谓泛型技术，说白了就是试图使用不变的代码来实现可变的算法。比如：模板技术，RTTI技术，虚函数技术，要么是试图做到在编译时决议，要么试图做到运行时决议。
关于虚函数的使用方法，我在这里不做过多的阐述。大家可以看看相关的C++的书籍。在这篇文章中，我只想从虚函数的实现机制上面为大家 一个清晰的剖析。
当然，相同的文章在网上也出现过一些了，但我总感觉这些文章不是很容易阅读，大段大段的代码，没有图片，没有详细的说明，没有比较，没有举一反三。不利于学习和阅读，所以这是我想写下这篇文章的原因。也希望大家多给我提意见。
言归正传，让我们一起进入虚函数的世界。 继续阅读全文
一、Debug 和 Release 编译方式的本质区别
Debug 通常称为调试版本，它包含调试信息，并且不作任何优化，便于程序员调试程序。Release 称为发布版本，它往往是进行了各种优化，使得程序在代码大小和运行速度上都是最优的，以便用户很好地使用。
Debug 和 Release 的真正秘密，在于一组编译选项。下面列出了分别针对二者的选项（当然除此之外还有其他一些，如/Fd /Fo，但区别并不重要，通常他们也不会引起 Release 版错误，在此不讨论） 继续阅读全文
对于一个c/c++程序员来说，内存泄漏是一个常见的也是令人头疼的问题。已经有许多技术被研究出来以应对这个问题，比如Smart Pointer，Garbage Collection等。Smart Pointer技术比较成熟，STL中已经包含支持Smart Pointer的class，但是它的使用似乎并不广泛，而且它也不能解决所有的问题；Garbage Collection技术在Java中已经比较成熟，但是在c/c++领域的发展并不顺畅，虽然很早就有人思考在C++中也加入GC的支持。现实世界就是这样的，作为一个c/c++程序员，内存泄漏是你心中永远的痛。不过好在现在有许多工具能够帮助我们验证内存泄漏的存在，找出发生问题的代码。 继续阅读全文