江苏龙网

  1. 首页 > 生活 > >

将一个哈希值A不断进行哈希，无穷多次后，还能返回到A吗

结论。定长的哈希无限次后一定会出现重复数字。但还没法证明给定的数字一定会重复证伪假设不会出现A，且每次哈希值定长为L，数字（字母）范围数量为N那么总共的数字数量为N^L根据抽屉原理，当哈希次数大于N^L时一定出现重复
■网友
如果证明是双射，就一定能。如果不是双射，那么就要看A在不在环上了。
■网友
看你hash算法md5 sha1之类的具体早忘了但是只要满足对于对于0..N，输出也在0...N里均匀分布，或者说在0...N这个输入输出集合上构建的hash映射可以做到双射，就肯定会再次出现。原因么，双射啊。
■网友
题目说是一个哈希值A，那么不论采用哪种算法，这个输出的A总是有固定位数的，也就有了取值上限，我们假定是2^256量级，我们称之为为N。显然这里N是一个足够大的值。
【将一个哈希值A不断进行哈希，无穷多次后，还能返回到A吗】 在这里，我们把哈希算法简化为一个从range（N）到range（N）的随机映射。collision free的性质在这里显然不适用了，不然这个题就答案显然是不能。或者我们假设在有限次哈希算法中无法得到相同的值，以可以物理实现的操作次数视为有限次，以上的视为无限次，这个限度我们假定是2^80的量级，显著的小于N的，我们设为M。
puzzle friendly这个性质，我们就简化成成简单的随机映射。
这样就相当于把所有N以内的数字随机映射到另外一个N以内的数。那么问题来了，把所有N都做一次哈希，那么输出的值有多少种可能性？
问题相当于这样有N个盒子，每个盒子里面有N种球，随机每个盒子拿一个球，最终有多少种球。
其实我也不是很清楚这个属于哪种分布，但是根据我的直觉吧，结论是（1-1/e）N个球，意思是有1/e的部分只可能由其他值的哈希直接得到，而不能由两次哈希得到。【这个结果我不是很确定，其实也并不关键，我们下面假设成xN】。
根据puzzle friendly的性质，我们再次对这些结果进行操作，那么能得到的值又会缩减相同的比例，不然就产生了两次哈希和三次哈希的输出的分布有不同的性质，违反哈希的性质。
那么，再根据collision free的性质，在M次操作内不会产生相同的值，那么重复上述过程M次以内不会产生A。同时，因为在M次操作内仍然满足hash的性质，所以此时的可选值依然是足够大的，依然满足上述分布律，每次按照当前比例x缩减可能得到的值。（其实这个时候我对结论有怀疑，因为这个数量应该已经缩减到1以下了，应该到一定次数之后，因为N的值迅速缩减，与N无穷大的拟合偏差越来越多，或者N的离散度越来越低，导致缩减的比例减小了，但是很难计算这个速度）
这个时候，M次哈希可能产生的结果只剩下N*x^M，即使计算到上面应该发生的缩减，总归是比N/M要小的，这是所有M次哈希之后可能得到的值。按照以上的假设，M次哈希之内不会发生碰撞，所有只有此时的输出值，有可能跟之前产生的输出值产生碰撞。
同时我们也知道，对任意数字，做N+1次哈希，结果肯定会有碰撞的时候。
所以结论就是，一定存在这种A，经过多次哈希之后回到A，但是在有生之年你是找不到这个A了。换句话说，就是如果你随机取的这个A，A可以多次哈希然后回归到A的概率是0，虽然这件事情可能发生。
就约等于，在实数域上面随机抽取一个数，抽到一个有理数差不多。这件事有可能发生，但是概率是0。


    推荐阅读


    上一篇：为啥网络上的一些大大要隐瞒自己的性别呢

    下一篇： 「扦插」扦插太阳花，1根枝条就长满花盆，很简单，小时候的回忆