4

我认为如果我们通过链接解决冲突，哈希表会更合适，因为对于任何读取或写入操作，我们都必须获取哈希表中该条目（索引和值）的锁定，而我们必须获取整个 BST 的锁定以对其进行任何更新。

我认为我们需要锁定整个 BST 结构，因为假设我们必须在树中插入一个新节点，我们首先必须遍历到达正确的父位置（比如节点 A），如果我们还没有获得锁定树结构可能会改变，我们必须重新开始。

在散列表的情况下，输入总是散列到相同的位置，我们知道要锁定哪个索引，这在 BST 的情况下是未知的。

请在我错的地方纠正我并帮助我找到正确的答案。

PS：这是一个亚马逊面试问题。

4

2 回答 2

0

你可以做一个混合解决方案。做一个哈希表，其中每个槽都是二叉树。所以说 1024 个插槽，每个插槽都有一棵二叉树。哈希上的冲突进入二叉树，不需要在插入时锁定所有内容，只需更新需要更新的树。

此外，如果您使用原子操作和一些技巧，您可以通过完全避免锁定来使其更加并发。原子更新插入新节点，如果原子更新失败另一个线程添加了一个节点，只需再次循环，直到成功。

我已经这样做了 https://github.com/exodist/GSD/tree/master/Structures

这是一个高度并发的哈希/树混合。它使用原子操作，没有互斥体。它可以在插入时旋转，但从不阻止对现有键的读取或更新。它可以调整大小/平衡/等。您可以遍历所有条目等。管理自己的内存并具有用于引用计数键/值的回调。您还可以将一个字典中的键“链接”到另一个字典，以便更新第一个键中的键会改变第二个键的值。

当您在问题上投入更多线程时，这种设计实际上会提高性能：

(T)是多少个线程，忽略MI，slots是使用了多少个hash slot，Ops是插入了多少个项目（除以线程看每个线程做了多少）

./performance.run
   T, MI,   Slots,      Ops:      Insert   Rebalance      Update      Resize      Lookup      Immute            
   4, 16,    1024,  5000000:  2.765500363  0.915232065  2.540659476  2.172654813  2.545409560  2.089993698
13.029449975
   4, 16,   32768,  5000000:  2.122459866  1.403548309  2.413483374  1.885083901  2.092272466  2.643681518
12.560529434
   4, 16, 1048576,  5000000:  1.700994809  1.063704010  2.030809367  2.457275707  1.453413924  3.671012425
12.377210242
  16, 16,    1024,  5000000:  0.785675781  2.311281904  1.805610753  0.621521146  0.549546473  0.744009412
6.817645469
  16, 16,   32768,  5000000:  0.497359638  0.316017553  1.257663142  0.610761414  0.390849355  0.825944608
3.898595710
  16, 16, 1048576,  5000000:  0.328308989  0.647632801  1.267230625  1.139402693  0.342399827  1.189220470
4.914195405
  64, 16,    1024,  5000000:  0.129407132  0.767262021  2.631929019  0.157977313  0.103848004  0.177964574
3.968388063
  64, 16,   32768,  5000000:  0.087656606  0.068330231  1.365794852  0.166261966  0.079112728  0.203542885
1.970699268
  64, 16, 1048576,  5000000:  0.074605680  0.284322979  1.372998607  0.650503349  0.084956938  0.828653807
3.296041360

注意：在具有 8GB 内存的 i7 上单次运行。在从旧的 __sync 切换到 __atomic 的过程中使用 gcc atomic 内置函数，由于内存模型，这可能有助于提高性能。

于 2013-11-01T00:20:45.070 回答
0

我认为就并发性而言，您所说的是正确的，哈希表将是更好的选择，但就序列化而言，我认为 BST 会更好。这是因为在 BST 中我们将只有数据节点，但是在哈希表中我们将有数据的键和值对，并且很少有没有值的键。因此，与 BST 相比，它在序列化时将需要更多空间。

于 2013-02-21T09:27:21.537 回答