对于这个练习题，使用嵌套哈希表是否有效？
Is it efficient to use nested hashtables for this practice problem?
我的任务是为以下问题找到最有效的解决方案：我需要打印出 (k) 流媒体播放最多的电影流派 (g)，在给定的年份，(y)，i可以假设它需要 o(1) 来检索当前年份。这方面的一个例子是：
每次流式传输电影时，我都会得到电影的名称和类型。
“2014 年 5 流式传输最多的 爱情片 电影是什么？
返回的答案可能类似于
- MovieName1（爱情）3409 流
- MovieName2（爱情）4000 流
- MovieName3（爱情）5340 流
- MovieName4（爱情）9000 流
- MovieName5（爱情）10000 流
所以我的想法是使用 3 个嵌套哈希表。
- 其中我使用他们的名字（键）映射到频率（值）
- 一个我使用流派（键）映射到地图（名称，频率）（值）
- 最后一个我使用年份（键）映射到地图（流派，
地图（名称，频率）（值）
这有什么意义吗...我认为写这篇文章让我自己感到困惑..
是否可以只使用一个哈希表，将它们的年份用作键并映射到一个节点链表，其中每个节点都包含电影名称、频率和流派？这样会更有效率吗？
所以如果我想更新蝙蝠侠的频率我可以做 map.get(2008) 这将给出链表的头部
然后做
while(tmp != null){
if(tmp.name == "the dark knight"){
temp.frequency++;
}
所以你考虑过使用年份的哈希图到流派的哈希图到名称到频率的哈希图。是否有意义？当然。这是解决问题的好方法吗？很可能不会。正如您所说，也可以使用单一的年份主散列映射到流派-名称-频率元组（或结构，在许多语言中 - 如 C、C++、Java 等）的集合).对于集合，您想到了链表，但您也可以很好地使用向量或其他东西（链表通常是最糟糕的一种数据结构）。但这不会更有效，也不一定是解决问题的更好方法，即使它可能更具可读性和可维护性。
我不会谈论不影响时间复杂度的性能改进，因为你已经在评论中明确表示这是一个只关心时间复杂度的考试（这很可悲，但无论如何).另外，我假设这是您需要解决的唯一问题。
让我们看看如何改进您的想法。碰巧的是，两种解决方案的混合以及一项改进，在时间复杂度方面提供了最佳解决方案，即 O(k)。首先，请注意每个电影名称仅与一个频率相关联，并且每个频率（可能）仅与一个电影名称相关联。并且由于您想根据频率检索电影名称，因此哈希图与名称-频率对的线性集合（例如向量或链表）相比没有任何优势。然后，请注意每年和每种流派都（独立地）与多部电影相关联（每部电影都有名称和频率）。因此哈希图在这里占有一席之地：对于给定的年份和给定的类型，类似哈希图的结构将在预期的恒定时间内为您提供相关的电影。
结合这两个结果，您将得到一个哈希图，其中年份和流派作为键，名称-频率对的集合作为值。可以在 O(k) 时间复杂度内检索给定年份和流派的 k 流式传输最多的电影的一项改进是排序：如果您的名称-频率对在每个集合中按频率排序，您可以简单地 return 第一个（或最后一个，取决于顺序）k 个名字。
您可能会觉得奇怪的一个细节是哈希图同时使用年份和流派作为键。那是一个实现细节。您可以使用两个嵌套的哈希映射来实现，一个使用年份作为键，另一个使用流派，或者您可以组合年份和流派并直接使用这些对作为键。散列年份-流派对实际上很简单。
我的任务是为以下问题找到最有效的解决方案：我需要打印出 (k) 流媒体播放最多的电影流派 (g)，在给定的年份，(y)，i可以假设它需要 o(1) 来检索当前年份。这方面的一个例子是： 每次流式传输电影时，我都会得到电影的名称和类型。 “2014 年 5 流式传输最多的 爱情片 电影是什么？
返回的答案可能类似于
- MovieName1（爱情）3409 流
- MovieName2（爱情）4000 流
- MovieName3（爱情）5340 流
- MovieName4（爱情）9000 流
- MovieName5（爱情）10000 流
所以我的想法是使用 3 个嵌套哈希表。
- 其中我使用他们的名字（键）映射到频率（值）
- 一个我使用流派（键）映射到地图（名称，频率）（值）
- 最后一个我使用年份（键）映射到地图（流派， 地图（名称，频率）（值）
这有什么意义吗...我认为写这篇文章让我自己感到困惑.. 是否可以只使用一个哈希表，将它们的年份用作键并映射到一个节点链表，其中每个节点都包含电影名称、频率和流派？这样会更有效率吗？
所以如果我想更新蝙蝠侠的频率我可以做 map.get(2008) 这将给出链表的头部
然后做
while(tmp != null){
if(tmp.name == "the dark knight"){
temp.frequency++;
}
所以你考虑过使用年份的哈希图到流派的哈希图到名称到频率的哈希图。是否有意义？当然。这是解决问题的好方法吗？很可能不会。正如您所说，也可以使用单一的年份主散列映射到流派-名称-频率元组（或结构，在许多语言中 - 如 C、C++、Java 等）的集合).对于集合，您想到了链表，但您也可以很好地使用向量或其他东西（链表通常是最糟糕的一种数据结构）。但这不会更有效，也不一定是解决问题的更好方法，即使它可能更具可读性和可维护性。
我不会谈论不影响时间复杂度的性能改进，因为你已经在评论中明确表示这是一个只关心时间复杂度的考试（这很可悲，但无论如何).另外，我假设这是您需要解决的唯一问题。
让我们看看如何改进您的想法。碰巧的是，两种解决方案的混合以及一项改进，在时间复杂度方面提供了最佳解决方案，即 O(k)。首先，请注意每个电影名称仅与一个频率相关联，并且每个频率（可能）仅与一个电影名称相关联。并且由于您想根据频率检索电影名称，因此哈希图与名称-频率对的线性集合（例如向量或链表）相比没有任何优势。然后，请注意每年和每种流派都（独立地）与多部电影相关联（每部电影都有名称和频率）。因此哈希图在这里占有一席之地：对于给定的年份和给定的类型，类似哈希图的结构将在预期的恒定时间内为您提供相关的电影。
结合这两个结果，您将得到一个哈希图，其中年份和流派作为键，名称-频率对的集合作为值。可以在 O(k) 时间复杂度内检索给定年份和流派的 k 流式传输最多的电影的一项改进是排序：如果您的名称-频率对在每个集合中按频率排序，您可以简单地 return 第一个（或最后一个，取决于顺序）k 个名字。
您可能会觉得奇怪的一个细节是哈希图同时使用年份和流派作为键。那是一个实现细节。您可以使用两个嵌套的哈希映射来实现，一个使用年份作为键，另一个使用流派，或者您可以组合年份和流派并直接使用这些对作为键。散列年份-流派对实际上很简单。