Professional C__ - Marc Gregoire [45]
hash.enter(14534, "Kleper, Scott");
KEYS VALUES
14534 “Kleper, Scott” [string]
hash.enter(14534, "Kleper, Marni");
KEYS VALUES
14534 “Kleper, Marni” [string]
It’s not difficult to imagine uses for a data structure that’s like a hash table, but allows multiple values for a given key. In the insurance example, a family might have several names that correspond to the same ID. Because such a data structure is very similar to a hash table, it would be nice to leverage that functionality somehow. A hash table can have only a single value as a key, but that value can be anything. Instead of a string, the value could be a collection (such as an array or a list) containing the multiple values for the key. Every time you add a new member for an existing ID, add the name to the collection. This would work as shown in the following sequence.
Collection collection; // Make a new collection.
collection.insert("Kleper, Scott"); // Add a new element to the collection.
hash.enter(14534, collection); // Enter the collection into the table.
KEYS VALUES
14534 {“Kleper, Scott”} [collection]
Collection collection = hash.get(14534);// Retrieve the existing collection.
collection.insert("Kleper, Marni"); // Add a new element to the collection.
hash.enter(14534, collection); // Replace the collection with the updated one.
KEYS VALUES
14534 {“Kleper, Scott”, “Kleper, Marni”} [collection]
Messing around with a collection instead of a string is tedious and requires a lot of repetitive code. It would be preferable to wrap up this multiple-value functionality in a separate class, perhaps called a MultiHash. The MultiHash class would work just like Hashtable except that behind the scenes, it would store each value as a collection of strings instead of a single string. Clearly, MultiHash is somehow related to Hashtable because it is still using a hash table to store the data. What is unclear is whether that constitutes an is-a or a has-a relationship.
To start with the is-a relationship, imagine that MultiHash is a subclass of Hashtable. It would have to override the behavior that adds an entry into the table so that it would either create a collection and add the new element or retrieve the existing collection and add the new element. It would also override the behavior that retrieves a value. It could, for example, append all the values for a given key together into one string. This seems like a perfectly reasonable design. Even though it overrides all the behaviors of the superclass, it will still make use of the superclass’s behaviors by using the original behaviors within the subclass. This approach is shown in Figure 3-5.
FIGURE 3-5
Now consider it as a has-a relationship. MultiHash is its own class, but it contains a Hashtable object. It probably has an interface very similar to Hashtable, but it need not be the same. Behind the scenes, when a user adds something to the MultiHash, it is really wrapped in a collection and put in a Hashtable object. This also seems perfectly reasonable and is shown in Figure 3-6.
FIGURE 3-6
So, which solution is right? There’s no clear answer, though one of the authors, who has written a MultiHash class for production use, viewed it as a has-a relationship. The main reason was to allow modifications to the exposed interface without worrying about maintaining hash table functionality. For example, in Figure 3-6, the get behavior was changed to getAll, making it clear that this would get all the values for a particular key in a MultiHash. Additionally, with a has-a relationship, you don’t have to worry about any hash table functionality bleeding through. For example, if the