问题标签 [constant-time]

我有一个 class Person，它有另一个类的向量Badge（具有唯一的 Id）。要访问向量中的所有元素，我可以遍历元素，这需要 O(n) 时间，n 是向量的大小。我想在恒定时间内完成，所以我创建了一个地图，其中Badgeid 作为键，指针Badge作为值。这里，指针指向向量的一个元素。进一步来说：

涉及的功能：

完整的代码可以在这里找到：https ://www.ideone.com/hjUT6e

在运行该函数时，大多数时候会遇到运行时错误。有时，代码按预期工作，而其他时候，该updateRoyalty()函数对版税点没有影响，这意味着它与根本没有调用该函数一样好。

有没有办法解决这种奇怪的行为？我可以想到两个想法：

1）使用std::find()函数搜索向量中的元素并重载运=算符。但这也需要 O(n) 时间

2) 代替Badge *，Badge用作 中的值unordered_map。这里有两个问题。首先，Badge 没有被调用的构造函数Badge()，它有一个参数化的构造函数。所以编译器抱怨。其次，我需要重载[]运算符，编写自己的哈希函数。我对 C++ 相当陌生，所以在这里尽量保持简单（如果可能，语言独立）。

请让我知道如何实现这一目标

谢谢

编辑：该问题已被标记为重复并已关闭。重复的问题当向量需要更多内存并重新分配内存时，指针会发生什么？是一个完全不同的问题。它与调整向量内存的大小有关，而这与将指针（作为映射中的值）存储到向量元素有关。我要求重新提出这个问题。

从包括对可变长度字符串的 hash() 操作在内的程序的运行时间来看，我觉得 hash() 函数可能需要恒定的时间来对不同长度的字符串进行操作。为了验证我的假设，我制定了以下策略 -

• 创建长度为 k 的字符串
• 对字符串进行散列，记录hash()操作时间t
• 对于从 0 到 100,00 变化的 k 重复此操作，并生成字符串长度 k 与时间 t 的关系图。

因此，如果我猜测 hash() 函数在对字符串进行操作时是一个常数时间操作是正确的，你能用外行的术语解释为什么会这样吗？一个概念或理论解释而不是对源代码的引用将是更可取的 - 关于即使是大字符串如何立即产生散列，而与字符长度无关。

以下是上述策略的代码实现——

以下是生成的图 -

在这个网站：http ://elijahcaine.me/remote-timing-attacks/作者很好地描述了什么是恒定时间攻击以及如何防范这种类型的漏洞。

但是在作者所做的代码中：

我不明白为什么我们必须添加这一行才能使恒定时间攻击成功：

在网站上，作者说：

它夸大了评估 is_equal 函数所需的时间。

我试过了，我们需要一个“休眠”的方法来让这个攻击成功。为什么我们需要夸大时间？

我需要在恒定时间内获取字符串在列表中的位置，

但没有找到任何这样的 Java 实现。

考虑到当前计算机的内存大小，也许没有必要这样做；-)

LinkedHashMap 很有趣，但不保持位置。（参考）

有什么线索吗？

有很多关于 PHP 的文章指出，在进行直接字符串比较时可能会发生持续定时攻击。我编写了一些示例代码来尝试确定数量级差异，但它表明即使进行数百万次测试，也并非总是一个比另一个快。

您会期望第一次迭代活动时间更快，因为字符串中的第一个字符是错误的，因此比较可以退出，但情况并非总是如此。

在 Java 中，每次遍历所有元素时都会使用字符串方法，并使用 O(n) 找到长度，或者将长度存储在某处以在我们查询长度时返回 - 具有恒定的时间复杂度。