java - 使这个HashMap更高效的方法

Question

我有一个 User 类，它有 3 个对象(？)我不确定术语。

• (整数)ID 代码
• 用户创建的(整数)日期
• 和(字符串)名称

我正在尝试创建一种方法

• 将用户添加到我的数据结构 (1)
• 根据 ID 号返回用户的姓名 (2)
• 返回按日期排序的所有用户的完整列表 (3)
• 返回姓名包含特定字符串的用户列表，按日期排序 (4)
• 返回在特定日期 (5) 之前加入的用户列表

我根据加入年份(2004-2014)创建了 10 个数组，然后再次按日期对数组中的元素进行排序(按月然后日排序)

我是否正确地认为这意味着方法 (3) 和 (5) 具有 O(1) 时间复杂度，但 (1)、(4) 和 (2) 具有 O(N) ？

还有另一种数据结构/方法可以用来为我的所有方法提供 O(1) 吗？我反复尝试想出一种方法，但方法 (2) 的包含却让我难住了。

Answer 1

基于比较的排序始终为 O(N*log N)，并且添加到已排序的容器为 O(log N)。为了避免这种情况，你需要水桶，就像你多年来一直拥有的那样。这会用内存换取执行时间。

仅当您仅将内容添加到 HashMap 时，(1) 才可以是 O(1)。

如果您有一个单独的 HashMap 将 ID 映射到用户，(2) 的复杂度可以是 O(1)。

(3) 当然是 O(N)，因为你需要列出所有 N 个用户，但是如果你有一个 HashMap，其中 key 是日期，value 是用户列表，那么你只需要通过恒定(10年* 365天+ 2)数量的数组来列出所有用户。所以 O(N)，其中 (1) 仍然是 O(1)。假设用户在一天之内未排序。

(4) 与 3 基本相同，实现简单，只是打印较少。您也许可以使用 trie 或其他东西来加速最佳情况，但它仍然是 O(N)，因为它将匹配 N 的某些百分比。

(5) 与(3)相同，只是可以更快爆发。