The exercise in the textbook I'm working through was to implement a hash table from scratch. My version works, but it was different enough from the solution in the text, that I was eager for some other eyes to look over my code. The author used an array of Nodes that contained both the key and the value.
In addition to any general comments you might have, here are my specific questions...
1. stylecheck says of line 56: "Conditional logic can be removed." What does that mean?
2. stylecheck says that the variables inside my private nested class "must be private and must have accessor methods." Is it not enough to just make the class itself private?
Ken Austin wrote:
1. stylecheck says of line 56: "Conditional logic can be removed." What does that mean?
I think it's telling you that the code in lines 56-59 can be replaced with which is leaner and more elegant. Your code evaluates a boolean expression and then uses the resulting value as a condition to decide which boolean to return.
Ken Austin wrote:2. stylecheck says that the variables inside my private nested class "must be private and must have accessor methods." Is it not enough to just make the class itself private?
In my opinion, yes that's enough. But others may disagree. In Java, we're used to seeing pointlessly verbose classes, with private fields and public accessors. Any deviation from this is seen as suspect. But really, it's completely pointless for a private member class - it's already completely accessible from anywhere within the same top-level class, and nowhere else. So I would advise ignoring this particular stylecheck warning, or even disabling it. (Ideally, it should be disabled for private nested classes, and optionally enabled otherwise - if that's possible.)
It looks like your put() method puts entries in a linked list if there's more than one in a given bucket, as one would expect with a hash table. However your get() and containsKey() do not check any other entries in the linked list, they just check for an entry, and assume it's the right one. That seems wrong to me. For each key with the same hash, they need to check if the key is really equal (using the .equals() method) or not.
Also, is there any need to have an array of keys, and have the keys in the array of Nodes? Seems like you need one or the other, but not both. If you get rid of the array of keys, the remaining array can still do everything you need.
I am not storing the keys in the array of nodes. Just the values.
But the author's solution stored both the keys and the values in the value objects and just used one array, as you are suggesting would work better here.
I can add those equals() methods easily enough. (I think.)
Ken Austin wrote:I am not storing the keys in the array of nodes. Just the values.
Ah, I looked too quickly. That's a problem. In principle, it's possible for two different objects, not equal, to have the same hash code. And even with different hash codes, it's possible that % ARRAY_SIZE will return the same value for two or more different objects. Thus, you need the ability to store multiple keys with the same hashcode (or hashcode % ARRAY_SIZE) in the hash table. That's why you want the keys in the nodes, so you can have multiple keys and the values they go with.
That's better, yes. However, you still need to be able to support different keys with the same hash. For example, try putting "FB" as one key, and "Ea" as another. They happen to have the same hash. Can you get() the two different values associated with those two different keys?