c++ - 存储和散列 键的最佳方式 (C++)

Question

我的目标是创建一个高效的结构来存储矩阵中最相关的条目，该矩阵(在没有内存限制的情况下)大约为 10^5 x 10^5 并填充 double 。该矩阵是对称的，因此它实际上只包含 (10^10)/2 个值。

我需要在模拟中多次访问条目，因此快速检索至关重要。

为了使结构易于管理，我将删除不太可能使用的成员。如果索引是 (int_x1, int_x2)，我通常会想删除所有包含例如 x1 的对。

这项任务的最佳结构或结构集是什么？什么是两个整数的好散列？

为了便携性，我想避免使用 Boost。我目前在程序的其他地方使用 TR1 的 unordered_map。我正在考虑再次使用 key 对使用 unordered_map，但我不确定我如何能够以这种方式有效地删除条目，而且我不知道一个好的哈希函数是什么样的。

我是一名初级程序员，所以请说明显而易见的事情。

Answer 1

如果数据非常稀疏，您可以使用哈希表数组。

hash_map<int,double> matrix[] = new hash_map<int,double>[10000];
for (int i = 0; i < 10000; i++) matrix[i] = new hash_map<int,double>();

然后要查找值 (x,y)，您使用 x 索引数组并在哈希表中查找 y。

需要注意的几点:

• 删除可能会非常昂贵，因为您必须遍历大量哈希表。
• 总存储量会随着您的删除/插入而增长，您应该偶尔修剪()您的 hash_maps。
• 应该很容易利用对称性。