方法使此HashMap更有效率

我有一个class User有3个对象（？）我不确定的术语。方法使此HashMap更有效率

的（int）的ID码
用户创建
和

我想创建一个方法（字符串）名称的（INT）日期是

将用户添加到我的数据结构中（1）
根据用户的ID号返回用户名（2）
返回按日期排序的所有用户的完整列表（3）
回报用户列表谁的名字都有一定的字符串，按日期（4）
回报进行排序谁加入的用户的列表之前在特定日期（5）

我已基于该年10个阵列接合（2004-2014年），然后通过日期在再次阵列中的元素进行排序（按月份排序然后天）

我是否认为这意味着方法（3）和（5）具有时间复杂性，但是具有O(1)那（1），（4）和（2）有O(N)？

另外还有另一种数据结构/方法，我可以用我的所有方法有O(1)？我重复地尝试拿出一个，但包含方法（2）让我难住。

来源

2014-02-24 user2962956

基于比较的排序总是O（N * log N）和addi ng已经排序的容器是O（log N）。为了避免这种情况，你需要水桶，就像你现在拥有多年的方式。这交易内存的执行时间。 – hyde

没有办法为所有这些O（1）。例如，＃4 **需要**线性搜索。 – Radiodef

@hyde我的桶不是基于数年的10个阵列吗？ – user2962956

基于比较的排序总是O（N * log N），并且添加到已排序的容器是O（log N）。为了避免这种情况，你需要水桶，就像你现在拥有多年的方式。这交易内存的执行时间。（1）仅当您仅将东西添加到HashMap s时才可以是O（1）。（2）如果您有一个单独的HashMap，它将ID映射到用户，则可以为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）相同，你可以更快地爆发。

来源

2014-02-24 22:58:48 hyde

A HashMap不排序任何东西;其主要目的/优势是提供近O（1）查找（可用于通过ID进行查找）。如果您需要对某些内容进行排序，则应该让该类实现Comparable，将其添加到列表中，并使用Collections.sort对元素进行排序。

至于效率：

O（1）
O（1）
为O（n log n）的
O（n）的（至少）
O（ n）（或更少，但我认为它必须是O（n））

来源

2014-02-24 22:49:41 saiarcot895

还有其他数据结构/方法，我可以使用O（1）为我的所有方法？

三个HashMap。这不是一个数据库，所以你必须手工维护“索引”。

来源

2014-02-24 22:54:49

我看到一个可能的HashMap。第二和第三是什么？ – saiarcot895

不*相当*三个HashMaps，但你会明白。 UserID-> User，UserName-> OrderedSet （按创建日期排序），OrderedSet （按创建日期排序）。可以将其看作手工维护数据库索引，或者像硬编码数据库引擎一样。 –

你必须作出妥协，并对最常见的操作作出明智的猜测。最常见的操作很有可能是通过ID找到用户。因此HashMap是理想的结构：它是O（1），也是插入到地图中的。

要实现按日期排序的用户列表以及给定日期之前的用户列表，最佳数据结构应该是TreeSet。 TreeSet已经排序（所以你的第三个操作是O（1），并且可以在O（log（n））时间返回一个排序子集。

但是将HashMap并行维护一个HashMap非常麻烦，如果这些不是普通的操作，你可以简单地迭代条目并对它们进行过滤/排序，绝对不要忘记你的10个数组。是难以维护，而且一个TreeSet是一个更好更简单的解决方案，不限于10年。

用户的名字包含给定的字符串列表是O（N），无论您选择的数据结构。

来源

2014-02-24 23:00:03

另一种折衷方案是：不要使用TreeSet（它使得添加为* O（log N）*，这会让很多用户感到讨厌），只有在需要排序的顺序时进行排序，在修改之后进行第一次查找为* O（ N * log N）*。 – hyde

方法使此HashMap更有效率

回答

相关问题