我应该使用“Set”还是“List”？

Question

我正在学习Java.util.Collection，遇到了以下问题和答案。

考虑四个核心接口：Set、List、Queue和Map。对于以下四个任务中的每一个，请指定哪个核心接口最适合，并说明如何使用它来实现任务：

1. “Whimsical Toys Inc(WTI)”需要记录其所有雇员的姓名。每个月，将从这些记录中随机选择一个雇员赠送免费玩具。

教程提供的答案是：使用List。通过在0和size()-1之间选取一个数字来选择一个随机的雇员。

但我想知道，不应该使用Set而不是List吗？因为每个雇员都是独立的个体，我们不希望同一个雇员被多次输入。我的想法正确吗，还是我漏掉了什么？有没有人有建议？感谢您提前的任何帮助！

- user5849987

---

ArrayLists是常用的，虽然Set不能包含重复项。不过你可以使用ArrayList来检查重复项。 - Logan

@LoganKulinski 感谢您的评论。您有什么建议，我应该使用“Set”还是“List”？ - user5849987

不客气。List和Set是接口，因此您必须使用实现它们的类。例如，ArrayList类实现了List。 - Logan

我认为这些任务是很好的学习机会。感谢分享。但我强烈建议您发布您所做的工作，以解决您的问题。在您的特定情况下，名称和随机访问非常重要。我假设您可以有相同的名称，因此唯一性在这里并不重要。最重要的需求是随机访问。所以我想它已经为您提供了足够的信息来思考。 - The Roy

我很好奇，如果“Tom”被选为免费玩具的获得者，而公司中有多个名为“Tom”的人…… - Nier

Answer 1

但是我在想，应该使用Set而不是List吧？因为员工是独特的个体，我们不希望同一个员工被多次输入。

尽管员工是独特的个体，他们的名字可能并不是唯一的。使用Set会消除重复，但也会错误地删除具有相同姓名的不同员工的姓名。

- Sergey Kalinichenko

Answer 2

列表似乎是更好的选择。列表中的元素可以在常量时间内访问。如果您使用的是ArrayList，则可以使用list.get（index）方法直接获取所需的员工。

但是，如果您选择使用Set，则需要迭代set直到找到随机选择的员工。

例如：

int size = empHashSet.size();
int employee = new Random().nextInt(size);
int i = 0;
for(Employee emp : empHashSet)
{
    if (i == employee)
        return emp;
    i = i + 1;
}

因此，清单明显是正确的选择。

- Varun Risbud

---

实际上，情况恰恰相反。列表的时间复杂度为O(n)，也就是线性的，而集合的时间复杂度为O(1)，也就是常数级别的。 - Krakowski mudrac

Answer 3

“员工是独特的个体，我们不希望同一个员工被输入多次。”

- dimo414

Answer 4

看起来List是一个不错的选择：

创建每个用户的对象，名称可能相同但其他信息可以不同创建单独的对象。

将这些对象放在ArrayList下面。

覆盖hashCode和equals方法以提供您的比较逻辑。

[例如，您可以有不同的方式来比较对象，也许根据年龄作为其中一个成员变量，这可能是唯一的或需要唯一的“员工ID”，这将解决您的重复问题]

现在为什么列表有帮助：

1. 索引
2. 通过使用list.contains（object o）（以及您的equals和hashCode实现），您可以避免重复

要选择随机数很容易，只需使用Math.random或Random类对象从完整列表中引用随机整数即可。

- Apurv Nerlekar

Answer 5

首先：如问题评论中所述，更有趣的是更详细地了解问题。一般来说，回答问题使用具体版本的List或Set（例如ArrayList或HashSet）并不那么简单。

让我稍微解释一下为什么会这样，并思考一些你可能会有的想法：

使用 ArrayList: 如果你知道不会向列表中添加相同的 Employee，那么 ArrayList 是一个好的解决方案。如果你知道什么时候可能会第二次添加 Employee，它也是一个不错的选择。在后一种情况下，你可以使用如下代码检查员工信息：

private List<Employee> employees = new ArrayList<>();

public void addEmployee(final Employee employee, final boolean check) {
    if (check) {
         Employee found = employees.stream().filter(e -> e.equals(employee)).findFirst().orElse(null);
         if (found == null) {
             this.employees.add(employee);
         }
     } else {
         this.employees.add(employee);
     }
}

使用 HashSet: 如果添加重复元素的可能性很高，HashSet 更快。但随机访问元素时速度较慢（参见 Varun Risbud 的帖子）。

你不应该忘记，在这两种情况下，Employee类必须有一个equals函数（参见例如在Java中重写equals和hashCode时应考虑哪些问题？）。此外，当使用HashSet时，Employee的实现还需要重写'hashCode'。

- Philipp

Answer 6

名称可能包含重复项。在集合中不能有两个Tom。

- Hengqi Chen

---

从一组名字中，你怎么知道随机结果指的是哪个Tom？无论数据结构如何，这个问题陈述都不能处理重复的名字。 - dimo414