这章开始算法基础提升的内容，包括了哈希表的原理和并查集以及KMP算法的内容。其中哈希表的原理和KMP算法的细节是比较难懂的点。最后继续欢迎大佬指点！！

'''
# #哈希表
# 
# 
# # #认识哈希函数和哈希表
# #输入的值是无限制的，但是输出的值是有限制的
# #每一个输入的值都有一个固定的输出值
# #两个不同的输入值输出值有可能会一样(哈希冲撞)
# #输出值有均匀性、离散性
# 
# 
# #把n个输入值，计算出哈希值后模上一个m，所得到的值在0~m-1上也是均匀分布
# # #返回40亿个整数输入中出现最多的，但是只有1G内存，怎么做？
# #第一种方法:直接使用哈希表，输入值作为key，出现的次数为value。这样肯定可以得到答案。
# #         但是问题是一条哈希表至少需要key(4bit)+value(4bit)=8bit。最差情况是40亿*8bit=32G
# #第二种方法:把每一个数据经过哈希函数处理得到40亿个哈希数，把哈希数模上100，得到值是0~99
# #         按照模得到的数的不同把数据放到不同的文件上，每个文件可以得到一个出现最多的数，再在100个中得到出现最多的数，所以只需要32G/100=0.32G的内存
# 
# 
# # #利用哈希表设计一个结构，在该结构有如下三个功能:
# # #inset(key):将某个key加入到该结构，做到不重复
# # #delete(key):将原来在结构中的某个key移除
# # #gerandom():等概率随机返回结构中的任何一个key
# # import random
# # class pool(object):
# #     def __init__(self):
# #         self.keyindexmap={}
# #         self.indexkeymap={}
# #         self.size=0
# #     def insert(self,key):
# #         if key not in self.keyindexmap:
# #             self.keyindexmap[key]=self.size
# #             self.indexkeymap[self.size]=key
# #             self.size+=1
# #     def delete(self,key):
# #         if key in self.keyindexmap:
# #             deleteindex=self.keyindexmap[key]
# #             lastindex=self.size-1
# #             lastkey=self.indexkeymap[lastindex]
# #             self.keyindexmap[lastkey]=deleteindex
# #             self.indexkeymap[deleteindex]=lastkey
# #             del self.keyindexmap[key]
# #             del self.indexkeymap[lastindex]
# #     def getrandom(self):
# #         if self.size==0:
# #             return None
# #         randomindex=random.randint(0,self.size-1)
# #         return self.indexkeymap[randomindex]
# #
# # pool=pool()
# # pool.insert("a")
# # pool.insert("b")
# # pool.insert("c")
# # pool.delete("a")
# # print(pool.keyindexmap)
# # print(pool.indexkeymap)
# # print(pool.size)
# # print(pool.getrandom())
# 
# 
# #布隆过滤器
# #100亿个url做成一个黑名单，请问什么方法需要的空间尽量小？
# #把url1通过哈希函数1得到out1再模上m得到m1，在长度为m的arr中描黑，再通过哈希函数2得到out2再模上m得到m2，继续描黑，通过k个哈希函数可以描黑k个位置
# #把100亿个url都通过这个方法处理。在拿到一个新的url时，如果通过这个过程得到的m1--mk都被描黑了，就可以认为是在黑名单中
# #这个方法可能会把不是黑名单中的url判断为黑的，但是概率随着m的增大减小。且如果是黑的url则一定会被判断出来
# #n=样本量，P=最高失误率
# #m=-(n*lnP)/(ln2)^2，实际使用空间=m/8。
# #k=ln2*m/n≈0.7*m/m，得到的值向上取整
# #P真=(1-e^(-n*k/m))^k，m为实际给你的空间，k为向上取整后的k，得到的p真比p更低
# 
# 
# #一致性哈希原理
# #选择哈希key时，尽量选择种类比较多，使高频中频低频都有数量的key，尽量时负载均衡
# #把数据哈希运算后模上服务器数可以较为均衡的分到每一个服务器，经典结构的问题是增加和减少服务器的代价都是全量的。
# #一致性哈希原理:把服务器的某个特征值经过哈希函数的处理，把特征值放到一个环上，再对每一个数据经过哈希函数的处理，也放到这个环上，划到环顺时针方向最近的服务器。
# #好处是增加或者减少服务器时，只需要分走或者释放最近的那个>=服务器。问题是，机器很少时，很难做到负载均衡
# #解决方法:虚拟节点:给每一个机器分配n个节点，把每一个节点经过哈希函数处理抢环。好处是还可以根据每个服务器的具体性能分配不同的节点数
# '''
# 
# # #一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛。
# # #例:[[0,0,1,0,1,0],[1,1,1,0,1,0],[1,0,0,1,0,0],[0,0,0,0,0,0]],这个矩阵有三个岛
# # def island(m):
# #     if m==None or m[0]==None:
# #         return 0
# #     res=0
# #     for i in range(len(m)):
# #         for j in range(len(m[0])):
# #             if m[i][j]==1:
# #                 res+=1
# #                 infect(m,i,j,len(m),len(m[0]))
# #     return res
# # def infect(m,i,j,lm,lm0):
# #     if m[i][j]!=1 or j>=lm0 or j<0 or i>=lm or i<0:
# #         return
# #     m[i][j]=2
# #     infect(m,i+1,j,lm,lm0)
# #     infect(m,i-1,j,lm,lm0)
# #     infect(m,i,j+1,lm,lm0)
# #     infect(m,i,j-1,lm,lm0)
# #
# # m=[[0,0,1,0,1,0],[1,1,1,0,1,0],[1,0,0,1,0,0],[0,0,0,0,0,0]]
# # print(island(m))
# 
# 
# #并查集
# #如果你有n个样本，如果你的finhead调了O(N)的水平后，则可以认为时间复杂度接近O(1)
# class Element(object):
#     def __init__(self,value):
#         self.value=value
# 
# class UnionFindSet(object):
#     def unionfindset(self,l):
#         self.elementmap={}
#         self.fathermap={}
#         self.rankmap={}
#         for i in l:
#             element=Element(i)
#             self.elementmap[i]=element   #{元素，element格式}
#             self.fathermap[element]=element   #{element格式，该节点的父节点}
#             self.rankmap[element]=1    #{父节点，父节点下有多少节点}
# 
#     def findhead(self,element):    #查找element的头节点
#         a=[]
#         while element!=self.fathermap[element]:    #当不是头节点时，把这个节点放到一个辅助列表中，节点跳到这个节点的父节点
#             a.append(element)
#             element=self.fathermap[element]
#         while a!=[]:   #把所有辅助节点的父节点都设置为头节点
#             self.fathermap[a.pop()]=element
#         return element  #返回头节点
# 
#     def issameset(self,a,b):    #判断a、b是不是在同一个集合
#         if a in self.elementmap and b in self.elementmap:   #如果a、b被写入过，则返回两个节点的头节点是不是同一个
#             return self.findhead(self.elementmap[a])==self.findhead(self.elementmap[b])
#         return False
# 
#     def union(self,a,b):    #合并两个元素的集合
#         if a in self.elementmap and b in self.elementmap:   #如果a、b都被写入过，查找两个的父节点
#             af=self.findhead(self.elementmap[a])
#             bf=self.findhead(self.elementmap[b])
#             if af!=bf:  #如果两个父节点不同
#                 if self.rankmap[af]>=self.rankmap[bf]:  #找到两个集合中较大较小的，方便后续把较小的那个接在较大的那个的下面
#                     thebig=af
#                     thesmall=bf
#                 else:
#                     thebig=bf
#                     thesmall=bf
#                 self.fathermap[thesmall]=thebig    #直接把较小的那个接在较大的那个下面
#                 self.rankmap[thebig]=self.rankmap[af]+self.rankmap[bf]      #把两个集合长度相加赋值给较大的那个集合
#                 del self.rankmap[thesmall]      #删除较小的那个节点的记录
# 
# '''
# #如何设计一个并行算法解决上面求岛问题
# #即把一个矩阵分成两个或者多个矩阵分开计算再合并结果，但是简单的相加可能会导致得到的岛的数量超过实际值
# #在计算其中一张图岛的数量的时候，记录边界位置的的岛
# #例:下图中的矩阵很明显只有一个岛，但是如果从中间分开得到左边2个岛和右边两个岛,记录边界位置的岛部分，不同岛记为不同的点。
# #   得到A、B、C、D四个集合，检查相连出A、C是否为同一个集合，不是则合并(A、C)岛的数量4-1。
# #   检查相连(A、C)和B是否为同一个集合，不是则合并(A、B、C)岛的数量4-1-1。
# #   检查相连的(A、B、C)和D是否为同一个集合，不是则合并(A、B、C、D)岛的数量4-1-1-1。
# #   检查相连的(A、B、C、D)和D是否为同一个集合，是则不做任何操作
# #   所以岛的数量为4-1-1-1=1
# # [1,1,1,1,1,1,1,1]     [1,1,1,1] [1,1,1,1]     [1,1,1,A] [C,1,1,1]
# # [1,0,0,0,0,0,0,1]     [1,0,0,0] [0,0,0,1]     [1,0,0,0] [0,0,0,1]
# # [1,0,1,1,1,1,1,1]     [1,0,1,1] [1,1,1,1]     [1,0,1,B] [C,1,1,1]
# # [1,0,1,0,0,0,0,0]---> [1,0,1,0] [0,0,0,0]---> [1,0,1,0] [0,0,0,0]
# # [1,0,1,1,1,1,1,1]     [1,0,1,1] [1,1,1,1]     [1,0,1,B] [D,1,1,1]
# # [1,0,0,0,0,0,0,1]     [1,0,0,0] [0,0,0,1]     [1,0,0,0] [0,0,0,1]
# # [1,1,1,1,1,1,1,1]     [1,1,1,1] [1,1,1,1]     [1,1,1,A] [D,1,1,1]
# '''
# 
# 
# #字符串str1中是否包含str2，如果包含返回str2在str1中开始的位置
# #常规方法:for i in range(len(str1)):        时间复杂度为O(len(str1)*len(str2))
# #           j=0
# #           while j<=len(str2):
# #               if str1[i]!=str2[j]:
# #                   break
# #               i+=1
# #               j+=1
# #
# #KMP算法:
# #例:"aabcabcabadef"中是否包含"abcabcabab"
# #   首先求str2的nextarr，即这一位前的后缀和前缀一样的最大位，[-1,0,0,0,1,2,3,4,5,1],例如倒数第二位前缀abcab和后缀abcab相同，所以这一位是5
# #   把str1和str2的第一位作比较，a=a,则两组都后移,a!=b,则查看nextarr中这一位是多少
# def getindex(s,m):
#     if s==None or m==None or len(s)<1 or len(m)<len(s):
#         return -1
#     i1=0
#     i2=0
#     nextarr=getnextarr(m)
#     while i1<len(s) and i2<len(m):
#         if s[i1]==m[i2]:
#             i1+=1
#             i2+=1
#         elif i2==0:
#             i1+=1
#         else:
#             i2=nextarr[i2]
#     if i2==len(m):
#         return i1-i2
#     return -1
# 
# def getnextarr(s):
#     if len(s)==1:
#         return [-1]
#     nextarr = [0] * len(s)
#     nextarr[0] = -1
#     nextarr[1] = 0
#     i = 2
#     cn = 0
#     while i < len(s):
#         if s[i - 1] == s[cn]:
#             cn += 1
#             nextarr[i] = cn
#             i += 1
#         elif cn > 0:
#             cn = nextarr[cn]
#         else:
#             nextarr[i] = 0
#             i += 1
#     return nextarr
# 
# '''
#             i1         x
# str1="...... a bcabcab e c......"
#                y      
# ste2="abcabcab a b"
# 经过计算nextarr=[-1,0,0,0,1,2,3,4,5,1]
# 在str1的比对过程中比对到了i1位置，发现后续可以一直比对到str1的x位置，即str2的y位置，对应的next值为5，
# 即前缀abcab和后缀abcab是能找出的最长的相同前后缀。
# 因为出现的比对不匹配的情况，所以需要跳转比对位置重新比对
# 在经典算法中，str1的比对位需要跳转到i1+1上，str2则跳转到0位置
# 在KMP算法中，因为next值位置为5>0，str1的比对位置不跳转停留在x位置，只需要跳转str2位置5位置，即第6个字符第二个c
# 因为"c"!="e",查询nextarr[5]=2，str1比对位置继续停留，跳转str2位置到2位置，即第一个字符c
# 因为又不相等，查询nextarr[2]=0,则把str1的比对位置调转到x的下一个位置，str2的比对位置回到0
# 
# 
# 第一点:为什么str1比对位置会停留在原地，str2比对位置对跳转到nextarr中的值的位置？
# 第一轮比对结束后，因为前面的字符比对相同，所以str1的这一段字符的nextarr值也是相同的
# 即str1的5位后缀==str2的5位前缀，这5位可以直接加速跳过，不需要比对。
# 所以跳过str1的x位置的前5位和str2的前五位，直接比对str1的x位置和str2的5位置(即第六个位置)
# 第二轮同理，跳过了前两位，直接比对str1的x位置和wtr2的2位置(即第3个位置)
# 第三轮，排查了忽略前5位和前2位后，str2比对位置重新回到了0位置，即从头开始比较两个字符组。
# 因为"e"!="a",从str1的x+1位置和str2的0位置开始比对
# 
# 
# 第二点:证明第一轮中i1位置到x-5位置不可能配出完整的str2。
# 假设i1到x-5位置有一个位置k能配出str2。
# 则str1的k到x这段等于str2的等长的前缀，因为str1的k到x这段也可以理解为x的后缀，所以前后缀的长度大于了nextarr中对应的前后缀长度。
# 与nextarr的定义相违背，所以不可能。
# 
# 
# 第三点:如何计算nextarr?
# nextarr的定义是最长前后缀长度。
# abbstabb ec abbstabb?!
# 因为next值只考虑该位置前面的字符情况。所以?位置的next值是8，abbstabb=abbstabb。
# 求！位置的next值，首先拿？和？的前缀后一个位置相比，即"e"和？比较，如果一样则！位置的next值为8+1=9，abbstabbe=abbstabb?
# 如果不一样，则查看？的前缀后一个位置的next值，即"e"位置，"e"的next值为3，abb=abb
# 比对"e"位置前缀的下一个位置"s"是否等于？，如果相等则next为4，abbs=abb？
# 如果不一样，则查看？的前缀后一个位置的前缀的后一个位置的next值，即"s"位置，"s"的next值为0
# 则比对0位置"a"和？，如果相等，则！的next值为1，否则为0
# '''