QQ空间
起因
现在21世纪，有人称之为大数据时代，谁有数据量大的数据，谁能够从海量数据中提取到有用信息，并能够将其转换为资本，谁就取得了互联网的地位。
互联网数据是由生活在网络上的每一个用户所产生的，用户在互联网上的活动会被记录下来，这就是数据，海量用户，有着海量数据。这些数据被利用，分析，与各种各样的广告联系在一起，进而把这些广告推送给用户，这些推送的广告都是用户的网络行为分析出的结果。
QQ上活跃这大量的用户，QQ空间里面记录了许多人的日常，这些就是数据。在日常使用QQ空间的时候，会偶尔点击给我们好友点赞的朋友，之后我们就能看到我们好友的好友的空间，依次类推，我们可以看到海量信息。
过程中用到的算法
布隆过滤器
一、 前言
布隆过滤器 (Bloom Filter)是由Burton Howard Bloom于1970年提出，用于判断一个元素是否在集合中。与课本上学的数据结构不同，它是一种概率型数据结构，所谓概率型，就是指在判重的时候，并不是完全一定确保某个数据在集合中，课本上的二分查找，哈希，都可以一定确定某个元素是否在集合中。
在爬虫的时候，数据发生重复，需要判重，判断该条数据是否加入到队列中。传统哈希表可用于判断元素是否在集合中，时间复杂度O(1),空间复杂度o(n)，布隆过滤器牺牲了一点时间，空间复杂度大约是哈希表的\frac{1}{4}。
布隆过滤器也支持数据的插入。
二、算法过程
一个布隆过滤器是一个有m个bit位的数组，每一个bit位都初始化为0。并且定义有k个不同的hash 函数，每个都以随机的将元素均匀hash到m个不同位置中的一个。
在下面的介绍中n为元素数，m为布隆过滤器或哈希表的槽数，k为布隆过滤器hash 函数个数。
- 往布隆过滤器增加一个元素：首先用k个hash 函数分别将该元素hash，得到k个数值，于布隆过滤器中将这k个数值对应的bit位置1。 举例：现在有3个哈希函数，f1,f2,f3，有一个8位qq号，布隆过滤器数组长度m为10。qq号先经过三个hash函数处理，假设分别得到1，3，7，然后就将布隆数组1，3，7位置1。
- 判断布隆过滤器中是否含有某个元素：首先用k个hash函数分别将该元素hash得到k个数值。再判断这k个数值在布隆数组中的位置是否全1，若全位1则此元素在集合中，若其中任一位不为1，则此元素比不在集合中。 举例：现在有3个哈希函数，f1,f2,f3，有一个8位qq号，布隆过滤器数组长度m为10。需要查找是否含有这个qq号。该qq号先经过三个hash函数处理，假设分别得到1，3，7，然后查看布隆数组1，3，7位置是否全为1。
- 概率型数组结构的解释： 举例：现在有3个哈希函数，f1,f2,f3，有3个8位qq号，假设分别为q1,q2,q3，布隆过滤器数组长度m为10。三个qq号分别经过三个hash函数处理，假设依次得到的结果为 q1:1，3，7， q2:2，5，8， q3:2，3，7， 在将q1,q2 依次插入到布隆数组中后，查询q3，发现其三个位置均为1，于是得到了q3在布隆过滤器的错误。这就是概率型的解释。
- 避免上述错误： 增加hash函数个数k，增加hash范围m。当hash结果范围很大大，且hash结果独立，直接上感觉不太可能发生碰撞。有没有一种hash函数的感觉?。
- 使用场景： 总结：数据量大，很大，在使用查询可以接受一定的查询错误，使用布隆过滤器 当数据量大小自己能够接受，且不接受误判，使用传统set，哈希表。
三、举例说明
以垃圾邮件过滤中黑白名单为例：假设现有1亿个email的黑名单，每个都拥有8 bytes的指纹信息，则能的数据量大小为
需要的位数组大小为
这个数据量对于位数组来说是太大了，且在邮箱里，邮箱数量相比较邮箱范围过于稀疏，而且还没有考虑到哈希表中的碰撞问题。
若采用哈希表，由于大多数采用开放地址法来解决碰撞，而此时的查找时间复杂度为 ：O(\frac{1}{1-\frac{n}{m}})，当哈希表半满(\frac{n}{m}=\frac{1}{2})，则每次search需要探测2次，因此在保证效率的情况下哈希表的存储效率最好不超过50%。此时每个元素占8 bytes，总空间为：\frac{10^8×8Byte}{1-0.5}=1.6GB
若采用布隆过滤器，取k=8。因为n为1亿，所以总共需要8 × 10^8被置位为1，在保证误判率低，选取合适的k，m，让空间利用率为50%，所以总空间为：\frac{8×10^8bis}{50%}\approx200MB，所需空间比上述哈希结构小得多，并且误判率在万分之一以下。
四、误判概率的证明和计算
假设布隆过滤器中的hash函数满足简单均匀哈希假设：每个元素都等概率地hash到m个槽中的任何一个，与其它元素被hash到哪个slot无关。
若m为bit数，则对某一特定bit位在一个元素由某特定hash函数插入时没有被置位为1的概率为：1-\frac{1}{m}，该结论算法导论有详细证明。
那么k个hash 函数中没有一个对其置位的概率为：(1-\frac{1}{m})^k。
如果插入了n个元素，但都未将其置位的概率为：(1-\frac{1}{m})^{kn}。
则此位被置位的概率为：1-(1-\frac{1}{m})^{kn}。
现在考虑查找阶段，若对应某个待查找元素的k bits全部置位为1，则可判定其在集合中。因此将某元素误判的概率为：(1-(1-\frac{1}{m})^{kn})^k。
从上式中可以看出，当m增大或n减小时，都会使得误判率减小，这也符合直觉。
根据小学二年级学过的极限公式:\lim\limits_{x\to0} (1+x)^{\frac{1}{x}}=e
(1-(1-\frac{1}{m})^{kn})^k=(1-(1-\frac{1}{m})^{m×\frac{kn}{-m}})^k~(1-e^{-\frac{nk}{m}})^k。
现在可以假设当给定m，和n的当k取何值时，可以将误判率降至最低。
假设f(k)=(1-e^{-\frac{nk}{m}})^k，设b = e^{\frac{n}{m}},此时，f(k)=(1-b^{-k})^k，接下来求f(k)的最值：
f(k)=(1-b^{-k})^k，两边同时取对数lnf(k)=kln(1-b^{-k})
两边同时对k求导 \frac{1}{f(k)}f’(k)=ln(1-b^{-k})+k\frac{b^{-k}lnb}{1-b^{-k}}=0
解上述方程：☞(1-b^{-k})ln(1-b^{-k})=-kb^{-k}lnb
☞(1-b^{-k})ln(1-b^{-k})=b^{-k}lnb^{-k}
☞(1-b^{-k})=b^{-k}
☞b^{-k}=\frac{1}{2}
☞e^{-\frac{kn}{m}}=\frac{1}{2}
☞k = ln2\frac{m}{n}
此时误判率f(k)=(1-b^{-k})^k=(1-\frac{1}{2})^{k}=2^{-ln2\frac{m}{n}}\approx0.6185^{\frac{m}{n}}
调节\frac{m}{n}的大小，即可降低误判率f(k)。
五、设计和应用布隆过滤器的方法
首先要先由用户决定要add的元素数n，希望的误差率P。其他参数需要计算。
首先要计算需要的内存大小m bits：p = 2^{-ln2\frac{m}{n}}⇨m=-\frac{nlnp}{(ln2)^2}
再由m，n得到hash函数的个数：k = ln2\frac{m}{n}
至此结束。
框架算法：BFS广度优先搜索
一、前言
人的社交可以抽象定义成一个网络图。
以每一个个人为中心，向外扩充一圈即时自己的好友圈。好友圈会有交叠。
不断的以每个人为中心，向外扩充，就是整个网络图(社交遍历)。
个人总结
每个人的好友圈是不同的，你的好友情况在别人那里情况可能是不一样的。
个人只能看到自己的朋友圈，去看看别人的朋友圈，了解一下其他圈子动态，也是一件相当有趣的事。
经过一圈圈的扩充遍历，好友的动态内容逐渐不同。我一开始能够访问到的内容是像自己一样普通大学生的动态，日常，到中间是那些转发，非原创动态，到最后，就逐渐变成卖衣服，卖手机的。
个人解释：qq空间其实是可以限制访问的，那些开放qq空间的人，会有哪些人？一，不在意别人访问的，二,需要别人浏览，阅读，转发。三，为了利益。
这些数据都有些什么用呢？有这些人的qq号，qq号主发的动态，号主的资料卡信息，其实这里最真实的只有qq号，然后是动态，分析假的资料信息并没有什么意义。qq号没得分析，动态分析，只得大致去浏览了。告一段落吧。
qq空间里人间百态。那个80-90-00的人间百态。