巴尔加瓦算法图解【完结】：算法运用（下）

布隆过滤器

在元素很多的情况下，判断一个元素是否在集合中可以使用布隆过滤器。布隆过滤器（Bloom Filter）是 1970 年由布隆提出的，是一种非常节省空间的概率数据结构，运行速度快，占用内存小，但是有一定的误判率且无法删除元素。它实际上是一个很长的二进制向量和一系列随机映射函数组成，主要用于判断一个元素是否在一个集合中。
布隆过滤器(Bloom Filter)详解

HyperLogLog

Redis 在 2.8.9 版本添加了 HyperLogLog 结构（简介HLL），在数量级特别大的情况下占用空间很小。如果使用我们平常的数据结构比如set,HashMap,等，虽然也可以实现去重统计的工作，但是当数据量上升到一定级别之后，其占用的空间也是非常的大。需要注意的是HyperLogLog算法的去重计数方案并不精确，当然不是特别不精确，标准误差只有0.81%

当然HyperLogLog虽说占据空间小，但也不是不占空间，它需要占据一定12k存储空间，所以如果我们的统计量可能比较小，使用HyperLogLog可能就是大材小用了，但是如果百万级、千万级，那节省的空间就大的大了去了。

SHA算法

散列算法：有一键，将相关的值放入数组中。
使用散列函数来确定应将这个值放在数组的什么地方。这样查找时间是固定的。当你想要知道指定键对应的值时，可再次执行散列函数，它将告诉你这个值存储在什么地方，需要的时间为O(1)。在这个示例中，你希望散列函数的结果是均匀分布的。散列函数接受一个字符串，并返回一个索引号。

比较文件

另一种散列函数是==安全散列算法(secure hash algorithm,SHA)==函数。给定一个字符串，SHA返回其散列值。
这里的术语有点令人迷惑。SHA是一个散列函数，它生成一个散列值——一个较短的字符串。用于创建散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另一个字符串。

‘Hello’: 24cf24db

对于每个不同的字符串，SHA生成的散列值都不同。SHA生成的散列值很长，这里截短了。如果散列值相同，说明是同一个文件。

检查密码

当你在注册或者更改密码时，Google并不直接将你的密码存储在数据库中，而是将密码通过一个特定的哈希函数进行转换，生成一个固定长度的哈希值。哈希函数是一种将任意长度的输入数据转换为固定长度输出的算法，其特点是单向的，即无法从哈希值反推出原始输入数据。

SHA被广泛用于计算密码的散列值。这种散列算法是单向的。你可根据字符串计算出散列值。但你无法根据散列值推断出原始字符串。这意味着计算攻击者窃取了Gmail的SHA散列值，也无法据此推断出原始密码！你可将密码转换为散列值，但反过来不行。这意味着计算攻击者窃取了Gmail的SHA散列值，也无法据此推断出原始密码！你可将密码转换为散列值，但反过来不行

Diffie-Hellman密钥交换

Diffie-Hellman使用两个密钥：公钥和私钥。顾名思义，公钥就是公开的，可将其发布到网站上，通过电子邮件发送给朋友，或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥，就只有你才能解密消息！

线性规划

例如，假设你所在的公司生产两种产品：衬衫和手提袋。衬衫每件利润2美元，需要消耗1米布料和5粒扣子；手提袋每个利润3美元，需要消耗2米布料和2粒扣子。你有11米布料和20粒扣子，为最大限度地提高利润，该生产多少件衬衫、多少个手提袋呢？

from scipy.optimize import linprog# 定义目标函数的系数
c = [-2, -3]  # -2x-3y求最小值# 定义约束条件的系数
A = [[1, 2], [5, 2]]  # 第一个约束条件表示布料消耗，第二个表示扣子消耗。
b = [11, 20]  # 右侧向量(限制）# 定义变量的取值范围
x0_bounds = (0, None)  # x的取值范围为非负数
x1_bounds = (0, None)  # y的取值范围为非负数# 求解线性规划问题
res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='highs')#ub=upper bound# 输出结果
print("最大利润：", -res.fun)
print("生产衬衫数量：", round(res.x[0]))
print("生产手提袋数量：", round(res.x[1]))

最大利润： 17.625
生产衬衫数量： 2
生产手提袋数量： 4

结语（完结）

本章简要地介绍了10个算法，唯愿这让你知道还有很多地方等待你去探索。在我看来，最佳的学习方式是找到感兴趣的主题，然后一头扎进去，而本书便为你这样做打下了坚实的基础。