Forums Register Login

From scratch hash table implementation questions

+Pie Number of slices to send: Send
Greetings, Java friends...

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?

Thanks!

1
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
Ah, yes. That is more elegant, isn't it? Thank you for pointing that out, Dennis.
1
+Pie Number of slices to send: Send
 

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.)
+Pie Number of slices to send: Send
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.
+Pie Number of slices to send: Send
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.)
+Pie Number of slices to send: Send
What would I do if they aren't equal? Throw an exception?
+Pie Number of slices to send: Send
Well, there can be more than one key in the linked list, right? Check the other keys. Is one of them equal?

If none are equal, that would mean the key is not in the map - same as if keys[k] were null. Do you throw an exception when a key is not present?
+Pie Number of slices to send: Send
 

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.
+Pie Number of slices to send: Send
Is this what you meant?

1
+Pie Number of slices to send: Send
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?
+Pie Number of slices to send: Send
I see what you're saying.

If I enter

"FB" and "one"

and

"Ea" and "two"

the output from my test program is:

FB one two
+Pie Number of slices to send: Send
Okay, I'm going to go back and rewrite it with both the key and the value in the nodes. Thanks for all your help, Mike.
+Pie Number of slices to send: Send
You're welcome.
Get meta with me! What pursues us is our own obsessions! But not this tiny ad:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com


reply
reply
This thread has been viewed 4805 times.
Similar Threads
Need help outputting to a text file...
getting the int value
Binary search tree questions...
Implementing a Hash Table
How to retrieve reqd. tag values
More...

All times above are in ranch (not your local) time.
The current ranch time is
Mar 28, 2024 15:16:27.