wood burning stoves 2.0*
The moose likes Java in General and the fly likes Implementing a Hash Table Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Implementing a Hash Table " Watch "Implementing a Hash Table " New topic
Author

Implementing a Hash Table

John Molloy
Greenhorn

Joined: Apr 26, 2009
Posts: 7
Alright so we have to implement a basic hash table for an assignment. It seems so simple but it's kicking my ass.
Basically what we have is an input file that contains the amount of entries on the first line and a dns record on each subsequent line.
So we are meant to make 3 classes: DNSKey, Record and HashTable.
These are the outlines they've given us



I have been trying to use an array of DNSKey's which are placed into a position decided by the hash function. I am however unsure if I even need an array of DNSKey's or if they should be hashed. So I'm basically wondering how I would map those DNSKey's to a record and placing that record
into the hashtable, while keeping track of the duplicates. The rest of the code basically follows the specification although I am a little unsure on how I would go about the HashTable class.

Here is the code I'm using to do what I explained:



And HashTable class



At the end I basically have to output the DNS key that occured the most and the amount of times it occured.

Thanks a ton if anyone can help/\.
Jelle Klap
Bartender

Joined: Mar 10, 2008
Posts: 1756
    
    7

John Molloy wrote:
I have been trying to use an array of DNSKey's which are placed into a position decided by the hash function. I am however unsure if I even need an array of DNSKey's or if they should be hashed. So I'm basically wondering how I would map those DNSKey's to a record and placing that record
into the hashtable, while keeping track of the duplicates. The rest of the code basically follows the specification although I am a little unsure on how I would go about the HashTable class.


Maintaining an array to store the elements in your HashTable class would be good choice. Alternatively you could use a Collection that implements the RandomAccess interface, of which ArrayList would be most suitable. I'd go for an array, though. A general purpose HashTable would likely use an inner class that represents an entry in the HashTable that wraps both the key and the value, however, if all you're going to store are Record objects that does not seem necessary as: "For this assignment key is simply stored in the Record". So your HashTable can simply maintain an array of Record objects, right? Well, if you could be absolutely sure that the hashing algorithm would always return a unique value, then yes, however the algorithm description is as follows: "use the sum of ASCII values for all characters in domain_name and source_address. Caller must reduce h modulo the hash table size". So there's quite a good chance of duplicate hash code's for different values. Such an occurence is called a "collision". That means keeping track of an array of Record objects directly is not good enough, as a Record in the array would be overwriten by adding another Record wo's key happens to hash to the same index position, but which is otherwise unequal. One of the simplest conceptual ways to deal with this problem would be to maintain an array of an array of Record objects. That way a key's hash value would always represent an array of Record objects, which means you could keep track of more than one Record for a given hash value. That nested array would represent what's known as a "bucket". However, implementing a bucket using an array is not really ideal, because an array's size is not dynamic. A linked list would probably be more efficient bucket implementation. See if you can work out a solution like this.

Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Implementing a Hash Table
 
Similar Threads
JTable, Table Models, Vectors & Objects : Confused
Hashtable
How do I get selected rows that have a check against them using check boxes in a table
better way?
Invisible JTable Column Header!