7 Replies - 338 Views - Last Post: 17 April 2011 - 02:06 PM Rate Topic: -----

#1 noctolater  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 72
  • Joined: 29-April 09

Help Selecting A Hash Function

Posted 17 April 2011 - 11:05 AM

I am using a HashMap to store the outgoing edges of a graph in each vertex. My key is a number from 0 to n-1, where n is specified at graph creation and represents the destination vertex. I have been looking around trying to find a good list of hash functions, but it seems that most places just say to develop your own based on your needs. I was wondering, however, if anyone might know a good place to start? I would imagine that the edges will be randomly distributed over the range from 0 to n-1, but the user can always input more edges at a later date. Any ideas as to general hash functions that I can specialize for this purpose? Thanks for your time.

This post has been edited by noctolater: 17 April 2011 - 11:06 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Help Selecting A Hash Function

#2 KYA  Icon User is online

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3120
  • View blog
  • Posts: 19,166
  • Joined: 14-September 07

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 11:08 AM

What happens if you have two vertexes with the same key? Is the second dropped?


If you ignore dupes, then a simple mod n hash would be sufficient.
Was This Post Helpful? 2
  • +
  • -

#3 noctolater  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 72
  • Joined: 29-April 09

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 11:48 AM

Yes, there are no repeated keys. However, the problem with a simple mod n is that I end up with an array the same size as the number of edges, which essentially gives me an adjacency matrix, which is too high memory cost. Or, by mod n, did you mean some number n much smaller than the number of keys? Sorry that I did not mention unique keys previously, and sorry if I misunderstood your response.

This post has been edited by noctolater: 17 April 2011 - 11:49 AM

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 12:29 PM

Are you designing your own HashMap class? If not, the HashMap class already handles hashing, so I'm not sure why you need to develop your own hashing function. What I would suggest is designing your own Edge class to store the destinationVertex and weight. Then store a HashMap<Integer, List<Edge>>.

Hope this helps some. :)
Was This Post Helpful? 2
  • +
  • -

#5 noctolater  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 72
  • Joined: 29-April 09

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 01:34 PM

Thanks for the reply! I am already doing that with the edge :P But, from everywhere I read about HashMap, you should override the equals and getHash methods when you use it. Was this information wrong?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 01:42 PM

You should almost always override the equals() method when creating a class, unless you want Objects from that class to be compared using the == operator solely. The values are not hashed, only the keys are. Really, no need to worry about custom hashcode if you are using an Integer as your key. When you may want to deal with overriding hashcode is if you have custom Objects as the keys. In this instance, hashcode() should return the same value only for two Objects that are equal according to the equals() method.
Was This Post Helpful? 1
  • +
  • -

#7 noctolater  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 72
  • Joined: 29-April 09

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 01:54 PM

Thank you so much for your responses. I will just leave it as it is then. I just finished the assignment super quick and was wondering about optimizations that could be done :P
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Help Selecting A Hash Function

Posted 17 April 2011 - 02:06 PM

Glad I could help! :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1