诸如恒定质量（可变位）摘要哈希算法之类的东西？
Such a thing as a constant quality (variable bit) digest hashing algorithm?
问题space：我们有大量数据需要消化，其大小可能在 6 个数量级范围内。寻找一种更高效的方法，从而使用更少的磁盘 space 来存储所有这些摘要。
所以我在考虑有损音频编码，比如 MP3。有两种基本方法 - 恒定比特率和恒定质量（也称为可变比特率）。由于我的主要兴趣是质量，所以我通常选择 VBR。因此，要达到相同的质量水平，纯正弦音需要比复杂的古典乐曲低得多的比特率。
使用相同的想法，两个非常小的数据块比两个非常大的数据块需要的总摘要位数要少得多，以确保它们的摘要碰撞具有大致相同的统计不可能性（我在这种情况下称之为质量）。这个假设在我看来直觉上是正确的，但话又说回来，我不是加密数学家。另请注意，这完全是关于身份识别，而不是安全性。如果一个小数据块有一个小摘要也没关系，因此在计算上可以重现。
我试着在管间周围搜索类似的东西。我找到的最接近的东西是某个地方的帖子，它谈到使用固定大小的摘要哈希（如 SHA256）作为 AES/CTR 的初始化向量，充当伪随机生成器。然后取第一个x位。
这似乎是一件完全可行的事情。这种方法的唯一问题是我不知道如何根据数据块大小计算 x 的适当值。我认为我的目标质量是两个 1GB 数据块之间 SHA256 冲突的统计不可能性。有人对这个计算有想法吗？
是否有任何现有的摘要哈希算法已经做到了这一点？或者是否有任何其他方法可以产生相同的结果？
更新：看起来有可以输出任意位数的 SHA3 Keccak "sponge"。但是我仍然需要知道我需要多少位作为输入大小的函数才能获得恒定的质量。听起来这个算法会产生无限的比特流，你可以截断任意数量的比特。但是在 Ruby 中进行测试时，我预计 SHA3-512 的前半部分与 SHA3-256 完全相等，但事实并非如此...
如果我对问题的理解正确，你有许多不同长度的数据项，并且你正在为每个项目计算一个散列（即摘要）以便识别这些项目。
假设您已经对 N 项进行了哈希处理（没有冲突），并且您使用的是 64 位哈希码。
您散列的下一项将采用 2^64 值之一，因此当您添加下一项时，您将有 N / 2^64 的散列冲突概率。
请注意，此概率不依赖于数据项的原始大小。它确实取决于您必须散列的项目总数，因此您应该根据您愿意容忍散列冲突的概率来选择位数。
但是，如果您以某种方式对数据集进行了分区，使得每个分区中的项目数量不同，那么您可以通过使用可变大小的哈希来节省少量 space .
例如，假设您使用 1TB 的磁盘驱动器来存储项目，并且所有 >1GB 的项目都在一个驱动器上，而 <1KB 的项目在另一个驱动器上，第三个用于中间大小。第一个驱动器上最多有 1000 个项目，因此您可以使用较小的哈希值，而驱动器上可能有 10 亿个包含小文件的项目，因此较大的哈希值适用于相同的冲突概率。
在这种情况下，哈希大小确实取决于文件大小，但仅以基于分区大小的间接方式。
你的评论逻辑很合理。在输入长度接近（或超过）哈希摘要长度之前，优质哈希函数不会生成 duplicate/previously 生成的输出。
但是，碰撞风险的关键因素是输入的大小设置为散列摘要的大小。使用质量哈希函数时，两个 1TB 文件发生冲突的几率与两个 1KB 文件或什至一个 1TB 和一个 1KB 文件发生冲突的几率没有显着差异。这是因为哈希函数争取uniformity；好的功能实现了它的高度。
由于birthday problem, the collision risk for a hash function is is less than the bitwidth of its output. That wiki article for the pigeonhole principle，这是生日问题的基础，说：
The [pigeonhole] principle can be used to prove that any lossless compression algorithm, provided it makes some inputs smaller (as the name compression suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given length L could be mapped to the (much) smaller set of all sequences of length less than L, and do so without collisions (because the compression is lossless), which possibility the pigeonhole principle excludes.
因此，'VBR' 散列摘要不能保证能拯救您 space。 birthday problem provides the math for calculating the chance that two random things will share the same property (a hash code is a property, in a broad sense), but this article 给出了更好的总结，包括以下 table.
来源：preshing.com
table 的第一行表示，为了与 32 位哈希函数有 50% 的碰撞几率，您只需要对 77k 项进行哈希处理。对于 64 位哈希函数，对于相同的 50% 冲突风险，该数字上升到 50.4 亿。对于 160 位哈希函数，您需要 1.42 * 1024 个输入，然后有 50% 的机会新输入与先前输入具有相同的哈希。
请注意，1.42 * 1024 160 位数字 本身 会占用不合理的大量 space；数百万兆兆字节，如果我没记错的话。这还不包括它们代表的 1024 个项目值。
table 的底端应该让您相信 160 位散列函数具有足够低的冲突风险。特别是，您必须有 1021 个哈希输入，才会有百万分之一的哈希冲突机会。这就是为什么您的搜索结果如此之少的原因：处理复杂性不值得。
然而，无论您决定采用何种哈希策略，都存在非零的冲突风险。依赖哈希的任何类型的 ID 系统都需要进行回退比较。对文件的一个简单的附加检查是比较它们的大小（适用于长度已知的任何可变长度数据，例如字符串）。维基百科涵盖了 hash tables 的几种不同的碰撞缓解和检测策略，其中大部分可以扩展到文件系统，只需一点想象力。如果您需要完美的保真度，那么在您 运行 完成快速检查后，您需要回退到最基本的比较器：两个输入的昂贵的逐位检查。
问题space：我们有大量数据需要消化，其大小可能在 6 个数量级范围内。寻找一种更高效的方法，从而使用更少的磁盘 space 来存储所有这些摘要。
所以我在考虑有损音频编码，比如 MP3。有两种基本方法 - 恒定比特率和恒定质量（也称为可变比特率）。由于我的主要兴趣是质量，所以我通常选择 VBR。因此，要达到相同的质量水平，纯正弦音需要比复杂的古典乐曲低得多的比特率。
使用相同的想法，两个非常小的数据块比两个非常大的数据块需要的总摘要位数要少得多，以确保它们的摘要碰撞具有大致相同的统计不可能性（我在这种情况下称之为质量）。这个假设在我看来直觉上是正确的，但话又说回来，我不是加密数学家。另请注意，这完全是关于身份识别，而不是安全性。如果一个小数据块有一个小摘要也没关系，因此在计算上可以重现。
我试着在管间周围搜索类似的东西。我找到的最接近的东西是某个地方的帖子，它谈到使用固定大小的摘要哈希（如 SHA256）作为 AES/CTR 的初始化向量，充当伪随机生成器。然后取第一个x位。
这似乎是一件完全可行的事情。这种方法的唯一问题是我不知道如何根据数据块大小计算 x 的适当值。我认为我的目标质量是两个 1GB 数据块之间 SHA256 冲突的统计不可能性。有人对这个计算有想法吗？
是否有任何现有的摘要哈希算法已经做到了这一点？或者是否有任何其他方法可以产生相同的结果？
更新：看起来有可以输出任意位数的 SHA3 Keccak "sponge"。但是我仍然需要知道我需要多少位作为输入大小的函数才能获得恒定的质量。听起来这个算法会产生无限的比特流，你可以截断任意数量的比特。但是在 Ruby 中进行测试时，我预计 SHA3-512 的前半部分与 SHA3-256 完全相等，但事实并非如此...
如果我对问题的理解正确，你有许多不同长度的数据项，并且你正在为每个项目计算一个散列（即摘要）以便识别这些项目。
假设您已经对 N 项进行了哈希处理（没有冲突），并且您使用的是 64 位哈希码。
您散列的下一项将采用 2^64 值之一，因此当您添加下一项时，您将有 N / 2^64 的散列冲突概率。
请注意，此概率不依赖于数据项的原始大小。它确实取决于您必须散列的项目总数，因此您应该根据您愿意容忍散列冲突的概率来选择位数。
但是，如果您以某种方式对数据集进行了分区，使得每个分区中的项目数量不同，那么您可以通过使用可变大小的哈希来节省少量 space .
例如，假设您使用 1TB 的磁盘驱动器来存储项目，并且所有 >1GB 的项目都在一个驱动器上，而 <1KB 的项目在另一个驱动器上，第三个用于中间大小。第一个驱动器上最多有 1000 个项目，因此您可以使用较小的哈希值，而驱动器上可能有 10 亿个包含小文件的项目，因此较大的哈希值适用于相同的冲突概率。
在这种情况下，哈希大小确实取决于文件大小，但仅以基于分区大小的间接方式。
你的评论逻辑很合理。在输入长度接近（或超过）哈希摘要长度之前，优质哈希函数不会生成 duplicate/previously 生成的输出。
但是，碰撞风险的关键因素是输入的大小设置为散列摘要的大小。使用质量哈希函数时，两个 1TB 文件发生冲突的几率与两个 1KB 文件或什至一个 1TB 和一个 1KB 文件发生冲突的几率没有显着差异。这是因为哈希函数争取uniformity；好的功能实现了它的高度。
由于birthday problem, the collision risk for a hash function is is less than the bitwidth of its output. That wiki article for the pigeonhole principle，这是生日问题的基础，说：
The [pigeonhole] principle can be used to prove that any lossless compression algorithm, provided it makes some inputs smaller (as the name compression suggests), will also make some other inputs larger. Otherwise, the set of all input sequences up to a given length L could be mapped to the (much) smaller set of all sequences of length less than L, and do so without collisions (because the compression is lossless), which possibility the pigeonhole principle excludes.
因此，'VBR' 散列摘要不能保证能拯救您 space。 birthday problem provides the math for calculating the chance that two random things will share the same property (a hash code is a property, in a broad sense), but this article 给出了更好的总结，包括以下 table.
来源：preshing.com
table 的第一行表示，为了与 32 位哈希函数有 50% 的碰撞几率，您只需要对 77k 项进行哈希处理。对于 64 位哈希函数，对于相同的 50% 冲突风险，该数字上升到 50.4 亿。对于 160 位哈希函数，您需要 1.42 * 1024 个输入，然后有 50% 的机会新输入与先前输入具有相同的哈希。
请注意，1.42 * 1024 160 位数字 本身 会占用不合理的大量 space；数百万兆兆字节，如果我没记错的话。这还不包括它们代表的 1024 个项目值。
table 的底端应该让您相信 160 位散列函数具有足够低的冲突风险。特别是，您必须有 1021 个哈希输入，才会有百万分之一的哈希冲突机会。这就是为什么您的搜索结果如此之少的原因：处理复杂性不值得。
然而，无论您决定采用何种哈希策略，都存在非零的冲突风险。依赖哈希的任何类型的 ID 系统都需要进行回退比较。对文件的一个简单的附加检查是比较它们的大小（适用于长度已知的任何可变长度数据，例如字符串）。维基百科涵盖了 hash tables 的几种不同的碰撞缓解和检测策略，其中大部分可以扩展到文件系统，只需一点想象力。如果您需要完美的保真度，那么在您 运行 完成快速检查后，您需要回退到最基本的比较器：两个输入的昂贵的逐位检查。