Page 1 of 2 12 LastLast
Results 1 to 20 of 35
Like Tree4Likes

Thread: Hashing vs Array

  1. #1
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Hashing vs Array

    My question if I want to find a certain element in array I have to scan through the array index starting from 0 until I find the number I am looking for. Even in data structures which use hashing like HashMap and Hashtable we will have to scan through the keys until we find the key we are looking for. So what is the use of hashing over index based searching? I mean how is hashing an advantage over an array?

  2. #2
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Hashing vs Array

    I have a load of Strings.
    I want to find a single String in that load.

    If my Strings are in an array I would have to go through each entry, comparing my String against each one in the array until I find one. For a HashSet I would simply have to find the "bucket" that represents my hash and look at the few (preferably one) that I then do an equals on.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  3. #3
    jashburn is offline Senior Member
    Join Date
    Feb 2014
    Posts
    219
    Rep Power
    1

    Default Re: Hashing vs Array

    Read my reply to your post (LinkedHashSet) that was posted last week. Read also Hash table - Wikipedia, the free encyclopedia to understand how hashing works in a data structure.

  4. #4
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    For a HashSet I would simply have to find the "bucket" that represents my hash and look at the few (preferably one) that I then do an equals on.

    How is that possible? How can we bypass the checking part? The explanation of the internal storage may help.

    At the post by jashburn, the wikipedia link does not mention how we can bypass the checking part.

  5. #5
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Hashing vs Array

    What checking part?

    A hash table stores things in buckets. Think of the bucket as an array (indeed it is in HashMap, I believe) where a given hash value is mapped to an entry in the array. The entry is a handful of values. You can therefore get to values which are potentially equal to your requested value by simply doing an array[modifiedhashvalue], and then doing an equals on the values in there to find the one you want.

    Or, as the wiki puts it:
    "
    A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.
    "
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  6. #6
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    You can therefore get to values which are potentially equal to your requested value by simply doing an array[modifiedhashvalue], and then doing an equals on the values in there to find the one you want.

    Ok, lets take an example. In the example below I don't use a hashcode method. So how is the hashcode internally used to get fast access? Say I want to retrieve "one" from the arraylist and hashtable.

    Java Code:
    import java.util.ArrayList;
    import java.util.Hashtable;
    import java.util.List;
    import java.util.Map;
    
    
    public class Check {
    	public static void main(String args[])
    	{
    		List al=new ArrayList();
    		al.add("zero");
    		al.add("one");
    		
    		Map ht=new Hashtable();
    		ht.put(0,"zero");
    		ht.put(1,"one");
    	}
    }

  7. #7
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Hashing vs Array

    Yes you do.
    Your 0 and 1 are auto-wrapped into Integer objects, which have their own hashcode methods.
    Indeed, all Objects have a hashcode method.

    Look, your best bet is to simply step through the code and see what those two collection classes do on a get.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  8. #8
    jmohandos304 is offline Member
    Join Date
    Apr 2014
    Posts
    78
    Rep Power
    0

    Default Re: Hashing vs Array

    Look, your best bet is to simply step through the code and see what those two collection classes do on a get.

    Exactly. Is there no tutorial or article on how exactly it works internally? Do I need to use a debugger for that and then see what happens?

  9. #9
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,503
    Rep Power
    5

    Default Re: Hashing vs Array

    Quote Originally Posted by jmohandos304 View Post
    Is there no tutorial or article on how exactly it works internally? Do I need to use a debugger for that and then see what happens?
    Well, I usually look at the actual source in the JDK. But that is overkill for this. I may be repeating concepts that have already been covered so I apologize. Let's say you want to store information using two types of keys. Those keys that begin with a thru m and those that begin with n thru z. Let's assume you have 1000 key/value pairs. You have two options.

    1. Put all the keys in one bucket. Then when you want to retrieve a value, search the entire bucket. 1000 possible searches.
    2. Use two buckets. Look at the first letter of the key. If its a thru m, use bucket 1. If it is n thru z, use bucket 2. Now you have reduced your search from a max of 1000 to 501 (1 to choose the bucket, and then 500 within that bucket). Note that this example assumes a perfectly uniform distribution of keys which is very rarely the case. But the point of a hash table is to expedite look up for keys which do not lend them selves to direct access lookup (e.g. arrays). The process of locating the proper bucket is where the hash code comes into play.

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

  10. #10
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    How is hashing faster than array? Someone pls guide.

  11. #11
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Hashing vs Array

    It's been explained to you (assuming you have reverted to your original username).
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  12. #12
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    Just post the part which seems to explain, over here again.

  13. #13
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,876
    Rep Power
    5

    Default Re: Hashing vs Array

    Is it April fools again?
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  14. #14
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    No. Seriously. There are so many responses, but none of them is convincing. Just because we use something called buckets, we can bypass the checking part? Is it? Or, if the explanation uses buckets it is clearly visible without scanning the elements while checking it?

  15. #15
    gimbal2 is offline Just a guy
    Join Date
    Jun 2013
    Location
    Netherlands
    Posts
    3,876
    Rep Power
    5

    Default Re: Hashing vs Array

    That's fine, good luck finding a more convincing source of information then. The problem here is you, not what is said in this forum.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

  16. #16
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    Say there are 4 buckets with hashcodes say 25, 50, 75 and 100. I am looking for 75. So I have to check
    1. 25 with 75
    2. 50 with 75
    3. 75 with 75
    Last edited by suhaas_mohandos; 05-13-2014 at 01:10 PM.

  17. #17
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,503
    Rep Power
    5

    Default Re: Hashing vs Array

    Ok, I will try one more time. Let's say you have 1000 boxes with numeric ID's stamped on them. You want to find the box with ID number 2920292029021. So you have to search thru a maximum of 1000 boxes to locate the one with that ID.

    Now lets say that someone decided to put all the boxes whose ID is even (i.e. divisible by two), in one location and all the odd ID'd boxes in another location. You already know which ID you want to find. And you know which location contains which pile of boxes (even or odd ids). Now you go to the odd id boxes (because your ID, 2920292029021 is odd). You have reduced how many boxes you have to look at. So its faster for you, and when implemented properly, fast for a computer.

    In this case, the two locations represent the buckets. Determining the proper pile by examining the ID is the hash function.

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

  18. #18
    Join Date
    Aug 2013
    Posts
    55
    Rep Power
    0

    Default Re: Hashing vs Array

    But then you have to go thru each of the odd numbered boxes until you find the one you are looking for. It is just like looking for an element in array. Where's the difference?

  19. #19
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,503
    Rep Power
    5

    Default Re: Hashing vs Array

    Notice how big the number is. 2,920,292,029,021. What do you think would happen if you allocated an array that big. The ID could also be 30 digits. And the ID's are not necessarily sequential. Now the buckets themselves could be arrays. But you still have to search sequentially to find the appropriate key (in this case a 13 digit ID). In any event you are missing the point. Hash tables are used to limit the number of searches you have to do in order to speed up retrieval. I simply can't explain it any clearer.

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

  20. #20
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Hashing vs Array

    Quote Originally Posted by suhaas_mohandos View Post
    But then you have to go thru each of the odd numbered boxes until you find the one you are looking for. It is just like looking for an element in array. Where's the difference?
    The difference is that (using jim's example) you have instantly removed 500 boxes from consideration.
    In a proper hashing you would, in fact, remove pretty much all but the one you're interested in.

    And if you can't see what advantage only testing one or two boxes for equality and (potentially) testing 1000, then I really don't know what else to say.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

Page 1 of 2 12 LastLast

Similar Threads

  1. extend-able hashing question
    By java23_000 in forum Advanced Java
    Replies: 1
    Last Post: 05-10-2011, 01:38 AM
  2. Hashing
    By sravan_51 in forum New To Java
    Replies: 1
    Last Post: 12-28-2010, 04:47 AM
  3. Hashing problem
    By etherkye in forum Java Applets
    Replies: 0
    Last Post: 07-23-2009, 12:56 PM
  4. Hashing and Searching Benchmarking
    By peterdfl in forum New To Java
    Replies: 0
    Last Post: 12-07-2008, 10:28 PM
  5. Hashing in Java
    By ajaykushwaha in forum New To Java
    Replies: 1
    Last Post: 11-17-2008, 12:51 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
  •