我最初编写了一个 ArrayList
并在其中存储了唯一值(用户名,即 Strings
)。后来我需要使用 ArrayList
来搜索其中是否存在用户。那是 O(n)
的搜索。
我的技术主管希望我将其更改为 HashMap
,并将用户名作为键存储在数组中,将值存储为空 Strings
。
所以,在 Java 中 -
hashmap.put("johndoe","");
我可以稍后通过运行查看此用户是否存在 -
hashmap.containsKey("johndoe");
这是 O(1)
对吧?
我的负责人说这是一种更有效的方法,这对我来说很有意义,但将 null/empty 作为值放在 hashmap 中并将元素作为键存储在其中似乎有点不对劲。
我的问题是,这是一个好方法吗?效率胜过 ArrayList#contains
或一般的数组搜索。有用。
我担心的是,我没有看到其他人在搜索后这样做。我可能在某处遗漏了一个明显的问题,但我看不到它。
最佳答案
由于您有一组唯一值,因此 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 更自然。
关于java - 将数据存储为具有空/空值的 HashMap 中的键是一个好主意吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38691454/