數據結構只保存鍵（不關心值）

我需要存儲一個字符串列表，並且需要檢查列表中是否存在字符串。數據結構只保存鍵（不關心值）

我通常只會使用一些地圖用鑰匙和布爾...即

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

數據結構只保存鍵（不關心值）

回答

相關問題