引言
- 哈希表:
本质是通过随机化，把一个比较大的、稀疏的空间，映射到一个比较小的、紧密的空间中。在计算机中，它通常是通过数组实现的。 - 对索引进行查询的演变：
将关键词变成一个编号，通过数学变换，把每一个中国人的名字都可以对应一个数字。将来查找时，只要用公式做一次计算，就能直接找到名字在索引中的位置。- 将关键词变成一个编号，然后再取尾数（火车安排座位，座位号重合的，就近坐下）
在尾号出现相同情况时，想办法找一个没有名字对应的尾号，作为备选方案。
- 伪随机数（
随机指定一个名字的编号）
计算机科学家们发现，如果随机地给每个名字进行编号，重复的可能性最小。于是，计算机科学又有了一个小分支，
如何产生伪随机数。
- 信息加密的应用：产生一个对应的随机数，也被称为私钥（不公开的）；而公开密钥，则相当于验钞机，验证真伪。
搜索需要用到随机化这种方法，每个人都不知不觉地使用的信息加密，也离不开随机化。从信息查找到信息加密，背后的道理是相通的。【将关键词变成一个编号，然后再取尾数（火车安排座位，座位号重合的，就近坐下）-＞ 伪随机数 -＞ 数据加密-＞公开密钥】
数据加密：数学家和计算机科学家发现，如果一个信息（比如名字），对应的伪随机数足够长，别人是无法通过这个数字还原出原来的信息的，但是产生这个伪随机数的人却可以。 公开密钥：数学家们想出了一个`不让对方知道自己怎么加密，却能够对某个信息解密的方法。
I 哈希表
1.1 哈希表的本质
哈希表本质是通过随机化，把一个比较大的、稀疏的空间，映射到一个比较小的、紧密的空间中。
在计算机中，它通常是通过数组实现的。
1.2 哈希表在一定程度上是否兼有数组和链表的优点？
数组、链表和哈希表是三个不同的东西，它们有一些相关性，但是使用的目的有区别。
数组
是为了便于直接查找访问，它要求数据项基本上是整齐的.
链表
强调的是前后的依赖关系，一个连着一个，比如某个学位选课的次序，一门课和它的先修课就是这种链接关系。
哈希表: 本质是通过随机化，把一个比较大的、稀疏的空间，映射到一个比较小的、紧密的空间中。在计算机中，它通常是通过数组实现的。
相比一般的数组，它有三个优点：
- 动态增加或者删除一个数据项比较快。
- 数组只能根据下标直接查找，下标和数据内容无关，如果要根据内容查找，效率就比较低，哈希表的下标是根据数据内容计算出来的，因此根据内容查找比较快。
- 数组在处理多个维度时变得很复杂，哈希表可以将多个维度的数据映射到一个维度。但是，哈希表是需要额外成本的，它其实是以空间换时间。其次，数组可以一次顺序存取很多项数据，而哈希表存取数据只能一个个进行。
II 对索引进行查询
对索引进行查询的公式：将关键词变成一个编号，然后再取尾数（火车安排座位，座位号重合的，就近坐下）-> 伪随机数 -> 数据加密->公开密钥
2.1 借助索引这个工具进行有效地查找信息
和图书的关键词索引类似，都保存着所要找的信息的位置。如果所要找的信息不止一条，它会保留所有的位置。
和图书关键词索引不同的是，书后面关键词的索引只有一种，而计算机里的索引常常需要根据应用场景建立很多种，以便按照不同门类的信息进行查找。
案例：户籍数据库对每一个人的记录编好号，相当于书的页码。人名索引的每一行存储的是名字和这个名字的所有人的信息记录编号。例如，张楠是数据库中编号20230210到第20260902的人。
———————————————— 版权声明：本文为CSDN博主「iOS逆向」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/z929118967/article/details/131848741
2.2 把索引排个序，用二分查找
对于规模不大的数据库，索引也是这么建立的。
这种方法最大的好处是不会浪费任何空间，存储的效率比较高。
2.3 利用随机化对索引进行查询
对索引进行查询的公式：将关键词变成一个编号，然后再取尾数（火车安排座位，座位号重合的，就近坐下）-> 伪随机数 -> 数据加密->公开密钥
方法一:将关键词变成一个编号，通过数学变换，把每一个中国人的名字都可以对应一个数字。将来查找时，只要用公式做一次计算，就能直接找到名字在索引中的位置。
假如汉字有3万个，每个汉字就对应了一个从0~29999的数字。 “张”这个字对应3500，“楠”这个字对应4003，那么“张楠”就对应一个数字组3500和4003。做一个简单的数学变换，把上面两个数字变成一个，方法是：30000*3500 4003＝105,004,003，也就是说拿105,004,003这个数字作为“张楠”这个名字的编号。类似地，每一个中国人的名字都可以对应一个数字。
建立索引时，直接把“张楠”存放到第105,004,003个存储单元，将来查找时，只要用上面的公式做一次计算，就能直接找到“张楠”在索引中的位置。
这个方法有两个大问题。
- 非常浪费。汉字组合不会都用来取名字，于是对应数字所占据的单元就被浪费掉了。
- 当大家起了三字名，甚至四字名后，名字对应的编号就可能非常大，超出计算机的存储范围。
方法二：只保留编号的尾数，不管编号有多少位，只保留最后的7位数字。
解决问题：两个不同的人名计算出的编号，尾数恰巧重复。
思路：在尾号出现相同情况时，想办法找一个没有名字对应的尾号，作为备选方案。
假如火车站是随机安排座位的，一定有一些人拿到相同的座号。如果火车能载1000人，只卖了800张票，一定有办法安排每一个人就座的。 具体的做法是，先来的先坐下，如果后来的发现自己票上的座位已经被占据了，那么没关系，找最近的坐下即可。如果火车上真有20%的空座位，大家其实都能在附近找到一个空座。在计算机中，安排这种相同尾数的编号的方法和火车上安排座位的原理是一样的。
方法三：伪随机数（ 随机指定一个名字的编号）
计算机科学家们发现，如果随机地给每个名字进行编号，重复的可能性最小。于是，计算机科学又有了一个小分支，
如何产生伪随机数。
III 信息加密
数据加密：数学家和计算机科学家发现，如果一个信息（比如名字），对应的伪随机数足够长，别人是无法通过这个数字还原出原来的信息的，但是产生这个伪随机数的人却可以。
公开密钥：数学家们想出了一个`不让对方知道自己怎么加密，却能够对某个信息解密的方法。
- 产生一个对应的随机数，也被称为私钥（不公开的）。
- 加密协议还会产生一个公开的密钥，它可以用来验证真假。
产生的协议可以看成是印钞机，它怎么印钞，不能让你知道。 公开密钥，则相当于验钞机，你可以拿它验证真伪。
IV 采用随机化的原理进行网络爬虫服务器管理
一个商业的网络爬虫需要有成千上万个服务器，并且通过高速网络连接起来。网络爬虫为了保障这1000台服务器不会把某个网页访问好几次，而把另外一些网页漏掉，需要有一个小本本，记录已经下载过的网页。
记录已经下载过的网页的小本本采用随机化的原理进行管理:随机化之后看上去无序，其实反而变得有规律可循，于是每个服务器看到一个网页，都知道这个网页是否属于自己的工作范围，如果不属于，则通知相应的服务器去处理，而不需要到处广播
