1

新的 C++11 标准具有无序容器。特别是，std::unordered_map<Key, Value>存储std::pair<Key, Value>在一个基于std::hash<Key>（默认散列函数）的位置。同样，std::unordered_set<Key>将 Key 存储在基于 的位置std::hash<Key>。

我的问题是：如何仅将键值对的值存储在基于的位置std::hash<Key>？如果使用完美的散列函数，即不同的键映射到不同的散列索引（因此永远不需要冲突解决），这将很有用。

unordered_set 只使用键，而 unordered_map 同时使用键和值，因此新 C++11 标准中的无序 STL 容器似乎不允许这种自定义。从现有的 STL 容器中获取这种数据结构的好方法是什么？

更一般地说，如何将 a 存储std::pair<T, Value>在基于 的位置中std::hash<Key>，T表示密钥签名的类型在哪里？例如，如果 Key 是一个大型数据结构，我想计算一个 64 位哈希键并将其分成两个 32 位部分：高 32 位与值一起形成 a std::pair<uint32_t, Value>，低 32 位确定它的位置存储对。

这将是有用的应用程序，例如计算机国际象棋，其中作为密钥类型的位置（在某些程序中为数 KB）被散列为 64 位密钥，其中只有高 32 位和一些搜索相关信息作为值type 以 a std::pair（通常总共只有 16 个字节）的形式存储在基于哈希键的低 32 位的位置中。

4

5 回答 5

1

为您要用作键的类型实现散列函数，然后创建一个类型来保存散列值并专门化该类型的 std::hash 以仅返回散列值。现在您可以计算散列，丢弃用于计算散列的数据，并将值及其散列粘贴到映射中。

要检索一个值，您以某种方式重建关键数据，然后您可以重新计算散列值，然后在映射中搜索该散列。

于 2012-01-09T21:56:07.810 回答
1

我可能完全弄错了，但为什么不只std::unordered_map<uint32_t, std::pair<uint32_t, Value>>使用一些不错的实用功能来插入和提取呢？

// demonstration with 32bit 'hash' and 16bit 'lo' and 'hi'
#include <unordered_map>
#include <string>
#include <stdint.h>
#include <iostream>

int main(){
    typedef std::unordered_map<uint16_t, std::pair<uint16_t, std::string>> map_type;
    map_type m;
    std::string key = "hello", value = "world";
    uint32_t hash = std::hash<std::string>()(key);
    uint16_t lo = hash & 0xFFFF, hi = hash >> 16; // make a nice function for this
    m.insert(std::make_pair(lo, std::make_pair(hi, value))); // and this
    auto it = m.find(lo); // and this
    std::cout << "hash: " << hash << '\n'
              << "lo: " << it->first << '\n'
              << "hi: " << it->second.first << '\n'
              << "lo | (hi << 16): " << (it->first | (uint32_t(it->second.first) << 16)) << '\n'
              << "value: " << it->second.second << '\n';
}

Ideone 上的现场演示。

输出：

hash: 1335831723
lo: 11435
hi: 20383
lo | (hi << 16): 1335831723
value: world
于 2012-01-09T22:16:12.033 回答
1

由于 C++11 哈希实际上是一种类型size_t，因此您可以执行以下操作：

template <typename T>
struct with_hash
{
    size_t hash;
    T value;
};

template<> struct std::hash<with_hash>
{
    typedef size_t result_type;
    typedef with_hash argument_type;
    size_t operator()(const with_hash &x)
    {
         return x.hash;
    }
};

template <typename T>
using perfectly_hashed = std::unordered_set< with_hash<T> >;

在这里和那里再加上一些语法糖……

于 2012-01-09T21:45:52.463 回答
1

我的问题是：如何仅将键值对的值存储在基于 std::hash 的位置？如果使用完美的散列函数，即不同的键映射到不同的散列索引（因此永远不需要冲突解决），这将很有用。

完美的哈希函数是不够的。您不仅要保证没有哈希冲突，还必须确保没有桶冲突。哎呀，您甚至必须确保桶的数量永远不会改变，因为您的数据结构无法发现键的哈希值。

于 2012-01-10T17:22:56.950 回答
1

如果不连续访问散列值，就没有通用的方法来对散列执行操作。例如，假设哈希在内部使用树。要将新节点添加到哈希中，您需要将其哈希值与树上现有节点的哈希值进行比较。如果你没有将它们的值存储在树中，你怎么能做到这一点？

您所要求的可能并非不可能，但没有一个典型的散列算法可以做到。无论如何似乎没有任何意义，您必须存储一些东西才能使集合可遍历，而且很难看出除了哈希之外的其他东西如何像哈希一样工作，因为这就是您正在搜索的内容为了。

如果散列“太大”，请使用散列的散列。（当然，那么你必须处理哈希冲突。）

于 2012-01-09T21:48:23.260 回答