5

我有一个效率关键应用程序，我需要这样一个数组类型的数据结构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 秒）。我的申请不能接受这个时间。或者也许有人推荐其他哈希表库？我尝试了 utash.c，它立即崩溃了。

我也试过SDArray，但它似乎不是正确的。

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

谢谢。

4

2 回答 2

6

通常，您需要两个哈希表来完成此任务。如您所知，哈希表可让您在预期的恒定时间内进行关键查找。搜索一个值需要遍历整个数据结构，因为有关这些值的信息没有编码在哈希查找表中。

使用两个哈希表：一个用于键值，一个（反向）用于值键查找。在您的特定情况下，只要您的键是“顺序的”，就可以使用向量来完成前向搜索。但这并没有改变对支持快速反向查找的数据结构的要求。

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

一个实现可能看起来像这样（当然这是可以调整的，比如引入 const 正确性，通过引用调用等）：

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 实现应该“包装”键值哈希映射，因此您的包装类中有“标准”接口。始终保持反向地图与您的正向地图同步。

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

于 2013-04-03T09:32:42.940 回答
0

我会选择两个向量（假设您的值确实不同），因为这是访问中的 O(1)，而访问中的映射是 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];
于 2013-04-03T10:23:51.083 回答