Preface :
We are about to roll up our sleeves and go to work implementing the TreeMap class. Before we start, however, let us step back and examine the tasks and requirements. The TreeMap class implements the Map interface, which defines methods such as get(), put() and remove() that access and update elements in a map collection. The Map interface specifies the interface Map.Entry as an inner interface. Map.Entry defines the structure of key-value pairs that are inserted into a map. It also defines a restricted set of methods for access and update to a key-value pair. A programmer can use a MapEntry reference to access the key and value with the methods getKey() and getValue() and can update the value component using setValue(). No update to the key component is available since the operation could destroy the tree ordering of the map. This interface, like the OrderedSet interface, defines methods that return minimum and maximum elements. The method firstKey() returns the first (least) key in the ordered map, and the method lastKey() returns the last(greatest) key in the map. Besides all the methods specified by the interfaces, the TreeMap class provides a constructor and the method toString(), which creates a string that describes the elements in the map.The UML diagram in below figure provides a blueprint for the methods and inner actions that must be designed into the implementation of the TreeMap class :
The implementation of TreeMap builds a binary search tree. The nodes are Entry objects that contains a key-value pair and references to the left and right subtrees of the node as well as a reference to the parent of the node :
The similarity between an Entry node for a TreeMap object and an STNode for an STree object is apparent. The difference, of course, is that an Entry has a key-value pair for its "value" component. The Entry objects in the search tree are ordered by the key.
The class Entry is defined as a static inner class within the TreeMap class. It implements the Map.Entry interface. The class is designated as static because it makes no reference to any variables in the outer class TreeMap. All of the features of the Entry class are shown in the following declaration of the class, including a constructor and the method toString() that returns a representation of an interface in the form 'key=value' :
The TreeMap Class Design :
The TreeMap class builds a binary search tree of Entry objects. The private instance variable root is a reference to an Entry node that defines the search tree. Two integer variables mapSize and modCount maintain the size of the collection and the number of tree modification (insertions and deletions). The class constructor creates an empty map and toString() displays the entries as a comma-separated list of elements in braces "{" and "}". Each element has the form key=value. The other methods implement OrderedMap interface operations. The following is a skeletal declaration of the TreeMap class that includes an implementation of the constructor :
Key Access to an Entry :
Map methods such as get(), containsKey() and remove() use a key argument to access an entry in the map. We provide access with the private method getEntry(), which takes a key and searches the tree for a pair with the specified key. It returns a reference to the key-value pair in the tree or null of it failed to locate an entry with the key. The getEntry() method is the search engine that provides low-level access to the entry nodes based only on the key :
The method containsKey() indicates whether an entry with the specified key is in the map or not. Its implementation is a direct application of getEntry(). It simply returns true if the return reference is non-null and false otherwise :
Access to the value component of a key-value pair is provided by the method get(). After calling getEntry() to locate the entry, the method return null or the contents of the value field depending on whether the entry is in the map. The contents are accessed using the method getValue() :
Updating an Entry :
For a map, the put() operation with arguments for the key and the value serves a dual purpose. It adds a new entry or it updates the value filed for an existing entry. The algorithm is the binary search tree insertion algorithm. Start at the root and search down a path using search tree ordering. If a match occurs, then an entry with the specified key is already in the map. Simply use setValue() with the value argument to update the value field in the matching entry. Otherwise, the scan ends in an empty tree, which becomes the insertion location. Create an Entry object with the specified key and value arguments and add the new node :
Removing an Entry :
The implementation of remove() uses getEntry() to determine if there is a key-value pair in the map with specified key. If there is, the private method removeNode() takes a reference to the node and deletes it from the tree. The method removeNode() uses the deletion algorithm for binary search tree discussed in Section 18.3. With remove(), we have some housekeeping to do. The size of the map is decremented, modCount is incremented, and the value of the deleted node is the return value :
Complexity of Insertion and Deletion in TreeSet and TreeMap :
Because the TreeSet and TreeMap classes implement insertion and deletion using a binary search tree, the average running for these operations is O(log2n). However, a binary search tree can be degenerate, so the worst-case running time for these operations is O(n). We can guarantee uniform O(log2n) performance by using balanced trees such as red-black tree or a AVL tree instead of a normal binary search tree.
Supplement :
* Java Gossip : 內部類別（Inner class）
We are about to roll up our sleeves and go to work implementing the TreeMap class. Before we start, however, let us step back and examine the tasks and requirements. The TreeMap class implements the Map interface, which defines methods such as get(), put() and remove() that access and update elements in a map collection. The Map interface specifies the interface Map.Entry as an inner interface. Map.Entry defines the structure of key-value pairs that are inserted into a map. It also defines a restricted set of methods for access and update to a key-value pair. A programmer can use a MapEntry reference to access the key and value with the methods getKey() and getValue() and can update the value component using setValue(). No update to the key component is available since the operation could destroy the tree ordering of the map. This interface, like the OrderedSet interface, defines methods that return minimum and maximum elements. The method firstKey() returns the first (least) key in the ordered map, and the method lastKey() returns the last(greatest) key in the map. Besides all the methods specified by the interfaces, the TreeMap class provides a constructor and the method toString(), which creates a string that describes the elements in the map.The UML diagram in below figure provides a blueprint for the methods and inner actions that must be designed into the implementation of the TreeMap class :
The implementation of TreeMap builds a binary search tree. The nodes are Entry objects that contains a key-value pair and references to the left and right subtrees of the node as well as a reference to the parent of the node :
The similarity between an Entry node for a TreeMap object and an STNode for an STree object is apparent. The difference, of course, is that an Entry has a key-value pair for its "value" component. The Entry objects in the search tree are ordered by the key.
The class Entry is defined as a static inner class within the TreeMap class. It implements the Map.Entry interface. The class is designated as static because it makes no reference to any variables in the outer class TreeMap. All of the features of the Entry class are shown in the following declaration of the class, including a constructor and the method toString() that returns a representation of an interface in the form 'key=value' :
The TreeMap Class Design :
The TreeMap class builds a binary search tree of Entry objects. The private instance variable root is a reference to an Entry node that defines the search tree. Two integer variables mapSize and modCount maintain the size of the collection and the number of tree modification (insertions and deletions). The class constructor creates an empty map and toString() displays the entries as a comma-separated list of elements in braces "{" and "}". Each element has the form key=value. The other methods implement OrderedMap interface operations. The following is a skeletal declaration of the TreeMap class that includes an implementation of the constructor :
Key Access to an Entry :
Map methods such as get(), containsKey() and remove() use a key argument to access an entry in the map. We provide access with the private method getEntry(), which takes a key and searches the tree for a pair with the specified key. It returns a reference to the key-value pair in the tree or null of it failed to locate an entry with the key. The getEntry() method is the search engine that provides low-level access to the entry nodes based only on the key :
The method containsKey() indicates whether an entry with the specified key is in the map or not. Its implementation is a direct application of getEntry(). It simply returns true if the return reference is non-null and false otherwise :
Access to the value component of a key-value pair is provided by the method get(). After calling getEntry() to locate the entry, the method return null or the contents of the value field depending on whether the entry is in the map. The contents are accessed using the method getValue() :
Updating an Entry :
For a map, the put() operation with arguments for the key and the value serves a dual purpose. It adds a new entry or it updates the value filed for an existing entry. The algorithm is the binary search tree insertion algorithm. Start at the root and search down a path using search tree ordering. If a match occurs, then an entry with the specified key is already in the map. Simply use setValue() with the value argument to update the value field in the matching entry. Otherwise, the scan ends in an empty tree, which becomes the insertion location. Create an Entry object with the specified key and value arguments and add the new node :
Removing an Entry :
The implementation of remove() uses getEntry() to determine if there is a key-value pair in the map with specified key. If there is, the private method removeNode() takes a reference to the node and deletes it from the tree. The method removeNode() uses the deletion algorithm for binary search tree discussed in Section 18.3. With remove(), we have some housekeeping to do. The size of the map is decremented, modCount is incremented, and the value of the deleted node is the return value :
Complexity of Insertion and Deletion in TreeSet and TreeMap :
Because the TreeSet and TreeMap classes implement insertion and deletion using a binary search tree, the average running for these operations is O(log2n). However, a binary search tree can be degenerate, so the worst-case running time for these operations is O(n). We can guarantee uniform O(log2n) performance by using balanced trees such as red-black tree or a AVL tree instead of a normal binary search tree.
Supplement :
* Java Gossip : 內部類別（Inner class）
This message was edited 2 times. Last update was at 30/03/2011 10:24:05
沒有留言:
張貼留言