Win a copy of Learn Spring Security (video course) this week in the Spring forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

From scratch hash table implementation questions

 
Ken Austin
Ranch Hand
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 808
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah, yes. That is more elegant, isn't it? Thank you for pointing that out, Dennis.
 
Mike Simmons
Ranch Hand
Posts: 3028
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3028
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What would I do if they aren't equal? Throw an exception?
 
Mike Simmons
Ranch Hand
Posts: 3028
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3028
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Is this what you meant?

 
Mike Simmons
Ranch Hand
Posts: 3028
10
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 39
Chrome Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3028
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic