hash - 关于散列及其用于数据压缩的说明

Question

我正面临一个使用散列的应用程序，但我仍然无法弄清楚它是如何工作的。这是我的问题，散列用于生成一些索引，并使用这些索引访问不同的表，并且在我添加使用索引获得的每个表的值之后，我得到了我的最终值。这样做是为了减少内存需求。散列函数的输入是在随机常数和应用程序的一些参数之间进行异或运算。

这是一个典型的哈希应用程序吗？我不明白的是如何使用散列来减少内存需求？任何人都可以澄清这一点吗？

谢谢

Answer 1

单独的散列与内存没有任何关系。

它通常用于哈希表。哈希表通过计算您要键入的内容的哈希值来工作，然后将其用作数据结构的索引。

散列允许您将键（字符串等）减少为更紧凑的值，如整数或位集。

这可能是您所指的内存节省 - 将大键减少为简单整数。

但请注意，哈希不是唯一的！一个好的散列算法可以最大限度地减少冲突，但它们并不打算减少到一个唯一值——这样做是不可能的（例如，如果你的散列输出一个 32 位整数，你的散列将只有 2^32 个唯一值）。

Answer 2

你说的是布隆过滤器吗？这使用哈希函数来获得一种空间有效的方法来测试集合的成员资格。如果是这样，请查看链接以获取说明。

Answer 3

大多数好的散列实现都是内存效率低下的，否则会涉及更多的计算——而这正是散列的重点。

哈希实现用于提高处理效率，因为它们将为您提供插入、删除和检索等操作的恒定运行时间。

您可以考虑散列的质量，即所有数据，无论是什么类型或大小，始终以一个固定长度的形式表示。

Answer 4

如果进行散列不是为了构建真正的散列表，而只是在字符串/内存块表中创建索引，则可以解释这一点。如果您的数据中有 20 次相同的字符串（或内存序列），然后仅用其哈希/表索引替换该字符串的所有 20 个实例，则可以通过这种方式实现数据压缩。但是，如果该表中包含每个哈希值的实际冲突链，那么我刚才描述的不是正在发生的事情；在这种情况下，散列的原因很可能是为了加快执行速度（通过提供对存储值的快速访问），而不是压缩。