将数据作为键存储在具有 empty/null 值的 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 接口的实现。

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 实现的。很好，在那个抽象级别。在手头任务的抽象级别--- 存储一组唯一的用户名，使用 set 是自然的选择，比 map 更自然。

Answer 2

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

例如：

HashSet 对 add 的实现是

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

其中 map 是支持 HashMap，PRESENT 是虚拟值。

My worry is, I haven't seen anyone else do this after a search. I may be missing an obvious issue somewhere but I can't see it.

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

将数据作为键存储在具有 empty/null 值的 HashMap 中是个好主意吗？

Is it a good idea to store data as keys in HashMap with empty/null values?

java

arrays

performance

hashmap

asymptotic-complexity