待完成的任务
了解: 1、Arrays.mergeSort排序算法 2、BigInteger的实现原理 3、红黑树的添加和删除操作实现 4、Collections各方法的相关实现 5、ORACLE怎么查找db_cache pool中的block,比如全表扫描怎么查找到所有的block。 6、学习apache,memcached、webservice、MYSQL
大数据量处理算法:
- Bloom Filter
- Hash
- Bit-Map
- 堆
- 双层桶划分
- 数据库索引
- 倒排索引(Inverted Index)
- 外排序
- Trie树
- 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%的人答不出来。 你能做出来吗?