serialization - : hash table or BST in terms of serialization, 并发哪个更合适？

Question

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

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

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

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

P.S:这是一个亚马逊面试问题。

Answer 1

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