c++ - 插入具有已知哈希值的 C++ unordered_map

Question

我有一个“表”，它是 std::unorderd_set基本上，std::vector<int>使用哈希函数返回 vector 中所有元素的哈希值的异或。因此， vector 的哈希值仅取决于元素，而不取决于它们的顺序。

现在，我正在该表上实现动态编程，该表应该首先检查表中是否已存在 vector ，如果没有，则为其计算表条目。然而，这种计算可能会改变 vector 元素的顺序。所以这就是我想做的，大致如下:

using Entry = vector<int>;
using Table = unordered_set<Entry, set_hash>; // set_hash is the XOR-based hasher
Table dp_table;

const Entry& query(const vector<int>& q) {
  auto [iter, success] = dp_table.emplace(q);
  // alternatively, I can dp_table.find() here, computing the hash of q
  if(success) {
    compute_entry(*iter); // I want to permute *iter here (doesn't change its hash)
    // alternatively, I can dp_table.emplace() here, computing the hash of q a second time
  }
  return *iter;
}

现在，我在这里编写的方式不起作用，因为 *iter是常量。可以理解，如unordered_set无法确定我的修改不会改变散列(但我知道它不会)。以下是可能的解决方案以及我不喜欢它们的原因:

1. 我可以使用“替代”方式，但这意味着我必须重复(昂贵的)哈希计算，这是我真正想避免的。我希望能够告诉unordered_set “嘿，这是那个东西的哈希值，相信我”，但这是不可能的。
2. 我可以包裹 Entry在我声明 vector mutable 的类中(如建议的 here )，但这意味着每当我处理表的元素时，我都会失去常量正确性。另外，我认为修改 const-item 是正式的 UB。
3. 我可以修改哈希器，以便它存储每个项目的哈希值，并且只获取这个缓存的哈希值，而不是在看到具有预先计算的哈希值的项目时重新计算哈希值，但如果我确实更改了 vector 并忘记了，那就很危险了清除缓存的哈希值。它还会占用额外的内存空间，这是我想避免的。

这就是我的问题，也是为什么我不喜欢我能想出的所有解决方案。您有更好的想法如何解决这个问题吗？非常感谢:)

Answer 1

您可以将计算出的哈希值与 vector 一起存储:

class Entry {
public:
    std::size_t hash() const { return m_hash; }
private:
    std::vector<int> m_data;
    std::size_t m_hash{};
};

template <> struct std::hash<Entry> {
    size_t operator()(const Entry& e) const { return e.hash(); }
};

然后只有在执行实际影响哈希值的操作时才重新计算哈希值。

当您需要对 vector 执行以任何方式更改它的操作时，只需提取它，进行更改并重新插入它:

std::unordered_set<Entry> s;
Entry e;
auto [sit, _] = s.insert(e);
    
auto node = s.extract(sit);
node.value().operation_that_does_not_alter_the_hash();
s.insert(std::move(node));

由于成员函数operation_that_does_not_alter_the_hash()不会改变哈希值，因此不需要重新计算它。当将节点重新插入到unordered_set中时，它将调用成员函数hash()，该函数将返回预先计算的值。

如果您另一方面调用 operation_that_does_alter_the_hash()，该函数应该重新计算哈希并存储它。同样，重新插入节点将以相同的方式完成，并且不需要额外重新计算哈希值。

Demo