这段代码很简单, 就是遍历数组a, 与关键字相等即返回下标 i; 遍历结束没有遇到相等就返回 -1

到这里, 并不完美, 因为每次循环的时候都需要对 i是否越界 i<n 进行判断. 事实上有一个更好的办法, 可以设置一个 哨兵 就解决了每次不需要对 越界 的比较.

免去了查找过程中每一次比较后要判断查找位置是否越界的小技巧, 看似与原先差别不大, 但在总数据较多时, 效率提高很大. 当然哨兵也并不一定非要放在数组开头也可以在数组末端.

当查找任何一个位置的概率相同时, 如果 n 很大, 查找效率极为低下, 有点是算法简单, 对静态表的记录没有任何要求, 在一些小型数据查找是可以适用.
由于查找效率不同, 完全可以吧容易查找到的记录放在前面, 而不常用的记录放置在后面, 效率也可以提高.

O(logN) 的复杂度远好于顺序表查找的 O(N), 对于静态查找表, 一次排序后不再变化, 这样的算法已经比较好了. 但是对于需要频繁执行插入或删除操作的数据集来说, 维护有序的排序会带来不小的工作量, 建议不要使用.

从折半查照中可以看出，折半查找的查找效率还是不错的。可是为什么要折半呢？为什么不是四分之一、八分之一呢？打个比方，在牛津词典里要查找“apple”这个单词，会首先翻开字典的中间部分，然后继续折半吗？肯定不会，对于查找单词“apple”，我们肯定是下意识的往字典的最前部分翻去，而查找单词“zero”则相反，我们会下意识的往字典的最后部分翻去。所以在折半查找法的基础上进行改造就出现了插值查找法，也叫做按比例查找。所以插值查找与折半查找唯一不同的是在于mid的计算方式上

通过改 mid 值就得到了 差值查找, 其核心在于要查找的关键字 key 与查找表中最大记录和最小记录的关键字比较后的查找算法, 核心在于差值公式比例 (key-a[low])/(a[high]-a[low]). , 该算法的时间复杂度也是O(logN), 对于表长较大, 关键字分布比较均匀的查找表来说, 差值查找的平均性能会比折半查找要好得多. 如果分布类似于[0, 1, 2, , …, 99] 这样的极端不均匀的数据使用二分查找会更有效率

斐波那契查找利用列黄金分割的原理实现的.

斐波那契查找算法的核心在于:

斐波那契如果查找记录在右侧, 则左侧的数据都不用判断, 不断反复进行下去, 对处于当中的大部分数据, 其工作效率会高一点. 所以尽管斐波那契数列查找的复杂时间都是O(logN)但就平均性能来说, 斐波那契查找要优于折半查找. 缺点: 当 key=1, 那么始终都处于左侧长半区查找, 则查找效率要慢于折半查找

索引概念: 就是一个关键字于它对应的记录相关联的过程.
索引按照结构可以分为线性索引, 树形索引和多级索引. 这里参考的是《大话数据结构》中的内容, 因此就只介绍线性索引技术.线性索引: 就是将索引项集合组织为线性结构, 也称为索引表.

稠密索引: 在线性索引中, 将数据集中的每个记录对应一个索引项
稠密索引对应的数据可能是成千上万的是数据，因此对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列.

优点: 索引项有序也就意味着, 我们要查找关键字时, 可以用到折半, 插值, 斐波那契查找,等有序查找算法.
缺点: 如果数据非常大, 比如上亿, 也就意味着索引页的同样的数据长度规模, 对于内存有限的计算机来说, 可能就需要反复去访问磁盘, 查找性能反而大大下降.

回想一下图书馆是如何藏书的. 显然她它会是顺序摆放后, 给我们一个稠密索引表去查, 然后再找到书给你. 图书馆的图书分摆放是一门非常完整的科学体系, 而他是最重要的一个特点就是分块.
稠密索引因为索引项与数据集的记录个数相同, 所以空间代价很大. 为了减少索引个数, 我么们可以对数据集进行分块, 使其分块有序, 然后再对每一块建立一个索引项, 从而减少索引项的个数.
分块有序是把数据集的记录分成了若干块, 并且这些块需要满足两个条件

1. 块内无序, 即每一块内的记录不要求有序. 要求有序的话需要大量的时间和空间代价, 因此不要求块内有序
2. 块间有序, 列如要求第二块所有记录的关键字均要大于第一块中所有记录的关键字, 第三块所有记录的关键字均要大于第二块所有记录的关键字. 因为只有块间有序, 才有可能在查找时带来效率.

