这个问题我想了很久：
您能否利用拥有多个 CPU 的事实在多核机器上构建更快的基础数据结构（即链表、哈希表、集合、跳过列表、布隆过滤器、红黑树等）？
我对 pthreads 做了一些初步试验，发现 pthread_create() 大约需要 30us，但是一个简单的 hash_map 插入比在单核上花费的时间要少得多。因此，我很难想象创建一个更快的 hash_map<>，因为同步原语和线程创建是如此缓慢。我也可以想象树遍历和并行平衡，但同样，同步原语似乎使运行时间更长，而不是更短。
我仍然觉得“我有更多的 CPU，因此，我应该能够更快地做到这一点”对我来说仍然很直观，但我不能完全围绕该陈述的证明或反证明。我在 C++ 中进行了相当多的实验，但现在我怀疑其他语言可能会为此任务提供更好的解决方案（erlang？）。想法？
编辑细节：我认为有几种经常使用的编程/数据结构范例可能会加快速度。例如，我发现自己经常编写基本上看起来像这样的代码（其中真实数据已替换为“rand()”）
static const int N = 1000000;
static const int M = 10000000; // 10x more lookups
hash_map<int, int> m;
// batch insert a bunch of interesting data
for (int i = 0; i < N; i++) m[rand()] = rand();
// Do some random access lookups.
for (int i = 0; i < M; i++) m[rand()]++;
这种范式经常用于名称-值设置和配置数据、批处理等。10 倍（或更多）的查找/插入比率使传统的 hash_map<> 成为此类操作的理想选择。
这可以很容易地分成两半，一个插入阶段和一个查找阶段，在并行世界中，两半之间可能会有一些“刷新队列”操作。更困难的是交错插入 + 查找版本：
hash_map<int, int> m;
for (int i = 0; i < N; i++) {
if (rand() % LOOKUP_RATIO == 0)
hash_map[rand()]++; // "lookup"
else
hash_map[rand()] = rand(); // "insert"
}
在这种情况下，只要在每次查找之前刷新插入队列，插入就可以是异步的，并且如果 LOOKUP_RATIO 足够大（例如，>1000），那么它就变得与上面的批处理示例非常相似，但有一些排队。虽然，排队意味着同步原语。
想象一下，下面的代码片段：
hash_map<int,int> a;
hash_map<int,int> b;
for (int i = 0; i < N; i++) {
// the following 2 lines could be executed in parallel
a[rand()] = rand();
b[rand()] = rand();
}
因此，可以通过以下方式“并行”进行查找：
int lookup(int value) {
// The following 2 lines could be executed in parallel:
v1 = a[value];
v2 = b[value];
if (v1) // pseudo code for "value existed in a"
return v1;
else
return v2;
}