我最初写了一个,ArrayList
并在其中存储了唯一的值(用户名,即Strings
)。稍后,我需要使用ArrayList
来搜索其中是否存在用户。那是O(n)
为了搜索。
我的技术负责人希望我将其更改为a HashMap
,并将用户名存储为数组中的键,并将值存储为空Strings
。
因此,在Java中-
hashmap.put("johndoe","");
我可以稍后运行以查看该用户是否存在-
hashmap.containsKey("johndoe");
是这样O(1)
吗
我的负责人说,这是一种更有效的方法,这对我来说很有意义,但是将null / empty作为哈希表中的值并将其中的元素存储为键似乎有点过时。
我的问题是,这是一个好方法吗?效率通常优于ArrayList#contains
数组搜索。有用。我担心的是,搜索后我没有看到其他人这样做。我可能在某处缺少明显的问题,但看不到。
由于您具有一组唯一值,因此aSet
是适当的数据结构。您可以将值放在接口HashSet
的实现内Set
。
我的负责人说,这是一种更有效的方法,这对我来说很有意义,但是将null / empty作为哈希表中的值并将其中的元素存储为键似乎有点过时。
线索的建议是有缺陷的。Map
不是正确的抽象,Set
是。AMap
适用于键值对。但是您没有值,只有键。
用法示例:
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
使用aMap
会很尴尬,因为值的类型应该是什么?这个问题在您的用例中毫无意义,因为您只有键,而不是键值对。使用Set
,您不需要问,用法是很自然的。
这是O(1)对吗?
是的,在aHashMap
或a中搜索HashSet
是O(1)摊销最差情况,而在aList
或数组中搜索是O(n)最坏情况。
一些评论指出aHashSet
是根据来实现的HashMap
。在那种抽象水平上很好。在即将完成的任务的抽象级别上---存储唯一的用户名的集合,使用集合是自然的选择,比地图更自然。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句