在分块索引表中查找, 分两步进行:

1. 分块索引表中查找关键所在的块. 由于块间有序所以可以使用有序表查找
2. 根据块首指针找到相应的块, 并在块间顺序查找关键码. 块间无序, 因此只能顺序查找

假设有 n 个记录的数据被平均分成 m 块, 每个块中有 t 条记录. 显然 n=m*t, 或者说 m=n/t. 再假设 L_b 为查找索引表的平均长度,

由此可见分块索引的效率比顺序查找的 O(N) 是高了不少, 不过显然它与折半查找的 O(logN) 相比还有不少的差距. 因此在确定所在块的过程中, 由于块间有序, 所以可以应用折半, 插值等查找方法来提高效率.
总的来说, 分块索引在兼顾了对细分块不需要有序的情况下, 大大增加了整体查找的速度, 所欲i普遍被用于数据库表查找等技术的应用当中.

在这里介绍最简单的，也算是最基础的搜索技术: 倒排索引。
我们来看样例，现在有两篇极短的英文“文章”一其实 只能算是句子，我们暂认为它是文章，编号分别是1和2。

有了这样一张单词表，我们要搜索文章，就非常方便了。如果你在搜索框中填写“book”关键字。系统就先在这张单词表中有序查找“book" ，找到后将它对应的文章编号1和2的文章地址(通常在搜索引擎中就是网页的标题和链接)返回，并告诉你，查找到两条记录，用时0.0001秒。由于单词表是有序的，查找效率很高，返回的又只是文章的编号，所以整体速度都非常快。

如果没有这张单词表，为了能证实所有的文章中有还是没有关键字“book”, 则需要对每一篇文章每一个单词顺序查找。在文章数是海量的情况下，这样的做法只存在理论.上可行性，现实中是没有人愿意使用的。
在这里这张单词表就是索引表，索引项的通用结构是:

1. 次关键码，例如上面的“英文单词”
2. 记录号表，例如上面的“文章编号”

其中记录号表存储具有相同次关键字的所有记录的记录号(可以是指向记录的指针或者是该记录的主关键字)。这样的索引方法就是倒排索引(inverted index) 。倒排索引源于实际应用中需要根据属性(或字段、次关键码)的值来查找记录。这种索引表中的每- -项都包括-一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。

优点: 倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，比如上例有7个单词的文章编号只有一个，而"book", “friend”, “good” 有两个文章编号
缺点: 若是对多篇文章所有单词建立倒排索引，那每个单词都将对应相当多的文章编号,维护比较困难，插入和删除操作都需要作相应的处理。

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

也就是说, 我们希望二叉排序树是比较平衡的, 即其深度与完全二叉树相同, 均为log₂ⁿ+1, 那么查找的时间复杂度也就为O(log_n), 近似于折半查找. 因此, 如果我们希望对一个集合按二叉排序树查找, 最好是把它构建成一颗平衡的二叉排序树.

之前所有的查找都是基于 “比较” 进行的, 能否直接通过关键字 key 得到要查找的记录内存存储位置呢?

一个公式: 存储位置=f(关键字)

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f (key)。 查找时，根据这个确定的对应关系找到给定值key 的映射f (key)，若查找集合中存在这个记录，则必定在f (key)的位置上。

这里我们把这种对应关系f称为散列函数，又称为哈希(Hash) 函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中, 这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。

1. 在存储时: 通过散列函数计算记录的散列地址，并按此散列地址存储该记录.
2. 当查找记录时，通过同样的散列函数计算记录的散列地址，按此散列地址访问该纪录

散列技术最适合的求解问题是查找与给定值相等的记录，但散列表不具备常规数据结构的能力

比如，同样的关键字能对应很多记录，却不适合用散列技术。一个班级几十个学生，他们的性别有男有女，用关键字“男”去查找就会对应很多的记录，这显然不合适。只有用班级学生的学号或者身份证号来散列存储，此时一个号码唯一对应一个学生才合适。

散列表不适合范围查找，比如查找一个班级18~22岁的学生，在散列表中无法进行。获取表中记录的排序也不可能，最值问题也无法从散列表中计算出来。

散列表设计要求： 简单，均匀，存储利用率高

