It depends. You want to arrange things so that your hashing algorithm will generate every number between 1 and the table size. So if you're generating an arbitrary number and doing modulo the table size, it doesn't matter what the table size is.Originally posted by John Lockheart:
1)Should the table size always be a prime number?
No, ideally the table should be completely full. But you probably won't achieve a perfect hash function.2)Should the table's size be double the amount of information being stored in it so it is only half full?
Since the function "1" works perfectly well for step size, I would say it doesn't matter how you find it.3)Double Hashing: 2 Hashing functions..1st for bucket number, second for step size...when calculating step size and using modulos arithmatic, does it matter how you find the step size? Can I just copy the first function but subtract 1 from the tablesize?
"I'm not back."  Bill Harding, Twister
A "perfect" hash function is one where you have N items to hash, and N slots to hash them into, and each of the N items hashes directly into a different one of the N slots. You don't get one of those things without a lot of upfront tinkering with your hash function, and you have to know in advance what the N items are. That isn't a common scenario. That's what I meant. I have no idea how much empty space you should budget for in a reallife hashtable, I'm sure that the phrase "it depends" would apply though.Originally posted by Jim Yingst:
[Paul]: No, ideally the table should be completely full. But you probably won't achieve a perfect hash function.[/b]
Hm, really? Seems like filling the hashtable to 100% would result in needing more and more probes as you go, since the slots would be increasingly likely to already be taken.
"I'm not back."  Bill Harding, Twister
"I'm not back."  Bill Harding, Twister
You’ll find me in my office. I’ll probably be drinking. And reading this tiny ad.
a bit of art, as a gift, the permaculture playing cards
https://gardenergift.com
