只保存密钥的数据结构(不关心价值)

Question

我需要存储一个字符串列表,并需要检查列表中是否存在字符串.

我通常会使用一些带有键和布尔值的Map ...即

HashMap map<String,Boolean> = new HashMap<String,Boolean)()

而且只是做一个 map.contains(string)

这是我过去总是进行这种查找的方式,因为我知道使用地图将是O(1)访问.

我知道这可能是挑剔和不重要的,但我只是好奇是否有一些结构可以保存那个布尔值.只是看起来浪费内存,因为我不关心错误值,因为如果密钥不存在等于false.

我想也许指着一个关键字null来做我想要的,但我想知道是否有一些数据结构有点做到这一点.

Answer 1

这就是该Set<T>系列的用途.该HashSet<T>实施是O(1),并在内部做了你提出正是:这是一个HashMap<T,V>在那里每个键的值是相同的内部对象实例.也就是说,源包含

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

并且每个条目的值都设置为PRESENT.