另一个问题是冲突。在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key₁≠key₂,但是却有f (key₁) =f (key₂), 这种现象我们称为冲突(collision), 并把key₁ 和key₂称为这个散列函数的同义词(synonym)。 出现了冲突当然非常糟糕，那将造成数据查找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少，但是不能完全避免。

如果我们现在要对0~ 100岁的人口数字统计表，那么我们对
年龄这个关键字就可以直接用年龄的数字作为地址。此时f (key) =key。
如果我们现在要统计的是80后出生年份的人口数，如表8-10-2所示，那么我们
对出生年份这个关键字可以用年份减去1980来作为地址。此时f (key) =key-1980。
也就是说，我们可以取关键字的某个线性函数值为散列地址，即

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

如果我们的关键字是位数较多的数字，比如我们的11位手机号“130xxxx1234” ，其中前三位是接入号, 一般对应不同运营商公司的子品牌，如130是联通如意通、136 是移动神州行、153 是电信等;中间四位是HLR识别号,表示用户号的归属地;后四位才是真正的用户号，如表所示。
如果对员工进行登记，用手机号作为关键字那么极有可能前7位极有可能相等。算则后四位成为散列地址就是不错的选择。如果还是容易出现问题，我们可以对抽取出来的数字进行反转(1234改成4321)，右环位移，甚至前两位数与后两位数叠加(1234改成12+34=46)。总的目的就是提供一个散列函数，能够合理将关键字分分配到三列表的各个位置。

抽取：使用关键字的一部分来计算散列存储位置的方法，这再散列函数中是常用的方法

数字分析法通常是和处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布均匀，就可以考虑使用该方法

这个方法计算很简单，假设关键字是1234,那么它的平方就是1522756，再抽取中间的3位就是227, 用做散列地址。再比如关键字是4321,那么它的平方就是,抽取中间的3位就可以是671,也可以是710，用做散列地址。

平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。比如我们的关键字是, 散列表表长为三位，我们将它分为四组,987|654|321|0,然后将它们叠加求和987+654+321+0=1962,再求后3位得到散列地址为962。

有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如我们将987和321反转，再与654和0相加，变成789+654+123+0=1566,此时散列地址为566。

折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为:

mod是取模(求余数)的意思。事实上，这方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。

很显然，本方法的关键就在于选择合适的p, p如果选得不好，就可能会容易产生同义词。

例如我们对于有12个记录的关键字构造散列表时，就用了f (key)=key.mod 12的方法。比如29 mod12=5,所以它存储在下标为5的位置。
不过这也是存在冲突的可能的，因为12=2*6=3*4.如果关键字中有像18 (3*6)、30 (5*6)、42 (7*6)等数字，它们的余数都为6,这就和78所对应的下标位置冲突了。

甚至极端一些，对于表中的关键字，如果我们让p为12的话，就可能出现下面的情况，所有的关键字都得到了0这个地址数，这未免也太糟糕了点。
我们不选用p=12而是11来做除留余数法如图所示
此就只有12和144有冲突，相对来说，就要好很多。

因此根据前辈们的经验，若散列表表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。

根据关键字的随机函数值作为它的散列地址。也就是f(key)=random(key)。当关键字长度不等时，采用这个方法构造散列函数是比较合适的。

对于字符串而言，无论是英语字母还是中文字符也包括各种各样的符号，他们都可以转为某种数字来对待，比如ASCII或者Unicode等。

总之，现实中，应该视不同的情况采用不同的散列函数。给出一些考虑的因素来提供参考:

1. 计算散列地址所需的时间。

综合这些因素，才能决策选择哪种散列函数更合适。

就像误差无法避免只能减少一样，散列冲突也是无法避免只能减少的。

那么当我们在使用散列函数后发现两个关键字key₁≠key₂,但是却有f (key₁) =f(key₂)，即有冲突时，怎么办呢？有以下几种方案。

发生冲突的时候去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到到并将记录存入

当计算前5个数{12,67,56,16,25}时， 都是没有冲突的散列地址，直接存入，如图所示
计算key=37时，发现f (37) =1，此时就与25所在的位置冲突。于是我们应用上面的公式f (37) = (f (37) +1) mod 12=2。于是将37存入下标为2的位置。这其实就是寻找下一个空散列地址的做法
接下来22,29,15,47都没有冲突，正常的存入。
我们把这种解决冲突的方法称为线性探测法
在解决冲突的时候会碰到48和37这种key不同但f(key)相同的个情况，这种现象称为堆积。堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。

