把数据作为空值或null值的键存储在HashMap中，这是一个好主意吗？

Question

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

我的技术领导要求我将其更改为 HashMap，并将用户名作为键存储在数组中，将值设为空的 Strings。

因此，在Java中 -

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

我可以通过运行以下命令稍后查看该用户是否存在 -

hashmap.containsKey("johndoe"); 

这是 O(1) 的，对吗？

我的领导说这是一种更有效的方法，我也觉得有道理，但是把null/empty作为值放在HashMap中，并将元素存储为键，这似乎有点不对劲。

我的问题是，这样做好吗？效率比ArrayList#contains或普通数组搜索都高。它能工作。 我担心的是，在搜索后我没有看到其他人这样做过。我可能会忽略了某些显而易见的问题，但我看不出来。

- dozer

---

加1，因为当一个人不熟悉Java的数据结构时，这是一个合理的问题。 - Daniel

HashSet是HashMap.keySet()的一种实现。如果你想将一个Map转换为Set，可以使用set = Collections.newSetFromMap(map)。 - Peter Lawrey

如果用户名不区分大小写，使用名称作为键和值的map<string,string>可能有助于映射到用户名的规范表示。 - CodesInChaos

@rdllopes 这个句子绝对没有任何暗示这个问题不适合在Stack Overflow提问。 - Chris Hayes

@rdllopes 我保证你和这个网站上几乎所有的人都有一个知识盲区，有人会认为你“应该知道”。该网站上评分最高的问题中有很多属于这个范畴。你不能成为判断哪些问题不够明显适合在这里发表的仲裁者。 - Chris Hayes

Answer 1

由于您拥有一组唯一的值，Set是适当的数据结构。您可以将这些值放在HashSet中，它是Set接口的一种实现。

我的领导说这是一种更有效的方法，并且对我来说很有道理，但在将null/empty作为值放入哈希映射中并将元素存储为键时，它似乎有点不对劲。

领导的建议是错误的。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 就不需要询问了，它的用法非常自然。

这是O(1)吗？

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

---

一些评论指出，HashSet 是基于 HashMap 实现的。 在那个抽象层面上，这是可以接受的。 在当前任务的抽象层面上 --- 存储一组唯一的用户名， 使用集合是一种更自然的选择，比使用映射更自然。

- janos

---

有一件事我想提醒，虽然我同意这个答案，但你应该与你的技术领导澄清是否需要使用Map。也许他们认为你会使用这个map来存储与用户ID相关的其他信息？如果有任何其他原因需要在内存中存储与用户相关的数据，你可能希望将其存储在那里，而不是在其他地方创建另一个集合，重复代码。 - gmiley

请注意，HashSet 是作为一个 HashMap 实现的，它的值是一个空对象（所有值共用一个实例）。 - Jim Garrison

@Janos：我并不认为主管的建议是有缺陷的……想法是正确的，只是数据结构选择不够优化。即使是空值，Map 仍然使用哈希作为查找键的方法。因此，比起数组迭代，这样做更快。可能技术主管来自 Perl 背景 - 在 Perl 中使用带有空（或虚拟）值的哈希来进行 O(1) 键存在检查是常见实践。Perl 没有 Set 数据结构。 - Greg Kennedy

更精确地说，在Java 8中，如果键是可比较的，那么它的最坏情况是O(log n)；如果特定的桶过度载入，它的链表冲突处理会切换到TreeSet风格的桶。这是为了避免一种拒绝服务攻击，在这种攻击中，攻击者可以定义一个URL，其查询字符串条目故意发生冲突，将预期的O(1)变成O(n)（这样将预期的O(n)循环转化为O(n^2)等）。 - yshavit

在需要使用Java 8中添加到Map的computeIfAbsent方法这样的方法时，Map可能比Set更好。 - Sergey Fedorov

Answer 2

这基本上就是 HashSet 的实现方式，所以我想你可以说这是一种好方法。你可以使用 HashSet 而不是带有空值的 HashMap。

例如：

HashSet中的 add 实现为

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

其中map是支持的HashMap而PRESENT是一个虚拟值。

我的担忧是，在搜索后我没有看到其他人这样做。也许我错过了某个明显的问题，但我没能发现它。

正如我提到的，JDK的开发人员正在使用相同的方法。

- Eran

---

谢谢，为什么不直接使用HashMap.put("aaa","")的现有实现，而要使用HashSet呢？ 另外，既然这种方法很好，那么数组不是就变得多余了吗？ - dozer

@dozer HashSet已经是JDK中现有的一个类，那为什么要重新发明轮子呢？这并不意味着数组变得无用，因为当元素数量固定时，数组更有效率，并且数组（以及ArrayList）允许重复。 - Eran

数组不仅存储元素，而且将它们存储在固定位置；从某种意义上说，它们将数字（即位置）与元素关联起来。相同的信息可以存储在映射中，但是（如果元素在其位置上不是稀疏的话）用这种方式存储的效率要低得多。 - gcali

“这不是让数组变得多余了吗？” 数组中元素的局部性使得迭代比使用分配每个元素单独空间的数据结构（如 maps、set、lists 等）更快。通常连续的数组元素会被一起缓存，因为它们在内存中靠近，从而最小化内存访问。 - Peter - Reinstate Monica