Results 1 to 15 of 15
  1. #1
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

    Default How does HashMap work?

    Hi,

    I'm trying to learn how the HashMap class works. I have this big textfile with "all" countrys with their name, capital, poupulation and so on. And I want to add them to a hashmap, with the name of the country as a key.

    My question is:
    Do I have to use a hashfunction when I'm using HashMap? Because I read this somewhere, how to calculate the table index of a element using a hashfunction and modulus:
    Java Code:
    index(”Sweden”) = hashfunction(”Sweden”) mod lenght(hashTableSize) = 4
    
    hashfunction(string) { 
    h = 17; 
     for all chars c in string do: 
        h is put to the value of h * 31 + asciivalue for c 
    return h
    }
    But I can't see that people are using a hashfunctions to decide positioning, when they are using HashMap.

    I'm kind a confused about all this, so can someone please explaine in simple words how this works?

    Thanks.

    //Diana
    Last edited by sunde887; 08-20-2011 at 12:44 PM.

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    With hash functions, you don't care too much about "positioning" but rather separation -- you want a hash function that will put separate entities into separate boxes, and do this quickly. But having said this, you likely don't have to worry about this since String comes with its own decent hashCode method. If however you were creating your own class and using objects of that class as key, then yes, you would need to create your own hashCode method.

  3. #3
    R-J
    R-J is offline Member
    Join Date
    Aug 2011
    Posts
    11
    Rep Power
    0

    Default

    Essentially you base a key off of some identifying number, or string. You then create a hash code (for example you may raise each character to a power one larger than the previous character). This will turn out to be a large number, you modulo that number by the size of your array and that gives you an array index. So in order to find something in a hash table you just need to recompute the hash code and then you know where it is.

    The only issue with this method is sometimes different keys result in the same hash code. Those occurrences are referred to as "collisions". There are multiple ways to deal with collisions. One is to assign another spot in the array. This is known as "open addressing" and there are three types. "Linear probing", "quadratic probing" and "double hashing". Another is to add it to a linked list and have an array of linked lists. These two methods are not the only ones when it comes to resolving collisions.

    The purpose of creating an efficient hash table is to reduce the number of collisions. In order to minimize them the length of the array that makes up your table needs to be > 2x the number of elements you're storing in it. The array length also needs to be a prime number. Once the number of elements you have equals the array length, you must resize it.

    This method of storing data is very fast and is O(1) for looking up data.

    This is just a little insight into how a hashtable and a hashmap work, but java deals with all of this for you under the hood.

  4. #4
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

    Default

    Ok thanks for the replys you two .

    Fubarable or R-J, if I want to use my own created object "Country" as a key, do I just have to add the two methods equals() and hashCode() to the class like this?

    Java Code:
    public class Country {
    	
    	private String name;
    	private String capital;
    	private int population;
    	private int area;
    	
    	public Country() {
    	}
    	
    	public Country(String name, String capital, String population, String landArea) {
    		this.name = name;
    		this.capital = capital;
    		this.population = Integer.parseInt(population);
    		this.area = Integer.parseInt(landArea);
    	}
    
    	public String getName() {
    		return name;
    	}
    	
    	public String getCapital() {
    		return capital;
    	}
    	
    	public int getPopulation() {
    		return population;
    	}
    	
    	public int getArea() {
    		return area;
    	}
    	
    	@Override
    	public String toString() {
    		return "Name: " + name + "\nCapital: " + capital + "\Population: " + population + "\nArea: " + area + " km^2";
    	}
    	
    	@Override
    	public int hashCode() {
    		return this.toString().hashCode();
    	}
    	
    	@Override
    	public boolean equals(Object country) {
    		if(country == null) 
    			return false;
    		
    		if (this.getClass() != country.getClass())
    			return false;
    		
    		String name = ((Country)country).toString();
    		
    		return this.toString().equals(name);
    		
    	}
    }

    Also how will the hashMap.put() argument look like?

    Thanks.

    //Diana

  5. #5
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    I would leave anything that has a reasonable chance of changing over time out of the equals and hashCode, and so for your example above, I would leave population out of equals and hashCode and probably stick with name and capital (and both can change of course, but much less likely than population).

    Regarding
    Also how will the hashMap.put() argument look like?
    I'm not sure what you're asking here.

  6. #6
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

    Default

    About the "Also how will the hashMap.put() argument look like?", can I write like this if I want the capital name to be the key and the capital obejct as value?


    HashMap<String, Country> hashMap = new HashMap<String, Country>();
    hashMap.put(c.getName(), c);

  7. #7
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Quote Originally Posted by puffsan View Post
    can I write like this if I want the capital name to be the key and the capital obejct as value?
    Did you try it? What did the compiler say?

  8. #8
    masijade is offline Senior Member
    Join Date
    Jun 2008
    Posts
    2,571
    Rep Power
    9

    Default

    Quote Originally Posted by puffsan
    About the "Also how will the hashMap.put() argument look like?", can I write like this if I want the capital name to be the key and the capital obejct as value?


    HashMap<String, Country> hashMap = new HashMap<String, Country>();
    hashMap.put(c.getName(), c);
    Of course, but then the hashCode and equals in your class are "irrelevant" as the String is the key.

  9. #9
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

    Default

    masijade ok.. sorry for being such a noob on this, but all of this feels like latin to me right now.. But ok so I can just remove the hashCode and equals methods and everything is fine? The compiler don't say anything, but when I try to find a country by specifying the key I get null as a answer.

    // First I add the country to the hashMap
    hashMap.put(c.getCapital(), c);

    // Then I try to find it and print it
    System.out.println(hashMap.get("Denmark").toString ());

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

    Default

    What does that code give you as a result?

  11. #11
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

    Default

    Tolls: NullpointerException

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

    Default

    And what is the result of c.getCapital?
    Because I would lay good odds that you haven't got a "Denmark" in there.
    Especially since the capital would be "Copenhagen".

  13. #13
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

    Default

    omg this was embarrassing, It works now when I changed it... thanks for the help Tolls. I don't know why but sometimes I think with my ass..

    Thanks & cheers all

  14. #14
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,755
    Rep Power
    7

    Default

    Quote Originally Posted by puffsan View Post
    sometimes I think with my ass..
    I've never know a donkey to write a decent program.

  15. #15
    puffsan is offline Member
    Join Date
    Aug 2011
    Posts
    7
    Rep Power
    0

Similar Threads

  1. Help with HashMap
    By d0nmin0 in forum Advanced Java
    Replies: 8
    Last Post: 08-15-2011, 01:25 AM
  2. final HashMap hm=new HashMap();
    By sangramkeshari.jena in forum New To Java
    Replies: 4
    Last Post: 07-21-2011, 09:44 PM
  3. 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
  4. HashMap Help
    By digitol97 in forum New To Java
    Replies: 4
    Last Post: 09-13-2010, 02:38 AM
  5. Replies: 7
    Last Post: 12-08-2009, 07:17 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
  •