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

Question

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

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

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

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

为了便携性，我想避免使用 Boost。我目前在程序的其他地方使用 TR1 的 unordered_map。我正在考虑再次将 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。
• 应该很容易利用对称性。