Granny's Programming Pearls
"inside of every large program is a small program struggling to get out"
JavaRanch.com/granny.jsp
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Jeanne Boyarsky
  • Tim Cooke
Sheriffs:
  • Knute Snortum
  • Junilu Lacar
  • Devaka Cooray
Saloon Keepers:
  • Ganesh Patekar
  • Tim Moores
  • Carey Brown
  • Stephan van Hulst
  • salvin francis
Bartenders:
  • Ron McLeod
  • Frits Walraven
  • Pete Letkeman

Bucket Hash Table Issues  RSS feed

 
Greenhorn
Posts: 17
  • 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

 
Saloon Keeper
Posts: 4999
54
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.
 
Marshal
Posts: 60816
190
  • 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: 17
  • 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: 4999
54
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: 17
  • 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: 4999
54
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
 
Master Rancher
Posts: 2918
100
  • 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: 17
  • 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
 
Sheriff
Posts: 23714
50
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: 23714
50
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: 60816
190
  • 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()?
 
Greenhorn
Posts: 7
  • 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: 60816
190
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch
 
Campbell Ritchie
Marshal
Posts: 60816
190
  • 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: 17
  • 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: 17
  • 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: 60816
190
  • 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: 60816
190
  • 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 ==.
 
Andrew Linton Bradford
Greenhorn
Posts: 17
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell,

Sorry for the taking so long to reply.  I have been trying to work my way through the 2nd part of the project: binary search tree.  I will probably be creating a post about that soon.

I removed all instances of == in my code, except for my comparisons to null.

I replaced the hashCode() method with:



Thanks again,
Andrew
 
Campbell Ritchie
Marshal
Posts: 60816
190
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Andrew Linton Bradford wrote:Campbell,

Sorry for the taking so long to reply.  . . .

That's all right.

I removed all instances of == in my code, except for my comparisons to null. . . . .

Good; that sounds correct.

I replaced the hashCode() method with: . . . Thanks again,
Andrew

That's a pleasure

If you add
hash *= 31;
in your loop, you will get a hash code similar to what you get from String#hashCode(). I presume you have considered the possibility that you will suffer an overflow error and get a negative hash code. Have you considered an abs() method to deal with such negative numbers?
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!