数据结构只保存键（不关心值）

我需要存储一个字符串列表，并且需要检查列表中是否存在字符串。数据结构只保存键（不关心值）

我通常只会使用一些地图用钥匙和布尔...即

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

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

这是那种我一直做这几样查找的方式在过去，因为我知道使用地图将是O（1）访问。

我知道这可能是挑剔和不重要的，但我只是好奇，如果有一些结构是在那里，将保存该布尔值。只是看起来像浪费了内存，因为我不在乎虚假的价值，因为如果钥匙不存在就等于虚假。

我在想也许指向一个关键字null会做我想做的，但我想知道是否有某种数据结构这样做。

来源

2012-03-02 K2xL

这是Set<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。

来源

2012-03-02 21:17:30

有趣，所以假设性能会更快通过使用散列表空值？ – K2xL 2012-03-02 21:21:46

@ K2xL为什么使用空值映射使用空值映射？ – NominSim 2012-03-02 21:43:45

这不是一个HashMap 其中的值为null。值是Object。 – chicout 2012-03-02 21:53:48

HashSet（或）其他Set接口实现可能会帮助您找到所需的功能。

来源

2012-03-02 21:18:18 kosa

-1

为什么不使用通常的ArrayList<String>它具有包含方法和其他一切......

来源

2012-03-02 21:18:18

这会使列表中的关键字增加很长时间 – K2xL 2012-03-02 21:18:59

@ K2xL - 否，向（未排序的）列表添加O（1），但包含操作为O（n）。 – 2012-03-02 21:22:07

@Andreas_D正确 – 2012-03-02 21:55:48

也许HashSet<E>？或者实际上，任何实现Set<E>的东西，尽管它们并不都具有O（1）期望的查找。

来源

2012-03-02 21:18:24

您应该使用HashSet<E> - “数据结构只保存键（不关心值）”。它的实现基于HashMap<K,V>，其中每个元素都是一个值，而键只是Object，正是你所需要的。

public class HashSet<E> ... { 
    ... 
    private transient HashMap<E,Object> map; 

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

    public HashSet() { 
     map = new HashMap<E,Object>(); 
    } 
    ... 

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

    ... 
}

来源

2012-03-02 21:27:06 chicout

数据结构只保存键（不关心值）

回答

相关问题