aspose file tools*
The moose likes Beginning Java and the fly likes From scratch hash table implementation questions Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "From scratch hash table implementation questions" Watch "From scratch hash table implementation questions" New topic
Author

From scratch hash table implementation questions

Ken Austin
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

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!

dennis deems
Ranch Hand

Joined: Mar 12, 2011
Posts: 808
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
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

Ah, yes. That is more elegant, isn't it? Thank you for pointing that out, Dennis.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.)
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
Ken Austin
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

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
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

What would I do if they aren't equal? Throw an exception?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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.
Ken Austin
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

Is this what you meant?

Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
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?
Ken Austin
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

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
Ken Austin
Ranch Hand

Joined: Aug 20, 2012
Posts: 39

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.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
You're welcome.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: From scratch hash table implementation questions