0

在我的项目中，有 N 个线程来访问一个全局哈希表，这是无法避免的。所以我认为我应该使用无锁哈希表或其他东西。毕竟我选择尝试别的东西，而不是lockfree hash table，因为lockfree hash通常是有特殊用途的，不是那么好用。

我的想法是：

有N个线程可以访问全局哈希表，因此我将哈希表溢出到M个子哈希表，其中M >= N。任何时候，所有线程从 M 个子哈希表中选择 N 个子哈希表的总和为 pow(M, N)，从 M 个唯一的子哈希表中选择 N 个子哈希表的总和为 P(M, N)，所以没有竞争条件的比率是P(M, N)/pow(M, N)，存在竞争条件的比率是1-P(M,N)/pow(M,N )，即 1-M!/(MN)!/pow(M,N)。

我的计算，r表示存在竞争条件的比率：

线程数=2

n=2, m=2 r=0.5
n=2, m=3 r=0.333333
n=2, m=4 r=0.25
n=2, m=5 r=0.2
n=2, m=6 r=0.166667
n=2, m=7 r=0.142857
n=2, m=8 r=0.125
n=2, m=9 r=0.111111
n=2, m=10 r=0.1
n=2, m=11 r=0.0909091
...
n=2, m=100 r=0.01
...

线程数=3

n=3, m=3 r=0.777778
n=3, m=4 r=0.625
n=3, m=5 r=0.52
n=3, m=6 r=0.444444
n=3, m=7 r=0.387755
...
n=3, m=29 r=0.10107
...

线程数=5

n=5, m=5 r=0.9616
n=5, m=6 r=0.907407
n=5, m=7 r=0.850062
n=5, m=8 r=0.794922
n=5, m=9 r=0.743941
...
n=5, m=96 r=0.100425

线程数=8

n=8, m=8 r=0.997597
n=8, m=9 r=0.99157
n=8, m=10 r=0.981856
n=8, m=11 r=0.968964
n=8, m=12 r=0.953583
...
n=8, m=268 r=0.100095

好处是选择合适的m，90%的时候可以解锁

缺点是我们浪费了很多资源。

我的想法对吗？有没有更好的解决方案？

4

1 回答 1

0

我认为你的算法的复杂性不值得它的好处。实际上还有很多更简单的解决方案。在开始之前，最好确定使用模式。我可以这样总结它们：

  • HashTable readonly - 初始化一次，读取是安全的。
  • 仅追加或读/写比率高 - 每次写入重新创建哈希表并使用 Interlocked.CompareExchange 替换。
  • 读/写比率低 - 使用基于 spinwait 的 Reader/Writer 锁。

请记住 - 确定问题最佳解决方案的唯一方法是仔细测试和测量！

于 2013-09-05T07:25:57.687 回答