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

Question

我最初写了一个ArrayList并存储了唯一值(用户名,即Strings).我后来需要使用它ArrayList来搜索用户是否存在.这是O(n)为了搜索.

我的技术负责人希望我将其更改为a HashMap并将用户名存储为数组中的键,并将值存储为空Strings.

所以,在Java中 -

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

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

hashmap.containsKey("johndoe"); 

这是O(1)对的？

我的主管说这是一种更有效的方法来实现这一点,这对我来说很有意义,但是将hash/empty作为值放在hashmap中并将其中的元素作为键存放似乎有点过时了.

我的问题是,这是一个好方法吗？效率节拍ArrayList#contains或一般的阵列搜索.有用.我担心的是,我没有看到其他人在搜索后这样做.我可能在某个地方错过了一个明显的问题,但我看不到它.

Answer 1

由于您有一组唯一值,因此a Set是适当的数据结构.您可以将值放在内部HashSet,即Set接口的实现.

我的主管说这是一种更有效的方法来实现这一点,这对我来说很有意义,但是将hash/empty作为值放在hashmap中并将其中的元素作为键存放似乎有点过时了.

领导的建议是有缺陷的.Map对此不是正确的抽象,Set是.A 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

使用a Map会很尴尬,因为值应该是什么类型？这个问题在你的用例中毫无意义,因为你只有键,而不是键值对.使用a Set,你不需要问,使用是完全自然的.

这是O(1)对吗？

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

一些评论指出a HashSet是以实施方式实施的HashMap.这很好,在那个抽象层面.在手头任务的抽象层面---存储一组独特的用户名,使用集合是一种自然的选择,比地图更自然.

Answer 2

这基本上是如何HashSet实现的,所以我想你可以说这是一个很好的方法.您也可以使用HashSet而不是HashMap使用空值.

例如 :

HashSet的实施add是

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

map支持在哪里HashMap,PRESENT是虚拟值.

我担心的是,我没有看到其他人在搜索后这样做.我可能在某个地方错过了一个明显的问题,但我看不到它.

正如我所提到的,JDK的开发人员正在使用相同的方法.