我有一个值超过2000万的流，它带有相应的键(超过1000万)。密钥链接到一个或多个值(最大50000)，例如：
... (key1, val1), (key2,val2), (key1, val3), (key2, val4), (key1, val6), (key3,val5)...
我将此流存储如下：
键1:val1、val3、val6
键2:val2，val4
键3:val5
每次我在流中收到一个新值时，我首先检查这个值是否出现在其对应密钥的列表中：
- 如果不是，我会在列表末尾添加值
- 如果值已经在列表的最后一位，那么我会什么都没有
- 最后，如果值已经在列表中，但不在最后地方，我推出了一面旗帜
我的问题是：执行此过程的更高效的数据结构或工具是什么(我希望尽可能快地启动标志)。我想到了一个与链表相关联的哈希表(正如我在示例中给出的)，但每次添加值时检查所有链表听起来并不正确。回想一下，我确实需要LAST值的概念。
谢谢
检查新值是否在列表中不是最佳的-检查需要O(n)时间。
您可以使用哈希表。您可以单独存储最后一个值，并在插入时对其进行更新。
因此，您有一个哈希表，其中的值是成对的。每对由一个哈希表(用作集合)和一个元素(集合中的最后一个元素)组成。
您的示例如下：
(key1 -> (val6, (val1->1, val3->1, val6->1))
(key2 -> (val4, (val2->1, val4->1)
(key3 -> (val5, (val5->1))
当集合只包含一个元素时，您可以通过不显式存储最后一个值来优化情况。