第5章 第2节 哈希

推荐给朋友

● Hash表处理冲突的方法

参考回答:

开放定址法

为产生冲突的地址求得一个地址序列(),其中。其中m为表的长度,而增量有三种取值方法,线性探测再散列,平方探测再散列,随即探测再散列。

链地址法

将所有Hash地址相同的记录都链接在同一链表中

再Hash法

同时构造多个不同的Hash函数,当产生冲突时,计算另一个Hash函数地址直到不再发生冲突为止。

建立公共溢出区

将Hash表分为基本表和溢出表,若是与基本表发生冲突,都放入溢出表。

● 一致性哈希

参考回答:

一致性哈希算法在1997年由麻省理工学院提出,设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP(缓冲阵列路由协议,Cache Array Routing Protocol)十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT(Distributed Hash Table,分布式哈希)可以在P2P环境中真正得到应用。

标准:一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件:

1)、平衡性(Balance)

平衡性也就是说负载均衡,是指客户端hash后的请求应该能够分散到不同的服务器上去。一致性hash可以做到每个服务器都进行处理请求,但是不能保证每个服务器处理的请求的数量大致相同。

2)、单调性(Monotonicity)

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应该能够保证已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

3)、分散性(Spread)

分布式环境中,客户端请求时候可能不知道所有服务器的存在,可能只知道其中一部分服务器,在客户端看来他看到的部分服务器会形成一个完整的hash环。如果多个客户端都把部分服务器作为一个完整hash环,那么可能会导致,同一个用户的请求被路由到不同的服务器进行处理。这种情况显然是应该避免的,因为它不能保证同一个用户的请求落到同一个服务器。所谓分散性是指上述情况发生的严重程度。

4)、负载(Load)

负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

● Hash表处理冲突的方法

参考回答:

开放定址法

为产生冲突的地址求得一个地址序列(),其中。其中m为表的长度,而增量有三种取值方法,线性探测再散列,平方探测再散列,随即探测再散列。

链地址法

将所有Hash地址相同的记录都链接在同一链表中

再Hash法

同时构造多个不同的Hash函数,当产生冲突时,计算另一个Hash函数地址直到不再发生冲突为止。

建立公共溢出区

将Hash表分为基本表和溢出表,若是与基本表发生冲突,都放入溢出表。

● apriori

参考回答:

1)Apriori原理

如果一个项集是频繁的,则它的所有子集一定也是频繁的;相反,如果项集是非频繁的,则它的所有超集也一定是非频繁的。

2)发现频繁项集

假定事务总数为N,支持度阈值是minsup,发现频繁项集的过程如下(理论上,存在许多产生候选项集的方法,本例使用支持度阈值来产生):

①初始时每个项都被看作候选1-项集。计数对它们的支持度之后,将支持度少于阈值的候选项集丢弃,生成频繁1-项集。

②在第二次迭代,依据Apriori原理(即所有非频繁的1-项集的超集都是非频繁的),仅使用频繁1-项集来产生候选2-项集。此时生成的候选2-项集有多个,将支持度少于阈值的候选项集丢弃,生成频繁2-项集。

③经过多次迭代,每次用上一次生成的频繁n-项集产生新的候选(n+1)-项集,直至没有发现频繁(n+1)-项集,则得到的频繁n-项集就是最终结果。

3)发现关联规则

发现关联规则是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则,其中minsup和minconf是对应的支持度阈值和置信度阈值。

● KM算法

参考回答:

匈牙利算法:求最大匹配,那么我们希望每一个在左边的点都尽量找到右边的一个点和它匹配。我们依次枚举左边的点x的所有出边指向的点y,若y之前没有被匹配,那么(x,y)就是一对合法的匹配,我们将匹配数加一,否则我们试图给原来匹配y的x’重新找一个匹配,如果x’匹配成功,那么(x,y)就可以新增为一对合法的匹配。给x’寻找匹配的过程可以递归解决.

从一边的未饱和点出发,寻找增广路。复杂度:O(VE)

KM算法:给定一个带权的二分图,求权值最大的完备匹配

相等子图的完备匹配=原图的最大权匹配

1)初始化可行性顶标

2)对n个点在相等子图中寻找增广路

(1)初始化访问标记

(2)寻找增广路

(3)若增广路不存在,则修改交错路中的顶标,直到对某个点而言找到一条增广路为止

3)求得最大权

算法时间复杂度O(n3)O(n3)