程式扎記: [ Data Structures with Java ] Section 21.7 : An Unordered Set Collection (HashSet)

標籤

2011年4月11日 星期一

[ Data Structures with Java ] Section 21.7 : An Unordered Set Collection (HashSet)


Preface :
HashSet completes our discussion of set and map classes. We introduce a new design strategy that implements HashSet using a HashMap object andcomposition. Using a map to implement a set makes sense. Each collection type stores elements by value. In the case of a map, elements are entry pairs identified by their key. You can view elements in a set as being only keys without an associated value component. A set of elements in the HashSet collection corresponds to a set of keys in the map. The value component of a map entry is not used but we must account for its presence in the entry.
The HashSet class uses a HashMap by composition (object composition is a way to combine simple objects or data types into more complex ones). The class defines a static Object reference called PRESENT. This becomes the value component for each entry in the map. The constant reference serves as a dummy placeholder in an entry pair. Declare a private instance variable map of type HashMap having T as the type of the set elements and Object as the value type. The constructor instantiates the map collection. This has the effect of creating an empty set.
- HashSet class partly implementation :
  1. public class HashSet implements Set{  
  2.     private static final Object PRESENT = new Object();  
  3.     private HashMap map;  
  4.       
  5.     public HashSet(){  
  6.         map = new HashMap();  
  7.     }  
  8. ...  
  9. }  

Implementing HashSet with HashMap Methods :
HashSet access and update methods take a single reference argument item. The set methods are implemented with map methods that use the entry as the argument. For instance, here is the implementation for the HashSet add() method. The corresponding map method put() inserts a new element in the map or updates the value component if the elements is already present. In HashSet, we are interested in using put() to insert a new element if a duplicate is not already present :

- Method add() in class HashSet :
  1. ...  
  2.     @Override  
  3.     public boolean add(T e) {  
  4.         return map.put(e, PRESENT)==null;  
  5.     }  
  6. ...  

The HashSet iterator must raverse the keys in the map. Implement the method iterator() by returning an iterator for the key set collection view of the map :
- Method iterator() in class HashSet :
  1. ...  
  2. public Iterator iterator() {  
  3.     return map.keySet().Iterator();  
  4. }  
  5. ...  

As a final example, the HashSet remove() methods calls the remove() method for the map. Recall that the map remove() method returns the value field in the key-value pair that was erased from the map or null if the key is not in the map. To determine whether an element was removed from the set, verify that the return value from the map remove() call is the reference PRESENT :
- Method remove() in class HashSet :
  1. ...  
  2.     @Override  
  3.     public boolean remove(Object o) {  
  4.         return map.remove(o) == PRESENT;  
  5.     }  
  6. ...  

Supplement :
[ Data Structures with Java ] Section 21.6 : An Unordered Map Collection

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!