考虑深一步，如果最后一个 key=34，f(34)=10，与22所在的位置冲突，但22后面没有位置前面有一个空位，尽管可以不断求余后得到结果，但效率会很差。因此我们可以改进d_i=1², -1², 2², -2², … q², -q². 这样就可以双向寻找可能的位置。额外增加的平方运算，缪是为了不让关键字都聚集在某一块区域内。此方法为二次探测法

还有一种方法是在冲突时，对于位移量**d_i**采用随机函数计算得到，称为随机探测法

如果我们设置随机种子相同，则不断调用随机函数可以生成不会重复的数列，在查找时用同样的随机种子，每次得到的数列是相同的，相同荣的d_i 当然可以得到相同的个散列地址

总之，开放定址法只要在散列表未填满时，总是能找到不发生冲突的地址，是我们常用的解决冲突的办法。

对于我们的散列表来说，我们事先准备多个散列函数。

这里RH_i就是不同的散列函数，把前面说的什么除留余数、折叠、平方取中全部用上。每当发生散列地址冲突时，就换一个 散列函数计算，相信总会有一个可以把冲突解决掉。这种方法能够使得关键字不产生聚集，当然，相应地也增加了计算的时间。

对于关键字集{12,67,56,16,25,37,22,29,15,47,48,34},我们用前面同样的12为除数，进行除留余数法，可得到如图，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题。
链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链表的性能损耗。

这个方法其实就更加好理解，你不是冲突吗?好吧，凡是冲突的都跟我走，我给你们这些冲突找个地儿待着。这就如同孤儿院收留所有无家可归的孩子一样，我们为所有冲突的关键字建立了一个公共的溢出区来存放。就前面的例子而言，我们共有三个关键字{37,48,34}与之前的关键字位置有冲突，那么就将它们存储到溢出表中，如图所示。
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功;如果不相等，则到溢出表去进行顺序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

如果相对JDK8版本的HashMap深入了解，可以查看我之前的博客

最后，我们对散列表查找的性能作-一个简单分析。如果没有冲突，散列查找是我们本章介绍的所有查找中效率最高的，因为它的时间复杂度为0(1)。 没有冲突的散列只是理想，在实际的应用中，冲突是不可避免的。那么散列查找的平均查找长度取决于哪些因素呢?

1. 散列函数是否均匀
散列函数的好坏直接影响着出现冲突的频繁程度，不过，由于不同的散列函数对同一组随机的关键字,产生冲突的可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。

相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。

3. 散列表的装填因子
所谓的装填因子α=填入表中的记录个数 / 散列表长度。a标志着散列表的装满的程度。当填入表中的记录越多，a就越大，产生冲突的可能性就越大。比如前面的例子散列表长度是12，而填入表中的记录个数为11,那么此时的装填因子x=11/12=0.9167,再填入最后一个关键字产生冲突的可能性就非常之大。也就是说，散列表的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。

不管记录个数n有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是0(1)了。为了做到这一点，通常我们都是将散列表的空间设置得比查找集合大，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说，还是非常值得的。

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

1. 遍历: 时间复杂度O(N)
2. 位图解决: 整形数据是否存在给定的整形数据中，状态只能是在或不在。【那么就可以是用二进制比特位来代表是否存在。1:存在；0:不存在】

上图中就是一组数据的存储方案

1. 方案一用数组，消耗40字节
2. 方案二用位图，消耗3字节

发现位图1字节存储8个int；数组而言4字节存储1个int

猜想：如果把40亿个整数全放在位图中，需要多少内存？

∵ 由于我们设计的位图每 8 个整数消耗 1 字节 \because 由于我们设计的位图每8个整数消耗1字节 ∵由于我们设计的位图每8个整数消耗1字节

∴40亿个整数，位图0.43G就可以存储

数组形式常用数据存储量

看了位图的示意图之后，发现 num/8决定落在位图的哪个字节；num%8决定落在位图的哪个字节哪个位

2: 22 落在下标位2的字节段

6: 根据2字节段，22 落在其 6 下标 地址

1. 快速查找某个数据是否在一个集合中

   位图标识为1就代表存在；为0就代表不存在。利用此思想，可以进行海量数据的处理。

   100亿个整数中找到出现1次的数据，出现2次的数据和出现2次以上的数据

   • 文件地址=hash(num)%200，一样的数字肯定放在同一个文件中
   • HashMap遍历文件统计每个数字出现的次数

