0

最近我读了一些关于散列技术的论文。散列似乎无处不在。

在计算机科学中，哈希表通常被用作一种高效的查找数据结构。

在加密中，散列是在诸如 md5 散列、sha 散列等技术中。

在数据库区。散列是在数据库中建立表的键。

在机器学习中，散列是为高效处理和经济存储创建短散列码，例如局部敏感散列、min-hash、sim-hash、散列技巧等。

这些应用程序在散列方面的相同点和不同点是什么？你能帮忙提供一些关于这些散列的读物或参考吗？尤其是它们之间的差异。我对这些散列技术感到困惑。

4

1 回答 1

1

我认为散列的要点是能够获取一组可变长度、动态和异步的内容，并能够将算法应用于该内容的每个成员，从而产生“稳定”、固定大小，并且本质上是每个标识符的唯一标识符。这就是您引用的大多数示例的重点：

  • 哈希表：将可变长度的键字符串或结构转换为具有已知下限和上限的“稳定”唯一标识符（即数组中的行号、数组中的行地址、数据库中的行号）。
  • 密码学：将可变长度的纯文本转换为稳定的、唯一的、固定长度的标识符。
  • 机器学习（至少是散列技巧）：将单词（可能还有它们的上下文）转换为稳定且唯一的键，转换为通用的数字组织本体

在所有这些情况下，您都在对组中每个成员的可变长度内容进行小总结。这些小摘要使处理所有可变长度内容变得更加容易，并且在哈希表的情况下可以显着加快处理速度。或者特别是在密码学可以提供显着好处的情况下，例如密码保护（当使用正确的密钥和重复散列时）或内容完整性验证。

您会注意到散列几乎总是导致冲突的可能性：例如，组中两个完全不同的成员具有不同的内容，但散列算法生成相同的摘要/散列值。哈希函数设计的一个关键部分是确定允许的可接受的重复级别，并在哈希实现的设计中正确处理发生冲突时的冲突。对于仅使用少量 RAM 的哈希表，冲突率可能很高。使用 256 位加密散列函数，碰撞概率可能实际上为零。

此外，散列几乎总是“一种方式”。大多数散列算法是故意“有损”的（这就是重复发生的原因），因此通常不能仅从摘要/散列值反向计算原始可变长度内容。有一些蛮力的方法可以解决这个问题，但简单快速的反向计算通常是不可能的。

请注意，我们在现实生活中也使用“散列算法”。我们在大公司中使用同事的名字是为了方便交谈/发送电子邮件/聊天（一个微不足道的哈希），即使肯定会有许多同名的同事。因此发生了冲突（“你是指会计部门的玛丽还是航运部门的玛丽？”）。您可以将所有已知的面巾纸产品“散列”成“Kleenex”一词（至少在美国是这样），但仍然更喜欢购买和使用不同的品牌。

于 2015-03-29T12:26:59.303 回答