java - 将数据存储为具有空/空值的 HashMap 中的键是一个好主意吗？

Question

我最初编写了一个 ArrayList 并在其中存储了唯一值(用户名，即 Strings)。后来我需要使用 ArrayList 来搜索其中是否存在用户。那是 O(n) 的搜索。

我的技术主管希望我将其更改为 HashMap，并将用户名作为键存储在数组中，将值存储为空 Strings。

所以，在 Java 中 -

hashmap.put("johndoe","");

我可以稍后通过运行查看此用户是否存在 -

hashmap.containsKey("johndoe"); 

这是 O(1) 对吧？

我的负责人说这是一种更有效的方法，这对我来说很有意义，但将 null/empty 作为值放在 hashmap 中并将元素作为键存储在其中似乎有点不对劲。

我的问题是，这是一个好方法吗？效率胜过 ArrayList#contains 或一般的数组搜索。有用。我担心的是，我没有看到其他人在搜索后这样做。我可能在某处遗漏了一个明显的问题，但我看不到它。

Answer 1

由于您有一组唯一值，因此 Set 是合适的数据结构。您可以将您的值放入 HashSet，这是 Set 接口(interface)的实现。

My lead said this was a more efficient way to do this and it made sense to me, but it just seemed a bit off to put null/empty as values in the hashmap and store elements in it as keys.

领导的建议有缺陷。 Map 不是正确的抽象，Set 是。 Map 适用于键值对。但是你没有值，只有键。

示例用法:

Set<String> users = new HashSet<>(Arrays.asList("Alice", "Bob"));

System.out.println(users.contains("Alice"));
// -> prints true

System.out.println(users.contains("Jack"));
// -> prints false

使用 Map 会很尴尬，因为值的类型应该是什么？这个问题在你的用例中没有意义，因为您只有键，而不是键值对。有了Set，你就不用问了，用法很自然。

This is O(1) right?

是的，在 HashMap 或 HashSet 中搜索是 O(1) 摊销的最坏情况，而在 List 或数组中搜索是 O(n) 最坏的情况。

---

一些评论指出 HashSet 是根据 HashMap 实现的。没关系，在那个抽象级别。在手头任务的抽象层次上——存储唯一用户名的集合，使用集合是一种自然的选择，比 map 更自然。