Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Hash Table

ippaccianiippacciani Posts: 2Member
Hello,

I'm an Italian student and I'm new on this site.

I have to implement in Java the Map abstract data type with separate chaining collison handlin without using java.util classes.

Is there anyone who could help me please?Because I've some doubts.

Thanks in advance,

Giorgio Vezzaro

Comments

  • zibadianzibadian Posts: 6,349Member
    : Hello,
    :
    : I'm an Italian student and I'm new on this site.
    :
    : I have to implement in Java the Map abstract data type with separate
    : chaining collison handlin without using java.util classes.
    :
    : Is there anyone who could help me please?Because I've some doubts.
    :
    : Thanks in advance,
    :
    : Giorgio Vezzaro
    :
    I would first start with a single bucket to handle the collisions. The most basic bucket is a class with 2 fields: the key and an array of the objects with the same key.
    Once you have that implemented and working correctly, then start with the map itself. The map can be a simple array of buckets, or it can be implemented as a balanced binary tree. I would suggest the array, since that is the easiest to code and works good enough for most applications.

    Adding an element to the map is a two step algorithm:
    1) find the correct bucket, creating it if necessary
    2) pass the element to that bucket for adding

    Retrieving an element is also a two step algorithm:
    1) find the correct bucket, return null (throw error) if none can be found
    2) pass the search value to the bucket, return null (throw error) if element cannot be found

    Iterating through all the keys of the map is simply iterating through the bucket-array and retrieving the stored key for each bucket.
    Iterating through all the values of the map is again a two step algorithm: iterate across each bucket and for each bucket iterate through each element.

    You can implement nearly all methods in the Map interface with these few algorithms.

    Note: you should really ask your teacher if you can use some of the collections framework classes as return values for your Set and Collection implementations.
  • ippaccianiippacciani Posts: 2Member
    : : Hello,
    : :
    : : I'm an Italian student and I'm new on this site.
    : :
    : : I have to implement in Java the Map abstract data type with separate
    : : chaining collison handlin without using java.util classes.
    : :
    : : Is there anyone who could help me please?Because I've some doubts.
    : :
    : : Thanks in advance,
    : :
    : : Giorgio Vezzaro
    : :
    : I would first start with a single bucket to handle the collisions.
    : The most basic bucket is a class with 2 fields: the key and an array
    : of the objects with the same key.
    : Once you have that implemented and working correctly, then start
    : with the map itself. The map can be a simple array of buckets, or it
    : can be implemented as a balanced binary tree. I would suggest the
    : array, since that is the easiest to code and works good enough for
    : most applications.
    :
    : Adding an element to the map is a two step algorithm:
    : 1) find the correct bucket, creating it if necessary
    : 2) pass the element to that bucket for adding
    :
    : Retrieving an element is also a two step algorithm:
    : 1) find the correct bucket, return null (throw error) if none can be
    : found
    : 2) pass the search value to the bucket, return null (throw error) if
    : element cannot be found
    :
    : Iterating through all the keys of the map is simply iterating
    : through the bucket-array and retrieving the stored key for each
    : bucket.
    : Iterating through all the values of the map is again a two step
    : algorithm: iterate across each bucket and for each bucket iterate
    : through each element.
    :
    : You can implement nearly all methods in the Map interface with these
    : few algorithms.
    :
    : Note: you should really ask your teacher if you can use some of the
    : collections framework classes as return values for your Set and
    : Collection implementations.


    Thanks a lot for your useful clarifications:it's very kind from you.
    I've understood all you've said,including adding and retrieving elements.
    I agree with you that the array is better and easier than the tree.
    However there's a little difference beteween your explanation and my teacher's request:he wants the bucket developped with a list not with an array.The map that he would is an array in which each element is the head of the list.What do you think about?
    Could you suggest me something please, including an hash function and a method that return an iterable collection of the list?

    Thanks in advance,

    Giorgio






  • zibadianzibadian Posts: 6,349Member
    : : : Hello,
    : : :
    : : : I'm an Italian student and I'm new on this site.
    : : :
    : : : I have to implement in Java the Map abstract data type with separate
    : : : chaining collison handlin without using java.util classes.
    : : :
    : : : Is there anyone who could help me please?Because I've some doubts.
    : : :
    : : : Thanks in advance,
    : : :
    : : : Giorgio Vezzaro
    : : :
    : : I would first start with a single bucket to handle the collisions.
    : : The most basic bucket is a class with 2 fields: the key and an array
    : : of the objects with the same key.
    : : Once you have that implemented and working correctly, then start
    : : with the map itself. The map can be a simple array of buckets, or it
    : : can be implemented as a balanced binary tree. I would suggest the
    : : array, since that is the easiest to code and works good enough for
    : : most applications.
    : :
    : : Adding an element to the map is a two step algorithm:
    : : 1) find the correct bucket, creating it if necessary
    : : 2) pass the element to that bucket for adding
    : :
    : : Retrieving an element is also a two step algorithm:
    : : 1) find the correct bucket, return null (throw error) if none can be
    : : found
    : : 2) pass the search value to the bucket, return null (throw error) if
    : : element cannot be found
    : :
    : : Iterating through all the keys of the map is simply iterating
    : : through the bucket-array and retrieving the stored key for each
    : : bucket.
    : : Iterating through all the values of the map is again a two step
    : : algorithm: iterate across each bucket and for each bucket iterate
    : : through each element.
    : :
    : : You can implement nearly all methods in the Map interface with these
    : : few algorithms.
    : :
    : : Note: you should really ask your teacher if you can use some of the
    : : collections framework classes as return values for your Set and
    : : Collection implementations.
    :
    :
    : Thanks a lot for your useful clarifications:it's very kind from you.
    : I've understood all you've said,including adding and retrieving
    : elements.
    : I agree with you that the array is better and easier than the tree.
    : However there's a little difference beteween your explanation and my
    : teacher's request:he wants the bucket developped with a list not
    : with an array.The map that he would is an array in which each
    : element is the head of the list.What do you think about?
    : Could you suggest me something please, including an hash function
    : and a method that return an iterable collection of the list?
    :
    : Thanks in advance,
    :
    : Giorgio
    :
    :
    :
    :
    :
    :
    :
    A linked list is also quite simple: create a new class to become a bucket element. It should have at least 2 fields: the value itself and the next bucket element.

    Retrieving an element from a bucket changes from a for-loop to a while loop:
    [code]
    current = bucketHead;
    while (current != null) {
    // Check value
    current = current.next;
    }
    [/code]
    As a hash I would use the hashCode() method, present in each Object.
    Creating a collection from this linked-list map is quite simple: just copy each individual linked list bucket and place the head of the next bucket after the tail of the first. For a first attempt, I would suggest that you make the collection unmodifiable.
    You also need to create an iterator, which should have 2 field: the current element and the head of the collection. The current field ought to start at null and never become null again. It's next() should check if the current is null, and if it is return the head of the collection. If it isn't and the current element has a non-null next, that should become the new current. hasNext() is simply checking if the current as a non-null next.
Sign In or Register to comment.