• ∵1Byte=8bit，字节数组中每个bit位代表一个整数

  ∴1Byte可以代表8个整数

• 位图不能用来存储重复的数据，通过从右到左【低字节位到高字节位输出标识位为1的数据】就可以输出从升序的数据列

数据值的计算方式：跨的字节数 * BIT + 位数

1. 有2个文件分别存储100亿个整数，如何快速找到他们的交集，并集和差集

   1. • 由于两个文件都是通过同一个哈希函数切割，所以对于相同文件地址进行 & 运算
   2. • 把第一个集合的数据放在位图中
      • 然后遍历第二个集合，看位图中是否存在便利读取的数据
   • 分别把两个集合的数据存放在两个位图中
   • 位图对应的标识位进行 & 运算，如果结果为1，就是交集
• 分别把两个集合的数据存放在两个位图中
• 位图对应的标识位进行 | 运算，如果结果为1，就是并集

• • 分别把两个集合的数据存放在两个位图中
  • 位图对应的标识位进行 ^ 运算，如果结果为1，就是差集

• 位图应用变形：1个文件有100个int，如何找出出现次数不超过2次的整数

• 找两个位图中标识不为 11 的数据就是出现次数不超过2次的整数

• 操作系统中磁盘块的标记

位图就是为了解决数据存储量大占用内存的问题，但也有一定的局限性

1. 存储的数据只能局限在整数，如果遇到字符串，小数就无能为力
2. 存储在位图中的数据不能重复，这也就导致在排序的时候就不会出现重复的数据

为了解决位图的痛点，人们又设计出一种新的数据数据结构——布隆过滤器

通常我们会有许多判断元素是否存在某个集合中的业务场景。我们经常使用的方法就是将集合中的元素全部保存起来，然后通过比较确定。常用的数据结构有链表 O ( N ) O(N) O(N)，树 O ( N ) O(N) O(N)。但是随着业务的增长，数据量也就开是线性增长，最终达到瓶颈。

散列表虽然是 O ( 1 ) O(1) O(1) ，但是由于负载因子的存在控制冲突概率，牺牲空间额外扩容的方式来解决哈希冲突，带来的数据效益是越来越小的，因此不推荐使用

布隆过滤器本质上是由哈希函数+位图结合而成的。

1. 布隆过滤器初始化状态为0

2. 当有k个元素加入集合的时候，会通过3个不同的hash函数分别映射到位图中，并置为1

3. 下次我们查询某个变量在不在集合的时候，通过哈希函数映射的的下标是否为1即可判断

   • 如果其中有一个为0，那么一定不存在
   • 如果哈希函数映射的位图都是1，则可能存在

   上图中的b和c都映射到了 字节数组0下标的3下标位 ，此时都是1，那么就无法判断一定存在了，仅仅是可能存在

1. 布隆过滤器在数据的插入和查询【时间和空间】上时间复杂度为 O ( 1 ) O(1) O(1) ，有着巨大的优势。哈希函数之间也没有关联关系

2. 由于没有存储数据本身，也不能像位图那样推到书原始数据，所以对于保密的数据来说，是安全的

3. 可以表示数据的全集，其它数据结构不能

4. 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容

5. 缓存宕机、缓存击穿场景：一般判断用户是否在缓存中，如果在则直接返回缓存结果；不在就会去数据库查询。如果一波冷数据，就会造成大量缓存访问，缓存击穿引发雪崩效应。这个时候使用布隆过滤器当缓存的索引，如果在布隆过滤器中才会访问缓存，缓存中没有用户数据，再访问数据库；如果布隆过滤器没有，则直接返回，不需要访问缓存

   冷数据：一般用不到的数据，集中处理存放在专门负责存储的机器上

   热数据：高频，经常使用到的数据，布置在高性能机器上【可以放到 LRUCache 中，先埋一个坑】

6. WEB拦截器：可以防止被同一个请求恶意多次攻击；也可以将用户第一次请求放入布隆过滤器中，下一次的先访问布隆过滤器在访决定是否访问缓存，请求提高缓存命中率

有一个100G的log文件，log中存储着IP地址，如何找到出现次数最多的IP地址？

上回是100亿个整数的文件，可以用位图解决；那么这次100G的IP地址日志文件就需要使用布隆过滤器。

