C/C++中的64位数组操作

Question

我有一个效率至关重要的应用程序，需要一种类似于数组的数据结构A。它的键为0, 1, 2,...，其值为uint64_t类型的不同值。我需要两个常量操作：

1. Given i, return A[i];
2. Given val, return i such that A[i] == val

我不想使用哈希表。因为我尝试过GLib GHashTable，将6000万个值加载到哈希表中需要大约20分钟的时间（如果我删除插入语句，则只需要大约6秒）。这个时间对我的应用程序来说是不能接受的。或许有人能推荐其他哈希表库吗？我尝试了uthash.c，但它立即崩溃了。

我还尝试了SDArray，但似乎不是合适的选择。

有人知道任何可以满足我的要求的数据结构吗？或者有任何高效的哈希表实现吗？我更喜欢使用C/C++。

谢谢。

- Joy

---

如果您有C++11，可以尝试使用std::unordered_map。一般来说，您需要两个哈希表，一个用于键值查找，另一个用于值-键查找。当然，您必须在两个表中插入新条目。 - leemes

@leemes：写一个回答！ - Lightness Races in Orbit

在开始添加条目之前，请确保在哈希表中预留足够的空间。例如，如果您正在使用std::unordered_map，请调用my_unordered_map.reserve(6e7)（6e7 == 6000万）。 - Nicu Stiurca

@Zeta 我更喜欢C语言，但如果不行的话，我可以接受C++。我正在从C向C++转移。 - Joy

@Alexey_Frunze 只有哈希表插入。如果我删除插入操作，加载时间仅需约6秒。我的键是uint64_t，值是指针。 - Joy

Answer 1

一般来说，您需要两个哈希表来完成此任务。正如您所知，哈希表可以在预期的常数时间内为您提供键查找。搜索值需要迭代整个数据结构，因为值的信息没有编码在哈希查找表中。

使用两个哈希表：一个用于键值，一个（反向）用于值-键查找。在您的特定情况下，如果您的键是“连续的”，则可以使用向量进行正向搜索。但这并不改变快速反向查找的数据结构要求。

关于哈希表的实现：在C++11中，您可以使用新的标准容器std::unordererd_map。

一个实现可能如下所示（当然，这是可调整的，例如引入const-correctness、按引用调用等）：

std::unordered_map<K,T> kvMap; // hash table for forward search
std::unordered_map<T,K> vkMap; // hash table for backward search

void insert(std::pair<K,T> item) {
    kvMap.insert(item);
    vkMap.insert(std::make_pair(item.second, item.first));
}

// expected O(1)
T valueForKey(K key) {
    return kvMap[key];
}

// expected O(1)
K keyForValue(T value) {
    return vkMap[value];
}

一份干净的C++11实现应该“包装”键值哈希映射，所以您在包装器类中有“标准”接口。始终确保反向映射与正向映射同步。

关于创建性能：在大多数实现中，有一种方法可以告诉数据结构将插入多少个元素，称为“预留”。对于哈希表来说，这是一个巨大的性能优势，因为动态调整数据结构大小（每隔一段时间发生插入）会完全重新构造整个哈希表，因为它会改变哈希函数本身。

- leemes

---

一般来说，我同意。但在这种特定情况下，使用数组（或std::vector）进行正向搜索不是更好吗？这应该会使用更少的RAM并且速度更快。 - user9876

你说得对，我没有注意到键是连续的。当然，在这种情况下，你应该使用针对这种情况进行优化的容器，即vector。 - leemes

@leemes：第二个map应该是unordered_map<T, K>，不是吗？ - Zeta

@leemes 非常感谢！我试了一下unordered_map，仅需40秒即可加载6000万个值。你救了我的命。 - Joy

@CaiShaojiang：有两个原因：首先，GHashTable是一个C库。C++是一种更强大的语言。C代码必须通过指针工作，这不如C++模板快。其次，unordered_map来自Boost，这是一个非常有能力的软件开发团队。 - MSalters

Answer 2

我会选择使用两个向量（假设您的值确实是不同的），因为这在访问时是O(1)，而使用map则是O(log n)。

vector<uint64_t> values;
vector<size_t> keys

values.reserve(maxSize); // do memory reservation first, so reallocation doesn't occur during reading of data
keys.reserve(maxSize); // do memory reservation first, so reallocation doesn't occur during reading of data

然后，在读取数据时

values[keyRead] = data;
keys[valueRead] = key;

读取信息的方法是相同的

data = values[currentKey];
key = keys[currentData];

- ogni42