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.
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 :
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 :
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 :
Supplement :
* [ Data Structures with Java ] Section 21.6 : An Unordered Map Collection
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.
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
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 :
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 :
Supplement :
* [ Data Structures with Java ] Section 21.6 : An Unordered Map Collection
沒有留言:
張貼留言