Live data from Hacker News

Hash function performance

scripting.com

21–22 of 22 posts

Re: Hash function performance

#21

Many of the design decisions in his software make a lot of sense for the design of an environment that could fit on a floppy.

None of the ones in this post do, though. Using an appropriate number of buckets would actually reduce memory usage. Using an appropriate hash function (one that at least considered all the characters in the key) wouldn't increase the time to hash a string read off a floppy disk, because he's using the first and last characters anyway.

What's the appropriate number of buckets, taking into account everywhere it's used?

Re: Hash function performance

#22

Earlier quoted context omitted.

None of the ones in this post do, though. Using an appropriate number of buckets would actually reduce memory usage. Using an appropriate hash function (one that at least considered all the characters in the key) wouldn't increase the time to hash a string read off a floppy disk, because he's using the first and last characters anyway.

What's the appropriate number of buckets, taking into account everywhere it's used?

Depends on your way of hashing. If you're using linear chaining (basically, hashing a linked list of entries) you can get away with N buckets for N items if you have a good hash function. If you're using open addressing, you'll usually want your load factor (the ratio of filled slots to unfilled slots) not to be much higher than 2/3 or so. It may appear on the surface that open addressing uses more memory, but don't forget the overhead of linear chaining (an extra pointer for every element in the hash table, many more cache misses relative to a low-load open addressed table).
Post reply on HN