Results 1 to 8 of 8
  1. #1
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Confusion about HashTables and how they work

    I have to implement my own version of the map ADT using a HashTable. So I was using the entry interface:

    Java Code:
       public interface Entry<K,V> { 
                          K getKey(); 
                          V getValue(); 
                           }
    However, my book also uses this class later on

    Java Code:
    public abstract class AbstractMap<K,V> implements Map<K,V> {
        public boolean isEmpty() { return size() == 0; } 
              //---------------- nested MapEntry class ---------------
                  protected static class MapEntry<K,V> implements Entry<K,V> { 
                     private K k; // key 
                      private V v; // value 
                     public MapEntry(K key, V value) { 
                        k = key; 
                        v = value; 
                      } 
                     // public methods of the Entry interface 
                      public K getKey() { return k; } 
                      public V getValue() { return v; } 
                    // utilities not exposed as part of the Entry interface                    
                        protected void setKey(K key) { k = key; }  
                        protected V setValue(V value) { 
                         V old = v; 
                         v = value; 
                         return old; 
                        } 
                   } 
             //----------- end of nested MapEntry class ----------
    This AbstractMap class is used in the hashtable. Therefore, I was wondering what is the use of the Map Entry nested class.
    So my question is
    1) Does a hashtable take a key K and hashes it to index i to then insert the element V in MapEntry<k,v> in A[i]?

    or

    2) A hashtable takes a key K, hashes it to index i and then it stores the whole MapEntry object in that exact index
    I.e: MapEntry(String, V) where V would be a char and the Key would be a string.
    So we have 2 MapEntry Object (Bus, C) and (Student, S). It hashes both keys (Bus and Student) to index, let's say, 2 and 5. In 2 and 5 we can then retrieve both bus and student?

    It just seems very confusing to me, I need some clarification but no one, not even my teacher, seems to understand my question.
    Thank you

  2. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Confusion about HashTables and how they work

    The way it works is as follows. You have a key/value pair. You need to hash the key to a number. This number is the number of the "bucket." Then you store then Entry (both key and value) in the bucket. The reason being is that when you want to retrieve the value for a given key, you hash the key to get the bucket, then search the bucket for the Entry than contains that key. Once found, you return the value.

    Note that the bucket can be an array or list implementation (as can be the collection of buckets).

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Re: Confusion about HashTables and how they work

    So, are you telling me I have to create Entry objects and then get the key of those, and THEN hashe it, when ashe I would ( if it's an array implementation) would do this --> Entry<String, Integer> entry1 = new Entry<String, Integer>(Bus, 5), Key = bus and it would give us i = 15 according to our Hashe function. This would then go to A[15] and store entry 1 in there. Did I get this right?

  4. #4
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Confusion about HashTables and how they work

    Not quite:

    To store a value.

    1. Create an ENTRY with both key and value.
    2. Get the hash code of the key.
    3. Create an index from the hash code to get the bucket (index is less than or equal to number of buckets).
    4. Store the ENTRY in the bucket.

    To retrieve a value for a specific key

    1. Hash the key
    2. Create an index from hash code to get the bucket.
    3. Now search each ENTRY in the bucket comparing the key to ENTRY.key.
    4. When found, return ENTRY.value
    5. If not found, return null (or some special value which means not found).

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  5. #5
    Manddd is offline Member
    Join Date
    Mar 2015
    Posts
    23
    Rep Power
    0

    Default Re: Confusion about HashTables and how they work

    Okay, lastly, the wikipedia article : https://en.wikipedia.org/wiki/Hash_table about hash Tables and it shows the array only stores phone numbers and not the actual entry, is that normal?

  6. #6
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Confusion about HashTables and how they work

    Quote Originally Posted by Manddd View Post
    Okay, lastly, the wikipedia article : https://en.wikipedia.org/wiki/Hash_table about hash Tables and it shows the array only stores phone numbers and not the actual entry, is that normal?
    You can't go by the picture alone because that was describing the ideal case. You need to read the article. Here is part of it under Collision Resolution.

    "...most hash table implementations have some collision resolution strategy to handle such events. Some common strategies are described below. All these methods require that the keys (or pointers to them) be stored in the table, together with the associated values."

    A collision is when multiple keys hash to the same bucket. So you need to store both the key and the value. Otherwise, you would not be able to determine which value within the bucket to return.

    Regards,
    Jim
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  7. #7
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default Re: Confusion about HashTables and how they work

    Quote Originally Posted by Manddd View Post
    Okay, lastly, the wikipedia article : https://en.wikipedia.org/wiki/Hash_table about hash Tables and it shows the array only stores phone numbers and not the actual entry, is that normal?
    Yes it is; suppose a key K hashes to a bucket b where V is stored (according to wikipedia); but now consider an entry K', V, where K' also hashes to bucket b ... if coalescing keys are kept as lists per bucket, you also have to store key K (and key K') somewhere near the values V and V'; that's why a Map.Entry object is stored.

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default Re: Confusion about HashTables and how they work

    What Jim says; I should refresh more often before I want to reply ;-)

    kind regards,

    Jos
    Build a wall around Donald Trump; I'll pay for it.

Similar Threads

  1. applet call dll work in Win2000 but not work in WinXP
    By manhcuongtin4 in forum Java Applets
    Replies: 1
    Last Post: 07-14-2011, 01:45 PM
  2. [SOLVED] HashTables
    By jon80 in forum New To Java
    Replies: 3
    Last Post: 06-22-2009, 02:15 PM
  3. Replies: 2
    Last Post: 12-07-2008, 06:13 PM
  4. accessing hashtables from another class
    By SimC in forum New To Java
    Replies: 19
    Last Post: 12-05-2008, 04:49 PM
  5. Generic Hashtables
    By ShoeNinja in forum New To Java
    Replies: 0
    Last Post: 12-04-2007, 10:43 PM

Tags for this Thread

Posting Permissions

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