通常不考虑大小，最常用的 K-V结构 即可解决；其次是 TopK 的思路解决。但问题是 100G 文件，数据量很大很大，即使用 TopK 也无法解决内存问题。

• 哈希切割文件：100G的文件切割为256MB，512MB。但是这样只能算出某个证文件中IP出现次数最多但并不代表整体文件中IP地址出现次数最多。

因此，我们不再按照文件来切割而是按照IP地址切割文件：将相同的IP地址切割到同一个文件中。然后 TopK使用大堆选择前三个最多出现次数的即可。

• IP本身就是一个字符串，通过哈希转换为数字
• 文件地址=hash(IP)%200，然后将从100G中读取的IP映射到对应的200份文件的地址中
• 统计每个文件中IP出现的次数【可以是用HashMap统计，因为是512MB，所以可以直接读取到内存中】。每一个文件最多的IP统计出来之后，整体文件的IP出现次数就得知了。无论是 TopK形式的前K个，还是最大的。都能快速找到

有2个文件，分别有100亿个query，但只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

这个query可能是SQL语句，也可能是HTTP请求，假设每个query是10字节。

1. • 哈希切割文件求交集，和位图的计算方式一样。这样是一种精确的算法【只不过这里需要按照query切割，我们可以通过哈希函数把query转为整数即可】
2. • 第1个文件中的query通过哈希函数映射到为途中
   • 遍历第2个文件，读取的每个query都去布隆过滤器中查找【会存在误判】
   • 因为误判，所以可能导致这个query没有，但是被判定为有

1. 误判率：随着插入元素越来越多，误判率也会越来越多。数据量太少，直接使用 HashMap 即可
2. 只能增加元素不能删除元素：因为删除元素依据的是标识为1，如果多个元素共同映射到一个标识位，那么删除这个标识位就会导致误判率的增加
3. 计数器溢出：通过计数器的方式来统计插入元素个数，多占用几倍的存储空间，并且也不一定100%正确

在了解一致性哈希算法和应用之前我们先了解一下经典的分布式缓存的应用场景。

大量的用户请求的query或者url会被经过哈希之后落在对应的服务器上。经过同一个哈希函数，对同一个url的运算结果应该是相同的，由于服务器数量为3，因此对3求余的结果就在 [ 0 , 1 , 2 ] [0, 1, 2] 区间内，如果计算结果为0，就使用0服务器；如果计算结果为1，就使用1服务器…当有300w个URL请求时，会通过这3个哈希函数将300w个请求均摊100w到每个服务器。

突然有一天，业务使用人数已经突破到了1亿访问量，每个服务器压力变为原来的了3.4倍，那么性能肯定会大打折扣的。如果突然增加了一个服务器，那么此时经过 hash(url)%4 的计算结果就落在了 [ 0 , 1 , 2 , 3 ] [0,1,2,3] 上，那么对应原来的业务出理的服务器肯定会打乱，服务器的均摊功能也会丧失，更有可能导致缓存雪崩，因此得不偿失。

什么是一致性哈希算法？之前的哈希算法是对服务器数量取模运算，但是一致性哈希使用 hashServer(Machine)%(2^32) 取模

1. 一致性哈希是将整个哈希值顺时针布置在一个虚拟的圆环，称为哈希环

2. 将服务器再哈希【可以用服务器的IP或者主机名作为关键子进行哈希】到哈希环上

3. 然后再使用使用特定的哈希函数 hashQuery(URL) 计算出哈希值，并确定在环上的位置，然后顺时针找到的第一个服务器就是其定位到的服务器

   假设 服务器2 出现了异常被移除之后，那么请求3就会顺时针找到遇到的第一个 服务器0 。而请求1，请求2依然交给 服务器1 处理；请求4交给 服务器0 处理，它们的请求处理服务器都没有改变；只有请求3 则转接给了 服务器0 处理。这就是一致性哈希的优点。

   传统的哈希分布式对服务器数量取模，当某一个服务器出现异常宕机或者新增服务器之后，就会出现缓存雪崩从而有可能导致系统的奔溃。而一致性哈希每次对于服务器数量的增删都只需要重定向一小部分数据即可，只有小部分缓存失效，不至于将大部分的缓存压力集中在某一台服务器上并且具有良好的容错性和可维护性。

   一致性哈希算法在服务器数量很少的情况下，会导致服务器节点分布不均匀导致的数据倾斜，也就是被缓存的对象大部分集中在一台服务器上，从而出现数据分布不均匀，也就是哈希环的倾斜现象。

   解决办法就是增加虚拟的服务器节点。hashServer(Matchine)%(2^32) 没计算一个物理地址就放置一个虚拟的地址称为 虚拟节点 。虚拟节点个数越多，数据/缓存/请求就会被分不的越均匀，哈希环倾斜的概率就越小。

   hashQuery(URL) 定位数据算法不变，但多了一步虚拟节点到物理节点的映射。

