4 ms·
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.
by wiredfool 16y ago
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.
- jemfinch 16y agoNone 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.
- hastydork 16y agoSorry you're wrong. Back in the day the tables had hundreds not thousands of elements. This was part of a code review. You're too grouchy.
- hastydork 16y agoSorry you're wrong. Back in the day the tables had hundreds not thousands of elements. This was part of a code review. You're too grouchy.
- wiredfool 16y agoWhat's the appropriate number of buckets, taking into account everywhere it's used?
- jemfinch 16y agoDepends 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).