高效的“滚动/移动哈希”计算（如移动平均）
我正在尝试优化一个程序，该程序需要在数据流的每个位置（字节）为数据流中的恒定大小窗口计算哈希。在比可用RAM大得多的磁盘文件中查找重复时需要它。目前我为每个窗口计算单独的md5哈希，但它花费了很多时间（窗口大小为几千字节，因此每个数据字节被处理几千次）。我想知道是否有一种方法可以在恒定（与窗口大小无关）时间内计算每个后续哈希（例如移动平均中1个元素的加减）？哈希函数可以是任何东西，只要它不提供长哈希（50-100位是可以的）并且它的计算相当快。它还必须在多达数万亿个不那么随机的窗口（TB的数据）上几乎不提供任何碰撞——在我的例子中，每次碰撞都意味着一次磁盘访问（crc32非常弱，md5在这方面还可以）。
如果你给我指出linux上现有的库函数（如果有的话），我将不胜感激。
这是我的第一个问题，所以如果我做错了什么，请宽容。
你好，巴托斯
共有2个答案
您所描述的非常接近数据消重存储中使用的基本方法。
在数据消重系统中，我们通常使用Rabin的指纹方法作为快速、滚动的哈希函数。然而，虽然Rabin指纹具有良好且易于理解的冲突属性，但它在密码学上并不安全，即会发生冲突。检查例如Bentley等人如何在他们的压缩方法中使用这样的方法。问题是您是否可以容忍以及可以容忍多少冲突。如果您可以容忍偶尔的冲突，一个好的Rabin指纹实现可能是个好主意。好的实现可以在每个内核每秒处理超过200 MB。
我不知道有哪种方法几乎没有冲突（也称为加密安全）并同时滚动。作为Plasmah，我非常怀疑这是否真的可能。
想想你是否可以放松限制。也许你可以允许遗漏一些副本。在这些情况下，更快的方法是可能的。
Wikipedia关于滚动哈希的文章有一个到ngramhashing的链接，ngramhashing在C中实现了一些不同的技术，包括：
- 随机化卡普-拉宾（有时称为拉宾-卡普）
- 通过循环多项式（也称为Buzhash）进行散列
- 通过不可约多项式进行哈希
（也可在GitHub上获得）
-
问题内容： 似乎没有函数可以简单地计算numpy / scipy的移动平均值，从而导致解决方案复杂。 我的问题有两个： （正确）用numpy实现移动平均的最简单方法是什么？ 由于这似乎很简单且容易出错，是否有充分的理由不将电池包括在这种情况下？ 问题答案： 一种简单的方法是使用。其背后的想法是利用离散卷积的计算方式，并使用它来返回 滚动平均值 。这可以通过对长度等于我们想要的滑动窗口长度的序列进行
-
问题内容： 美好的一天， 我正在使用以下代码来计算9天移动平均线。 但这是行不通的，因为它会在调用限制之前先计算所有返回的字段。换句话说，它将计算该日期之前或等于该日期的所有关闭时间，而不仅仅是最后9个。 因此，我需要从返回的选择中计算出SUM，而不是直接计算出来。 IE浏览器 从SELECT中选择SUM … 现在我将如何去做，这是非常昂贵的还是有更好的方法？ 问题答案： 使用类似 内查询返回的所
-
公式链接:https://sciencing.com/calculate-exponential-moving-averages-8221813.html
-
我正在将一个站点切换到rails。这是一个拥有5万用户的大型网站。问题是，现有的密码哈希方法非常弱。我有两个选择： 1）切换到一个新的算法，为每个人生成随机密码，然后将这些密码通过电子邮件发送给他们，并要求立即更改 2）实现新算法，但使用旧算法，然后对结果进行哈希。例如： 密码：abcdef=算法1= 任何新密码都需要经过原始算法（md5），然后对结果进行哈希运算，如果这有意义的话？这有什么不利之
-
问题内容： 我需要做类似的事情： 除了，我还需要检索的前20个值的移动平均值。 首选标准SQL，但如有必要，我将使用MySQL扩展。 问题答案： 这只是我的头顶，而且我正要出门，所以未经测试。我也无法想象它会在任何种类的大数据集上表现出色。我确实确认它至少可以正常运行。:)