• Post Reply Bookmark Topic Watch Topic
  • New Topic

Bucket Hash Table Issues  RSS feed

 
Andrew Linton Bradford
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello everyone,

I have been working on a small project for my Data Structures course and have run into quite a bit of trouble.

The assignment is to implement a bucket hash table structure without using Hashtable.  They basically want us to build it from scratch minus some choice Java classes like String, ArrayList, etc.

Here is my current attempt:

Main Class:


Hash Table Class:


Link/Node Class:


My main focus is simply getting the addNode() method to "work", then I want to try and work the rest out from there.

There might be some severe fundamental issues here.  Any advice would be appreciated.

Also, does anyone have any advice/techniques for keeping track of object references?  Trying to construct a linked list has proven to be painful for me.  I have spent a great deal of time trying to construct methods to help me find out what is going on.

Sincerely,
Andrew

 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

On line 27 you know that list[hash] is populated, it also may have its next reference set. You need to extend the linked list without clobbering any existing links.
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andrew Linton Bradford wrote:. . . implement a bucket hash table structure without using Hashtable.
Did they really mention Hashtable? They are behind the times. Nobody uses that class any more; they use HashMap instead.
They basically want us to build it from scratch . . .
Yes, algorithms course people like making you build things from scratch (Mwaahaahaahaahaahaahaahaahaahaa!) because it proves you have understood the structure. In twenty years you will still remember how to create a hash table and will understand what has gone wrong with your latest hash table‑using app.
 
Andrew Linton Bradford
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On line 27 you know that list[hash] is populated, it also may have its next reference set. You need to extend the linked list without clobbering any existing links.


Oops!  I am tinkering around with a new else statement.


Did they really mention Hashtable? They are behind the times. Nobody uses that class any more; they use HashMap instead.


Hashtable was the first one to come to mind.

 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

 
Andrew Linton Bradford
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you, Carey. 

I can see the path of references after mulling over it a few times.
 
Carey Brown
Saloon Keeper
Posts: 3310
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Glad to help.
 
Piet Souris
Master Rancher
Posts: 2041
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are you supposed to implement a Hashtable or a HashSet?
 
Andrew Linton Bradford
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Several weeks later and I am still trying.

At the very least, the Hash Table compiles and does what it is supposed to do, for the most part.  The first major problem I see right now is the amount of print statement clutter due to calling lookup() from inside remove().  Secondly, the lookup() method seems to be being called twice when called from inside remove() and I don't really understand why.

Hash Table Class:


Node Class:



Test Class:



I've had yet another mostly fruitless night of staring at the screen and tinkering.  Please share any suggestions/tips you might have to improve this. 

Thank you,
Andrew
 
Paul Clapham
Sheriff
Posts: 22819
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If your "remove()" method is the one called "delete" in the code you posted, then it calls lookup() at line 38 and then (possibly) again at line 40.
 
Paul Clapham
Sheriff
Posts: 22819
43
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And inside your lookup() method, you frequently use the == operator to compare the contents of two String objects. However the == operator only compares to see if the two String objects are the same object. It's possible for two different String objects to have the same contents, and to test for that, use the equals() method of the String class.
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Are your node objects immutable? If not, then they may change their hash code from time to time, after which they may become impossible to find.
Why are you using 13 buckets? Many hash table implementations use an exact power of 2, so you can escape the clutches of the remainder operator. If h means hash code and c means capacity of the buckets array, I shall let yo work out what the two advantages of
h & c - 1
over
h % c
are. If you use binary arithmetic, that trick only works well if c is an exact power of 2.
Why are you using bytes for the hash code? Why are you hard‑coding the % operator in the hash code method? Why are you using toLowerCase()?
 
shivkumar singh
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It Is basically used to store key value pairs. Using Has Table is not more difficult, It is good Data Structure for finding any value directory.But the problem is that Bucket Hash Table does not store more data. It is old method of using Bucket Hash Table .
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
shivkumar singh wrote:. . . It is old method of using Bucket Hash Table .
It is easier to implement as an assignment in a data structures course, however.
 
Andrew Linton Bradford
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for all the replies.  I am going to take some time to read through the posts and try to answer some of your questions.

Andrew
 
Andrew Linton Bradford
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If your "remove()" method is the one called "delete" in the code you posted, then it calls lookup() at line 38 and then (possibly) again at line 40.


Oh, I was apparently staring at the screen too long. haha I was checking if it was null before assigning it, but would it be better to remove that and just use some sort of exception handler?  Instead of double-printing the lookup() method?

And inside your lookup() method...


Should I be checking for both == and equals() in the if() parameter list?

Why are you using 13 buckets?


It was listed as a requirement in the assignment.

Why are you using bytes for the hash code?


It was my attempt at quickly converting the String to a numerical value.  Any suggestions?

Why are you hard‑coding the % operator in the hash code method?...


I was forcing the value to fit within one of the 13 buckets.

Why are you using toLowerCase()?


I don't remember why I did that.  It might have been something I have just neglected to change.  I removed it.

Welcome to the Ranch 


Thank you!

I will continue working and see if I can implement some of these suggestions,
Andrew


 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Andrew Linton Bradford wrote:. . .Should I be checking for both == and equals() in the if() parameter list?
No. I can't remember what the parameters are, but you should avoid ==. Good summary here.
. . .
Why are you using bytes for the hash code?
It was my attempt at quickly converting the String to a numerical value.  Any suggestions?
Use ints just as you would for any other arithmetic. Presumably you have to calculate a hash code yourself rather than using the method already existing in String. You know you can get the chars out of a String as an array: iterate that array and add each char and multiply each intermediate sum by 31. That will actually give the same result as String#hashCode(). I presume your assignment will permit that technique?
Why are you hard‑coding the % operator in the hash code method?...
I was forcing the value to fit within one of the 13 buckets.
Breach of the single responsibility principle. The object calculates its hash code; the hash table wants the remainder after division by 13. It is therefore the hash table's responsibility to work out that remainder. Otherwise you will create hash codes which work beautifully for thirteen buckets but won't work at all well when confronted with the more common counts of sixteen/32/64/etc buckets.
And beware: some of your hash codes will be negative, in which case h % 13 will also be negative.
. . .
Welcome to the Ranch 
Thank you! . . .
That's a pleasure
 
Campbell Ritchie
Marshal
Posts: 56525
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A few minutes ago, I wrote:. . . you should avoid ==. Good summary here. . . .
The link lists the situations when you do actually use ==.
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!