布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法

引言

在介绍布隆过滤器之前我们首先引入几个场景。

场景一

在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿?

有人说, 将这个key的值置为0存入缓存不就行了吗?确实,这是一个好的方案。大部分情况我们都是这样做的,当访问一个不存在的key的时候,设置一个带有过期时间的标志,然后放入缓存。不过这样做的缺点也很明显,浪费内存和无法抵御随机key攻击。

场景二

在一个黑名单系统中,我们需要设置很多黑名单内容。比如一个邮件系统,我们需要设置黑名单用户,当判断垃圾邮件的时候,要怎么去做。比如爬虫系统,我们要记录下来已经访问过的链接避免下次访问重复的链接。

在邮件很少或者用户很少的情况下,我们用普通数据库自带的查询就能完成。在数据量太多的时候,为了保证速度,通常情况下我们会将结果缓存到内存中,数据结构用hash表。这种查找的速度是O(1),但是内存消耗也是惊人的。打个比方,假如我们要存10亿条数据,每条数据平均占据32个字节,那么需要的内存是64G,这已经是一个惊人的大小了。

一种解决思路

能不能有一种思路,查询的速度是O(1),消耗内存特别小呢?前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态(是或者不是,存在或者不存在),那么对于所存的数据完全可以用位来表示!数据本身则可以通过一个hash函数计算出一个key,这个key是一个位置,而这个key所对的值就是0或者1(因为只有两种状态),如下图:

(更多…)

数据结构学习笔记:树

树是一种层次关系,在日常生活非常常见,比如社会关系,亲缘关系,文件管理。

一棵树是一些节点的集合,这个集合可以是空集,若非空,则一棵树由称作为根的节点r以及0个或者多个非空的(子)树组成,这些子树中的每一棵都是被来自根r的一条有向的边所连接。

一种数据结构需要包含一些操作,树这种数据结构有增加,删除,查找,修改。

节点

节点的度:节点子树的个数。

叶子节点:没有儿子的节点,也就是度为0的节点。

节点的层次:规定跟节点在1层,其他节点的层次为父节点的层次加1。

节点的高:节点的高为从这个节点到叶子的最长路径,所有树叶的高都是0。

节点的深度:从跟节点到该节点的唯一路径长,根的深度为0。

节点定义

typedef struct TreeNode *PtrToNode;

struct TreeNode
{
    ElementType Element;
    PtrToNode FitstChild;
    PtrNode NextSibling;
}

(更多…)