• Post Reply Bookmark Topic Watch Topic
  • New Topic

Creating buckets in a hash table  RSS feed

 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
When creating a hash table how do you set the number of buckets? Would it be using the second constructor of the hash table class HashTable(int size)? Also how would you turn a bucket into a linked list in order to handle collisions, coalesced hashing? I couldn't find much on Google so I figured I would ask here.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Charles, have you looked at the api for Hashtable? Here it is: http://docs.oracle.com/javase/7/docs/api/java/util/Hashtable.html. what does the int parameter to the constructor mean? You called it size but that is not what it really is. What does the api say about collisions?
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Luke wrote:Hi Charles, have you looked at the api for Hashtable? Here it is: http://docs.oracle.com/javase/7/docs/api/java/util/Hashtable.html. what does the int parameter to the constructor mean? You called it size but that is not what it really is. What does the api say about collisions?


Important lesson learned, I should report to the api documentation before asking questions. It is confirmed that the second constructor takes a parameter of int that clearly defines the number of buckets when the hash table is created but how do you create a linked list with a bucket?
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Charles Sexton wrote:Important lesson learned, I should report to the api documentation before asking questions. It is confirmed that the second constructor takes a parameter of int that clearly defines the number of buckets when the hash table is created but how do you create a linked list with a bucket?

The API says: "Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially." So each bucket, but its nature is configured to hold multiple objects, to deal with hash collisions. There is no documentation about how the collection of objects are stored, it is an implementation detail. As it happens, I have looked at the code for HashMap, and it uses a form of a linked list, so I would assume the Hashtable does the same. Do you specifically need to ensure a LinkedList, implementation independent and specifically?
 
Paul Clapham
Sheriff
Posts: 22831
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm confused about whether you're making a hash table (i.e. writing your own code) or making a Hashtable (i.e. using Oracle's java.util.Hashtable class). Could you clarify for us which it is? The answers for your questions are very different in the two cases.
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paul Clapham wrote:I'm confused about whether you're making a hash table (i.e. writing your own code) or making a Hashtable (i.e. using Oracle's java.util.Hashtable class). Could you clarify for us which it is? The answers for your questions are very different in the two cases.


I would like to use java.util.hash but if I have to then I will write my own.
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Luke wrote:
Charles Sexton wrote:Important lesson learned, I should report to the api documentation before asking questions. It is confirmed that the second constructor takes a parameter of int that clearly defines the number of buckets when the hash table is created but how do you create a linked list with a bucket?

The API says: "Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially." So each bucket, but its nature is configured to hold multiple objects, to deal with hash collisions. There is no documentation about how the collection of objects are stored, it is an implementation detail. As it happens, I have looked at the code for HashMap, and it uses a form of a linked list, so I would assume the Hashtable does the same. Do you specifically need to ensure a LinkedList, implementation independent and specifically?


Well I would like to try to use a linked list for each hash bucket to handle collisions, this process is called coalesced hashing or coalesced chaining. I couldn't find any Google searches on the subject being defined.
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is an example of a hash table using linked list but I was wanting something a little more simplistic and uses the java.util.hash class

 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So you specifically want to use the LinkedList class rather than the generic list that Hashtable uses for some reason? Then you have to write your own implementation in afraid. I have no idea why you want the specific LinkedList rather than what is given to you but that is your issue to deal with I guess. I would also suggest using a HashMap rather than Hashtable but I am not sure that is relevant. ..
 
Charles Sexton
Ranch Hand
Posts: 273
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve Luke wrote:So you specifically want to use the LinkedList class rather than the generic list that Hashtable uses for some reason? Then you have to write your own implementation in afraid. I have no idea why you want the specific LinkedList rather than what is given to you but that is your issue to deal with I guess. I would also suggest using a HashMap rather than Hashtable but I am not sure that is relevant. ..


Its a school assignment and hash tables are outdated and replaced by hash map nowadays.....
 
Paul Clapham
Sheriff
Posts: 22831
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, it's true that java.util.Hashtable was made obsolete in favour of java.util.HashMap many years ago, but I don't understand what that has to do with your assignment. If you're supposed to write your own code, then those two things are entirely irrelevant. And knowing how they are implemented internally is also irrelevant. Perhaps you could explain a bit more about this assignment?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!