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++.

谢谢.

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实现应该"包装"键值哈希映射,所以你的包装类中有"标准"接口.始终将反向地图与前向地图保持同步.

关于创建性能:在大多数实现中,有一种方法可以告诉数据结构要插入多少元素,称为"reserve".对于散列表,这是一个巨大的性能优势,因为动态调整数据结构大小(在插入过程中偶尔发生)会完全重构整个散列表,因为它会更改散列函数本身.