Rust哈希实现的特别之处


在 Python、Java 或 C++ 等语言中,哈希通常是通过调用对象的“hash”函数方法来实现的,这个方法由类型者自己提供。这种设计存在一些潜在的问题和挑战,主要包括:
  • 如果输入数据已经是随机的,那么使用复杂的哈希函数可能只是在浪费计算周期。
  • 如果使用一个无操作的哈希函数(no-op hasher),那么对哈希表的拒绝服务(DoS)攻击几乎是不可避免的,因为攻击者可以轻易地构造出大量冲突。
  • 如果对整数进行彻底的哈希处理,那些只缓存哈希值以优化等值检查的消费者会损失性能。

如何混合哈希?

  • 如果将混合哈希的任务留给用户,那么每个人都可能会发明自己的糟糕混合器
  • 如果提供一个适用于大多数用例的足够好的混合器,比如 a * x + y,那么可能会因为人们错误地使用 mix(x, mix(y, z)) 而不是 mix(mix(x, y), z) 而导致安全问题。


对于哈希值,您提供什么保证?

  • 是否需要哈希函数具有雪崩效应(avalanche effect)?如果不需要,那么对于简单的二的幂次大小的哈希表来说,哈希函数可能不是最优的。
  • 是否需要半雪崩效应?这样可能会破坏那些或者素数大小的哈希表。

哈希函数的种子问题:

  • 如果哈希函数不是种子化的,那么DoS攻击仍然是一个问题。
  • 如果种子在不同的哈希表之间重用,那么这些表的性能可能会变成二次的。
  • 如果种子明确地传递给每个哈希器,如何确保不同的哈希器不会意外地抵消彼此的效果?

Rust 从这些错误中吸取了教训,将责任分开:

  • 对象实现Hash  trait,允许它们将底层数据写入Hasher对象。
  • 哈希对象实现Hasher trait,对Hash 对象写入的数据进行哈希处理。

对象将结构化数据转换为整数流;哈希器将流转换为数字哈希:

  • 简化整数哈希:
    • 哈希整数时,只需将整数发送给哈希器。这样,消费者可以选择提供必要保证的哈希器。
  • 避免手动混合哈希:
    • 用户不需要手动混合哈希值。哈希器可以以最优的方式完成这个工作。
  • 适应随机数据:
    • 如果已知数据是随机的,可以不改变 Hash 实现的情况下使用快速简单的哈希器。
  • 定制哈希表:
    • 不同的哈希表可以使用不同的哈希器,有效地提供所需的雪崩效果。
  • 种子化哈希器:
    • 哈希器可以为每个表单独设置种子。只有哈希器能够访问种子,因此可以安全地在混合过程中使用种子。
  • 性能优化:
    • 这种设计允许哈希器针对特定类型的数据进行优化,例如,对于小整数可以直接发送给哈希器,而对于复杂的结构化数据,则可以分解为更小的部分进行哈希。
  • 安全性:
    • 通过使用种子和特定的哈希算法,可以降低DoS攻击的风险,因为攻击者更难预测哈希值。
  • 灵活性:
    • 这种分离的责任允许在不同的上下文中使用不同的哈希策略,例如,对于需要高安全性的应用可以选择更复杂的哈希器,而对于性能敏感的应用则可以选择更简单的哈希器。