用于开放地址哈希表的高效C++应用编程接口

Question

我正在构建一个C++开放地址哈希表。它由以下数组组成：

struct KeyValue {
    K key;
    V value;
}

其中类型密钥具有两个特殊元素:空和墓碑。第一个用来说明插槽是空闲的，第二个用来说明插槽已经被使用过，但后来被删除了(这对于探测是必要的)。

主要的挑战是为这种结构设计一个有效的API。我希望最大限度地减少散列密钥和查找槽的次数。

到目前为止，我发现以下API是不安全的：

// Return the slot index if the key is in the table
// or a slot index where I can construct the KeyValue
// if the key is not here (or -1 if there is no slot
// available and the insertion of such a key would
// need to grow the hash table)
int search(const K& key)

// Tells if the slot is empy (or if i == -1)
bool empty(int i)

// Construct a KeyValue in the HashTable in the slot i
// which has been found by search. The i might be changed
// if the table needs to grow.
void insert(const K& key, const V& value, int& i)

// Accessors for a slot i which is occupied
const V& value(int i);

请注意，该表还具有经典函数，例如

void insert(const K& key, const V& value)

它计算散列，搜索槽，并将该对插入到表中。但我想在这里集中讨论允许程序员非常有效地使用表的接口。

例如，这里有一个函数，如果从未计算过f(键)的值，则返回f(键)的值；如果已经计算过，则从HashTable返回它的值。

const V& compute(const K& key, HashTable<K, V>& table) {
    int i = table.search(key);
    if (table.empty(i)) {
        table.insert(key, f(key), i);
    }
    return table.value(i);
 }

我并不完全热衷于这个HashTable的接口，因为方法insert(const K&，const V&，int&)对我来说真的很不安全。

你对更好的API有什么建议吗？

PS: Chandler Carruth的演讲“算法的性能，数据结构的效率”，特别是在23:50之后，很好地理解了std::unordered_map的问题

Answer 1

我认为你应该尝试超快的散列函数。

看看这个，https://github.com/Cyan4973/xxHash。我从它的描述中引用："xxHash是一个非常快的哈希算法，在内存速度限制下运行。它成功地完成了SMHasher测试套件，该测试套件评估哈希函数的冲突、分散和随机性质量。代码高度可移植，哈希在所有平台上都是相同的(小端/大端)。“

还有这个网站上另一个问题的帖子：Fast Cross-Platform C/C++ Hashing Library。众所周知，FNV、Jenkins和MurmurHash都很快。

看看这篇文章，我在这里发布了相同的答案，还有其他答案：Are there faster hash functions for unordered_map/set in C++?

Answer 2

您可以创建一个接受任意函数而不是值的get_or_insert函数模板。然后您可以使用lambda调用它：

template <class K, class V>
class HashTable {
private:
    int search(const K& key);
    bool empty(int i);
    void insert(const K& key, const V& value, int& i);
    const V& value(int i);

public:    
    template <class F>
    const V& get_or_insert(const K& key, F&& f) {
        int i = search(key);
        if (empty(i)) {
            insert(key, f(), i);
        }
        return value(i);
    }
};

double expensive_computation(int key);

void foo() {
    HashTable<int, double> ht;
    int key = 42;
    double value = ht.get_or_insert(key, [key]{ return expensive_computation(key); });
}

如果get_or_insert是内联的，并且您不需要捕获很多内容，那么这应该和您显示的代码一样高效。如果有疑问，可以使用Godbolt的Compiler Explorer或类似工具比较生成的代码。(如果它没有被内联，它仍然是可以的，除非你必须捕获很多不同的变量。假设您捕获的是smart -即，如果复制成本较高，则通过引用捕获内容。)

注意:在C++中传递函数器的“标准”方法似乎是通过值传递，但我认为通过引用传递更有意义。如果所有的东西都被内联了，它不应该有什么不同(在我检查过的例子中，GCC，Clang和MSVC)，如果get_or_insert调用没有被内联，如果它捕获了超过1到2个小的和琐碎的变量，你真的不想复制函数器。

我能想象到的使用通用引用的唯一缺点是，如果你有一个在operator()中改变其状态的函数器。对于这样的函数式，至少在我能想到的例子中，我希望原始的函数式是变异的。所以，这并不是一个真正的缺点。

或者上面的一个修改版本，适用于值的创建/分配/销毁开销很大的情况(如std::string)：使用对插槽中的值的可变引用来调用函数器。然后函数器可以直接分配/修改哈希表->中的值，而不需要构造和销毁临时。