待完成的任务

了解：
1、Arrays.mergeSort排序算法
2、BigInteger的实现原理
3、红黑树的添加和删除操作实现
4、Collections各方法的相关实现
5、ORACLE怎么查找db_cache pool中的block，比如全表扫描怎么查找到所有的block。
6、学习apache，memcached、webservice、MYSQL


大数据量处理算法：
   1. Bloom Filter
   2. Hash
   3. Bit-Map
   4. 堆
   5. 双层桶划分
   6. 数据库索引
   7. 倒排索引（Inverted Index）
   8. 外排序
   9. Trie树
  10. MapReduce
1、bloom filter
转载：http://www.hellodba.net/2009/04/bloom_filter.html
设想以下的一个问题：有一个keyword的集合，我们需要快速判定某个keyword是否包含在其中。最简单的方法是遍历，但是效率很差。我们马上想到了hash的方法，因为在Oracle内部，hash无处不在。比如在cache buffer中找到某个block，在shared pool中找到某个SQL等等。我们可以把keyword的集合build成一个hash table，然后根据keyword计算hash值，通过是否落在相应的hash bucket中，这样就可以实现快速查找的目的。这个方法不错，但是当keyword过多时，hash table会占用大量内存，效率也会随之下降。

今天公司的架构师介绍了一个新的方法给我：Bloom Filter。它是一种基于随机数(或Hash)的数据结构，它支持对成员使用较少空间来存储，却能得到较高效率的查询。换句话说：在Bloom Filter 可以用于检索一个元素是否在一个集合中。其原理如下：

建立一个容量为500万的Bit Array结构（Bit Array的大小和keyword的数量决定了误判的几率），将集合中的每个keyword通过32个hash函数分别计算出32个数字，然后对这32个数字分别用500万取模，然后将Bit Array中对应的位置为1，我们将其称为特征值。简单的说就是将每个keyword对应到Bit Array中的32个位置上，见下图：



当需要快速查找某个keyword时，只要将其通过同样的32个hash函数运算，然后映射到Bit Array中的对应位，如果Bit Array中的对应位全部是1，那么说明该keyword匹配成功。
Bloom filter 是一个集合的有损编码，所以它不是一种“保险”的方案，存在一定的误判率。

另参考：http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx
========================================================================



1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物


问题是：谁养鱼？


提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、 挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居


以上是爱因斯坦在20世纪初出的这个谜语。他说世界上有98％的人答不出来。
你能做出来吗？