存储和散列的最佳方式键 (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。
• 利用对称性应该很容易。