algorithm - 用键存储值然后搜索最聪明的方法，算法

Question

我有一个包含超过 2000 万个值的流，这些值带有相应的键(>1000 万)。键链接到一个或多个值(最大 50000)，示例:

... (key1, val1), (key2,val2), (key1, val3), (key2, val4), (key1, val6), (key3,val5)...

我将这个流存储如下:

key1 : val1, val3, val6

key2 : val2, val4

key3 : val5

每次我在流中收到一个新值时，我首先检查这个值是否出现在其对应键的列表中:

• 如果不是，我将值添加到列表的末尾。
• 如果该值已经在最后一个位置的列表中，那么我做 什么都没有。
• 最后，如果值已经在列表中，但不在最后 地方，我发射一面旗帜。

我的问题是:执行此过程的更有效数据结构或工具是什么(我想尽可能快地启动标志)。我想到了一个与链表关联的哈希表(正如我在示例中给出的那样)，但是每次添加值时都检查所有链表听起来不对。回想一下，我确实需要这个 LAST 值的概念。

谢谢

Answer 1

检查新值是否在列表中不是最优的 - 检查需要 O(n) 时间。

您可以改用哈希表。您可以单独存储最后一个值并在插入时更新它。

所以你有一个哈希表，其中的值是成对的。每对由一个哈希表(用作集合)和一个元素(集合中的最后一个元素)组成。

您的示例如下所示:

(key1 -> (val6, (val1->1, val3->1, val6->1))
(key2 -> (val4, (val2->1, val4->1)
(key3 -> (val5, (val5->1))

您可以通过不显式存储最后一个值来优化集合仅包含一个元素的情况。