哈希和加密都能把一段文本信息转化为特定的字符串，很多人分不清楚。更详细的说哈希是把文本转换为相等长度，不可逆的字符串【也称为消息摘要】；而加密则是把文本转换为具有不同长度，可逆的密文

1. 转化后目标文本是否长度等长

   加密：不等长，随着加密文本的长度变化而变化

2. 转话后目标文本是否可逆

试想：如果哈希可逆，那么它将是世上最强悍的压缩方式。无论多长的文本，都被转换为定长文本固定大小。

穷举法模拟一次简单的哈希加密破解

这里学习了一下 MessageDigest 的用法，就换了另外一种方式来计算MD5和加盐的方式

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集 合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于哪个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(unionFindSet)

547. 省份数量，这个LeetCode利用到了并查集数据结构。

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

返回矩阵中 省份 的数量。

1. [0,0]=1: 城市0和自己本身就是相连的，所以为1

了解题目意思之后，最简单粗暴的方法就是暴力遍历，硬求出 i, j 不同时，数组中 1 的数量。我们可以是用并查集来解决此问题。我们先来学习如何构建并查集这样的数据结构

假设先构建 10 个具有亲戚关系的元素

这个时候对应城市的下标值【下标值直接替代父节点即可】再计算代表相连

假设我们要合并城市8和城市1

按照规定，那么 城市1 需要把 父节点 就是 城市8 的 父节点0【arr[1]=0】 ，城市0 需要把自己的下标更改为 7【arr[0]+=arr[1]】 才可以

底层数组 -1 填充：任何一个元素在最开始没有合并之前，自己本身就是一个父节点

借助上述并查集的实现代码，有两个OJ题目可以顺手解决

手写双向链表借助HashMap实现

通过继承的方式实现LRU缓存

本篇博客围绕着“搜索”的主题来讲。
首先我们要弄清楚查找表，记录，关键字，主关键字，静态查找表，动态查找表等这些概念。

尽管方法很土(简单)，但它却是后面很多查找的基础，注意设置“哨兵”的技巧，可以使得本已经很难提升的简单算法里还是提高了性能

折半查找性能上比原来的顺序表查找有了质的飞跃，由O(N)到O(log_N)。之后两种优秀的有序查找：插值查找和斐波那契数列查找，三者各有优缺点。

稠密索引，分块索引和倒排索引。索引技术被广泛用于文件检索，数据库和搜索引等技术领域。是进一步学习这些技术的基础。

动态查找最重要的数据结构，兼顾查找性能的基础上让插入和删除也变得效率高。不过为了达到最好的性能，最好构平衡的二叉树才最佳。因此这一块需要我们认真学习关于平衡二叉树(AVL树)，了解AVL树是如何处理平衡性的问题

B树这种数据结构是针对内存与外存之间的存取而专门设计的。由于内外存的查找性能更多取决于读取的次数，因此在设计中要考虑B树的平衡和层次。先通过最最简单的B树(2-3 树)来理解如何构建、插入、删除元素的操作，再通过2-3-4树的深化，最终来理解B树的原理。之后，我们还介绍了B+树的设计思想。

散列表是一种非常高效的查找数据结构，在原理上也与前面的查找不尽相同，它回避了关键字之间反复比较的烦琐，而是直接一步到位查找结果。当然，这也就带来了记录之间没有任何关联的弊端。应该说，散列表对于那种查找性能要求高，记录之间关系无要求的数据有非常好的适用性。在学习中要注意的是散列函数的选择和处理冲突的方法。

存储固定的整数类型数据，遇到小数，字符串就无法存储。再处理海量数据的时候具有很高的存储效率和查询效率

修补位图的不足，应用范围更加广泛和多样化

主要用来判断是否两者具有一定的关联关系【图数据结构中需要用到次数据结构判断是否有环】

最后最近访问的数据，经常把用到的数据放在前边。

如果你对体育频道有任何意见或建议，请到交流平台反馈。【】