安微省城城乡建设厅网站,大丰建站,电子商务网站设计原则,服装设计网页大家吼啊#xff01;这是我下定决心写专栏以来的第二篇文章#xff0c;请大家多多资瓷#xff01;#xff01;同样我们先以上次的话起头吧#xff01;恭喜你找到了这篇博客#xff01;虽然这个标题看起来非常像是nc营销号的标题但是#xff01;请相信我一次这是真的这是我下定决心写专栏以来的第二篇文章请大家多多资瓷同样我们先以上次的话起头吧恭喜你找到了这篇博客虽然这个标题看起来非常像是nc营销号的标题但是请相信我一次这是真的如果不行请随时取关等等你好像还没关注我那不如现在先关注看完再取关吧哈哈好了不跟你多BB想象你现在有一堆数你要把他们装进一堆桶里相同的数放在一起你会怎么做呢哦这太简单了只要在每个桶上面标上这个数然后把数丢进相应的桶不就完了咦怎么有个桶看起来就很蠢的样子那我们在程序上怎么实现这个桶呢啊答主你是没学过数组还是怎么的直接开一个a[1000]假设来了一个数x就让a[x]自加1不就行了好啊但你这有个小问题。要是来一个9999怎么办开a[10000]那要是来99999呢987654321呢或者更直接来个字符串呢难道要开字符串为下标的数组这怎么可能呢。字符串到整数的唯一映射——字符串哈希让我们想想问题出在哪。下标必须是一个不太大的正整数也就是说我们要将一个字符串变成一个不太大的正整数。首先我们将每个字符看做等于他的ASCII码的整数这样字符串就变成了一个数串且每个数不超过127只有字母和数字的话ASCII是不超过127的。现在我们就来突发奇想啦怎么才能用一个数表示这个数组呢从前有这样一种东西它的每一位都不超过127也就是说不到128……啊这不就是一个128进制的数吗从左到右分别代表了这个128进制数的从高位到低位……然而我们现在知道的是这个数的每一位要得到这个数是很简单的。比如[100,55]这个数有两位那么这个数的值就是100×1285512855有三位的话如[127,100,55]那就是127×(128^2)100×128552093623那么我们只需要提前处理出128的若干次方然后分别与这个数的每一位相乘就能得到这个数了完美等等128的5次方不就超出int范围了吗超就超要知道我们实际上要建立的是一个单射关系即只要能通过一个字符串推出一个唯一确定的数我们的目的就达到了。我其实是求出了这个128进制数的值的只是最后将它映射到了int范围里的数。这时聪明的读者说你这样损失了信息万一两个128进制数本来不同这么一搞给你搞成相同的了那不完犊子了考虑到这个数已经很大了将它mod一下int范围其实已经相当于int范围内的随机数了只是这个数是由字符串唯一确定的。既然是随机数那不同的字符串映射到相同数的概率就跟在0~2147483647里随机取两个数它们相等的概率一样了。在实际中我们可以认为这个概率就是0。完美当然现在这个数的范围是0~2147483647。如果想要继续缩小范围那么可以再mod一个随便什么数原理同上。当然你mod的数也不能太小。具体如果你取N那么平均情况下在计算到第1.17*√N个字符串时有50%的概率会重复证明可搜“生日攻击”。所以建议在不超过限度的情况下尽量取大。int 喜欢的话就支持一下啦想笔者出什么文章或者有什么建议也可以在评论区说☆
