5 ms·

What's up with that weird hash function? Seems to me you could just convert the string into its base 26 representation. Edit: I would actually like to know if/

What's up with that weird hash function? Seems to me you could just convert the string into its base 26 representation. Edit: I would actually like to know if/why the method used is more useful than the one I gave. I'm not just trying to be arrogant.

amalcon 17y ago
First, the function he gave wasn't particularly weird; it's a pretty standard thing. Second, the value resultant from said function is independent of the length of the word, which is exactly the sort of thing you want with a hash function. If you have a hash space large enough to hold the longest English word converted to base 26, then you might still need to be concerned with clustering properties. It's considered undesirable to have large stretches within the hash space with no associated key; my understanding is that this somehow impairs the distribution from the modulus step in most hashtable implementations.
alextp 17y ago
The problem with hashing is that you do not just want a number, but a number that is between 0 and the size of your table and that, over a reasonable distribution of objects, gives numbers that are uniformely distributed in that interval. You also want to avoid some obvious collisions (say, if you just add the letters of a word then all anagrams will hash into the same place, which is bad). Converting a word into base 26 will give you a huge number. Over six or seven characters and your hash does not fit into a 32-bit integer, and over 13 characters it will not fit into a 64-bit word. So he chooses to multiply by number that is prime in relation to the table size because that would definitely avoid cycles (say, if you've got a table of size 16 and double the number each time there are many positions into which words with that prefix will never hash, which can be a very bad idea).

5 ms·

What's up with that weird hash function? Seems to me you could just convert the string into its base 26 representation. Edit: I would actually like to know if/

by TheSOB88 17y ago

amalcon 17y ago
First, the function he gave wasn't particularly weird; it's a pretty standard thing. Second, the value resultant from said function is independent of the length of the word, which is exactly the sort of thing you want with a hash function. If you have a hash space large enough to hold the longest English word converted to base 26, then you might still need to be concerned with clustering properties. It's considered undesirable to have large stretches within the hash space with no associated key; my understanding is that this somehow impairs the distribution from the modulus step in most hashtable implementations.
alextp 17y ago
The problem with hashing is that you do not just want a number, but a number that is between 0 and the size of your table and that, over a reasonable distribution of objects, gives numbers that are uniformely distributed in that interval. You also want to avoid some obvious collisions (say, if you just add the letters of a word then all anagrams will hash into the same place, which is bad). Converting a word into base 26 will give you a huge number. Over six or seven characters and your hash does not fit into a 32-bit integer, and over 13 characters it will not fit into a 64-bit word. So he chooses to multiply by number that is prime in relation to the table size because that would definitely avoid cycles (say, if you've got a table of size 16 and double the number each time there are many positions into which words with that prefix will never hash, which can be a very bad idea).