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

Question

我有一个“表”，它基本上是

std::unorderd_set

的

std::vector<int>

，带有一个散列函数，该函数返回向量中所有元素的散列值的 XOR。因此，向量的哈希值仅取决于元素，而不取决于它们的顺序。

现在，我正在对上述表实施动态规划，该表应该首先检查表中是否已经存在向量，如果不存在，则为其计算表条目。但是，此计算可能会更改向量元素的顺序。所以这就是我想做的，大致是：

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

   包装在一个类中，在该类中我声明向量

   mutable

   （如建议的 here），但这意味着每当我处理表的元素时我都会失去 const-correctness。另外，我认为修改 const-item 是正式的 UB。
3. 我可以修改散列器，使其与每个项目一起存储散列，并且只使用这个缓存的散列，而不是在它看到带有预计算散列的项目时重新计算散列，但是如果我更改向量并忘记清除，那将是危险的缓存的哈希。它还会占用额外的内存空间，我想避免这种情况。

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

Answer 1

您可以将计算出的哈希值与向量一起存储：

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(); }
};

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

当你需要对向量执行任何改变它的操作时，只需提取它，进行更改并重新插入它：

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()

，该函数应该重新计算哈希并存储它。同样，重新插入节点将以相同的方式完成，不需要额外重新计算哈希值。

演示

Answer 2

为了将来参考，我最终对 Ted 的 code 进行了轻微修改：我将

vector<int>

包装在一个类

Entry

中，声明向量成员

mutable

并具有允许任意排列

vector<int>

的函数。这保证了哈希的完整性，并且没有我在之前的方法中提到的任何缺点。

class Entry {
protected:
    mutable std::vector<int> data;
public:
    void permute_data(const Permutation& perm) const { ... }
    ...
};