面试题目

1.如何交换两个变量的值？

方法1：我们平时都用的，整个中间变量：

		let mid 

		mid = x 

		x = y 

		y = mid

复制代码

方法2：借助位运算，不需要任何辅助空间

但是这个有缺陷！！只能转换Number类型哦

方法3：不需要任何辅助空间强烈推荐！！！

这个方法可以转换任何类型

x = [y,y=x][0]

复制代码

比较大小

其他

JavaScrip 判断数组元素 | 位运算 经典面试算法

布隆过滤器

介绍哈希函数

哈希函数又叫散列函数,哈希函数的输入域可以是非常大的范围,但是输出域是固定范围。

哈希函数的性质：

1、典型的哈希函数都拥有无限的输入值域

2、输入值相同时,返回值一样。

3、输入值不同时,返回值可能一样,也可能不一样。

算一下哈，如果把所有的黑名单都存到数据库中，

我算了一下也就是需要5.8T的空间来存嘛。

但是！！！题目中说给你的空间不超过30G！！！所以你就不能直接存数据库里了，你就得用到布隆过滤器的知识了。

我只会系统的讲一下什么是布隆过滤器，想深入了解的自己去查

布隆过滤器可精确的代表一个集合，可精确判断某一元素是否在此集合中，精确程度由用户的具体设计决定，做到100%的精确即正确是不可能的。布隆过滤器的优势在于,利用很少的空间，可以做到精确率较高。

原理

• 当你的url加入之后，bitarray就相当于一个包含了所有的url的集合。

  • 设立一个bitarray的二进制数组，数组一项大小为1比特，初始时候全都为0

  • 一个URL，我们通过k个哈希函数将其计算。得出k个结果。将计算结果放入哈希表bitarray之中，如果结果在哈希表中为0，我们哈希表该位置设为1

• 当你要查找某个url是否在其中，你只需要将这个url经过你所设定的k个哈希函数的计算，

看看结果所对应的哈希表上的位置，如果k个位置均为1，则证明你要检测的这个url在bitarray；反正有一个位置为0，就证明这个网页不在bitarray中。

这样我们就能感觉到缺陷了，因为会产生误判，就是可能这个网页它没在黑名单里，但是经过k个哈希函数计算之后所在的k个位置却都是1，被认为是在黑名单中。


布隆过滤器如何设置？

说了布隆过滤器会产生误判，那怎么知道误判的概率呢。回到这个题：

先看这个题目中的数据：

黑名单url个数：100亿

url大小：64B

允许失误率：0.01%

空间限制：30G

• bitarray：受黑名单url个数和允许失误率的影响。

  • 公式：

	- m：bitarray大小（bitarray一项的大小为1比特）

	- n：样本数量

	- p：允许失误率



- 在这个题里边n = 100 亿，p=0.01%，求出 m = 19.19n，向上取整20n，20n比特也就是![在这里插入图片描述](https://img-blog.csdnimg.cn/20200404152319845.png =200x)

- <font color=sienna>23G比要求的30G少哦。比起存在数据库里需要6000G，少很多了哦。</font>
复制代码

• 散列函数：数量受bitarray大小和样本数量的影响；函数设计受url大小影响

  • 数量公式：

  

    - k：散列函数的个数
  
    - m：bitarray大小（bitarray一项的大小为1比特）
  
    - n：样本数量
  复制代码

  • 本题中m = 20n，求得k为14，也就是你最少需要设立14个散列函数

• 精确程度

  • 公式：

  

    -  本题中n = 100亿，m = 20n ， k =14 ，计算之后 实际的失误率为0.006%
  
    - <font color=sienna>比题目要求的0.01%还低哦。</font>
  复制代码

适用情况

容忍一定程度的失误率，对空间要求较严格

• 网页黑名单系统

• 垃圾邮件过滤系统

• 爬虫的网址判断重复系统