c++ - 名称和伪 ID 的数据结构 : use a hash table or a BST?

Question

我的任务是构建一个数据结构，用于存储从整数“伪 ID”到名称的映射。我可以将新名称插入表中，其中每个名称都与许多伪 ID 相关联，前提是没有任何伪 ID 已被占用。我需要支持按 ID 查找和按 ID 删除，如果我删除某个人的任何伪 ID，它会删除该人的所有伪 ID。

这个程序运行在一个看起来像这样的脚本上:

I JackSmart 3 9 1009 1000009
L 1000009
I TedPumpkinhead 1 19
I PeterMeter 1 9
L 19
D 19
L 19
I JohnCritic 2 1 19
L 19
L 1
L 9

在这里，每一行的第一个字符决定了如何解释它。

• 以 I 开头的行是一个插入。该行的其余部分将包含一个名称，后跟该名称的多个伪 ID，然后是每个伪 ID。除非任何伪 ID 已在使用中，否则应插入该名称。

• 以 L 开头的行是一个查找。该行包含要查找的伪 ID。我需要打印与之关联的名称，或者报告不存在这样的名称。

• 以 D 开头的行是删除。该行包含要删除的伪 ID。然后我需要从表中删除与该伪 ID 相关联的人，这样通过他们的伪 ID 查找他们的任何现在都失败了。

此任务的输出(根据顶部的示例文件)将是:

ok
JackSmart
ok
no
TedPumpkinhead
ok
no
ok
JohnCritic
JohnCritic
JackSmart

这里最好的方法是什么？我应该使用哪种数据结构来完成这项任务？因为有插入和删除，所以我认为是BST。有什么想法吗？

此外，这需要高效运行。每个任务都应该在最坏情况下运行 O(log n)。

Answer 1

让我们逐步了解尝试解决此问题的不同方法。

解决此问题的一个选择是存储某种关联数组，其中每个键都是一个伪 ID，每个值都是一个名称。要进行插入，您需要检查每个伪 ID 是否空闲。如果是，则将键/值对插入每个槽。要进行查找，您只需按 ID 进行查找并返回找到的内容。要执行删除操作，您需要查找与键/值对关联的键，然后遍历表并删除具有该值的每个键/值对。

这种方法对于插入和查找来说非常快，但是对于删除来说真的很慢。具体来说，插入一个带有 k 个伪 ID 的名字需要 O(k) 次关联数组操作(每个操作的运行时间取决于我们如何实现关联数组)，查找一个名字需要 O(1) 次关联数组操作，但是删除需要 O (n) 关联数组操作。

为了加快速度，我们可以使用的一个技巧是让每个值存储，除了实际名称之外，还有与该名称关联的所有伪 ID 的列表。这样，当我们执行删除时，我们可以查找哪些伪 ID 需要删除，而不必从字面上查看关联数组中的每个条目。这要快得多 - 它降低了 O(k) 关联数组操作的删除成本，其中 k 是删除的元素数。

为了让事情变得甚至更快，一个聪明的想法是让关联数组中的每个值都是一个指向存储两条信息的结构的指针:与条目关联的实际名称，加上一个标志，指示该元素是否已被删除。然后每个伪 ID key 存储一个指向该共享结构的指针。每当您进行删除时，只需将结构上的“已删除”标志设置为 true 即可删除键/值对的所有拷贝。但是，键/值映射仍将存在于表中，因此每当您进行查找或插入并找到存储在某处的键/值对时，在断定键的伪 ID 已被使用之前，您会检查标志。如果它被标记为已删除，那么您可以假装该 ID 不再被使用。如果它没有被标记为已删除，您就知道该条目是实时的并且应该跳过它。

这里有一些伪代码:

Maintain an associative array "table."

To do a lookup(pseudoID):
   if table[pseudoID] doesn't exist, return null
   if table[pseudoID] exists, but table[pseudoID].deleted is true, return null
   return table[pseudoID].value

To do insertion(name, id1, id2, ..., idk):
   for (each id):
      if (lookup(id) != null) return false

   create a new structure:
      entry.value   = name
      entry.deleted = false 

   for (each id):
      table[id] = entry

To do delete(id):
   lookup(id) == null: return false;
   table[id].deleted = true

总的来说，这种新方法需要 O(k) 次关联数组操作来插入具有 k 个伪 ID 的名称，O(1) 次关联数组操作来查找，O(1) 次关联数组操作来删除.

现在的问题是表示关联数组的最佳结构是什么。请注意，我们永远不需要担心按排序顺序访问任何内容，因此虽然我们可以使用 BST，但最好使用哈希表来完成此操作，因为它(按预期)要快得多。因此，如果在 BST 和哈希表之间进行选择，我会使用哈希表，因为它可能会快得多。不过，如果您需要保证最坏情况下的效率，则可以使用 BST。

对于 BST，k 个 ID 的插入运行时间为 O(k log n)，查找和删除都将在最坏情况下运行时间为 O(log n)。对于哈希表，k 个 ID 的插入在预期的 O(k) 时间内运行，查找和删除都将在预期的 O(1) 时间内运行。

根据可用于伪 ID 的数字类型，另一种选择可能是使用二进制 trie。这将取决于 key 中可以包含多少位以及您期望所有内容的密度。