Results 1 to 6 of 6
Like Tree1Likes
  • 1 Post By jim829

Thread: Hash table chaining

  1. #1
    jktexas1 is offline Member
    Join Date
    Feb 2013
    Posts
    6
    Rep Power
    0

    Default Hash table chaining

    My book decided to not show any code on this portion but I have a picture painted in my head from it. I just need confirmation that I'm going the right way.

    -A linked based hash table is an array of linked lists.

    I'll pretend that I made a class called linkedList for simplicity and ill store ints.

    This is the picture I have:

    linkedList table1[] = new linkedList[20];
    int a = 33;
    int hashCode = a%20;
    table1[hashCode].add(a);

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    2,924
    Rep Power
    4

    Default Re: Hash table chaining

    You are correct! Your description of a HashTable is one way of implementing it. Basically, a hash table in general is a way to speed up access to stored information. Each hashCode points to a bucket of information. You then do a finer grained search on the contents of the bucket to find the specific value.

    Using an array and linked list is actually how it is done within the JDK API. And your example is correct. You have an element, a. You generate a hash code based on the value "a" and some hash function and use that to add a to the linked list indexed into the array. The main caution is to ensure that the hashcode always returns the same value if the same values are operated on. In other words, you don't want the String "hello" to hash to two different buckets on different calls to the same hash function.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    jktexas1 is offline Member
    Join Date
    Feb 2013
    Posts
    6
    Rep Power
    0

    Default Re: Hash table chaining

    "Buckets of information" really sticks, I like that.

    Thanks for your help Jim,

    -Jacob

  4. #4
    jktexas1 is offline Member
    Join Date
    Feb 2013
    Posts
    6
    Rep Power
    0

    Default Re: Hash table chaining

    For reference purposes:

    All lists need to be initialized before they can be used.

    for(int i = 0; i<table.size(); i++){
    table[i] = new linkedList();
    }

  5. #5
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    2,924
    Rep Power
    4

    Default Re: Hash table chaining

    Not necessary and definitely inefficient.

    LinkedList[] table;

    table = new LinkedList[10];

    The table now contains 10 references to null. When you find the table index for a hashcode, just check for null. If it is null, then assign a new LinkedList entry. Otherwise, tie one into the existing entry at that index.

    Regards,
    Jim
    jktexas1 likes this.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  6. #6
    jktexas1 is offline Member
    Join Date
    Feb 2013
    Posts
    6
    Rep Power
    0

    Default Re: Hash table chaining

    That is definitely more efficient, didn't think about doing that.
    Thanks for the tip,

    Jacob
    Last edited by jktexas1; 03-22-2013 at 04:21 AM.

Similar Threads

  1. Replies: 9
    Last Post: 11-12-2012, 11:38 AM
  2. hash table chaining
    By xkillswitchx14 in forum New To Java
    Replies: 0
    Last Post: 05-03-2011, 05:24 PM
  3. hash table
    By pinkfahtema in forum New To Java
    Replies: 1
    Last Post: 03-28-2011, 08:25 AM
  4. Hash Table Help
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 11-27-2008, 05:12 PM
  5. Hash table with separate chaining
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-12-2008, 08:42 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •