I need help writing a hash function. I don't really understand them too much but I need to make one for a list of words. I'm writing a program that finds every word in a Word Search that appears in the Word Search's "dictionary". For example if the category of the puzzle was "food" then some words in the dictionary may be: apple, carrot, orange, ect. I need to do this by both double hashing and linear probing which I think I understand but I don't know how to make a good hash function to do so. Can anyone help>
4
-
why cannot you use the existing hashtable/map?Kent– Kent2012-02-20 21:43:17 +00:00Commented Feb 20, 2012 at 21:43
-
1This sounds like homework; if it is, then please edit your question to add the "homework" tag.ruakh– ruakh2012-02-20 21:44:40 +00:00Commented Feb 20, 2012 at 21:44
-
This looks like homework. If so, you might be able to just use the built in String hash function, which is pretty good. I'd imagine you can then focus on the hash table itself. If I'm wrong about the homework or being allowed to use a String hash function, let me know and I'll try to help more.BlackVegetable– BlackVegetable2012-02-20 21:45:10 +00:00Commented Feb 20, 2012 at 21:45
-
1You only need to do those things (i.e: double hashing and linear probing) in the event of a collision. The basic process will be to compute the hash of some string then store it in an array or table using the hashcode as the index.Hunter McMillen– Hunter McMillen2012-02-20 21:45:33 +00:00Commented Feb 20, 2012 at 21:45
Add a comment
|
1 Answer
As far as I understand, you need to build a hash function for a set of words, right? Simple sequential XORing (+ rotating, if the word order matters) of hashCode()'s for each word will do a good job for you.
If unsure, create a class for which you need to build a hash function and execute the Source - Generate hashCode() and equals() command in Eclipse for this class.
1 Comment
BlackVegetable
To check your collision resolution, use a terrible hash function like everything mapping to bucket #1 and run it in the debugger. That way you can see how your linear probing functions, at the very least. A great hash function like Alex posted will hide this from you perhaps, stealing a learning opportunity from you but reaching your endgoal quite nicely.