Hash function performance
scripting.com
Hash function performance
1–10 of 22 posts
Re: Hash function performance
#2I upvoted because I really hope to hear from someone who knows this stuff. Off the top of my head (as a non-expert), this sounds like a horrible hash function that is vulnerable to a plethora of attacks, but I don't know for sure. Why not just use the built-in hash function, or some function someone smarter than you has written?
Re: Hash function performance
#3I upvoted because I really hope to hear from someone who knows this stuff. Off the top of my head (as a non-expert), this sounds like a horrible hash function that is vulnerable to a plethora of attacks, but I don't know for sure. Why not just use the built-in hash function, or some function someone smarter than you has written?
It's absolutely, positively horrible. My real comments are on the blog itself.
Re: Hash function performance
#4Many of the design decisions in his software make a lot of sense for the design of an environment that could fit on a floppy.
Re: Hash function performance
#5I upvoted because I really hope to hear from someone who knows this stuff. Off the top of my head (as a non-expert), this sounds like a horrible hash function that is vulnerable to a plethora of attacks, but I don't know for sure. Why not just use the built-in hash function, or some function someone smarter than you has written?
It's an internal hash for hash tables and the like. It's not for crypto.
It's main issue is that it turns large tables into an O(n/10) linked list. It was kinda painful for a few things 10 years ago, and it was a reasonable hack 10 years before that when it was likely originally written. Iirc, there was one pathological case where all the items ended up in one bucket, but that's lost to the sands of time.
Fwiw, md5 has been available in his system since 98 or so, and any security related stuff would have been using that.
Re: Hash function performance
#6That's an awful hash function. The largest bucket has more than 4X as many items as the smallest. He should pick another function that uses all the characters in the object name. Whatever language or libraries he's already using probably has a better function for strings handy.
Re: Hash function performance
#7I read that headline and straight away thought of md4 versus md5 performance. I need to take a break :)
Re: Hash function performance
#8Why only 11 buckets? That seems like the bigger issue. Converting an O(n) lookup to O(n/10) seems silly. Why not have 1000 buckets and get two more orders of magnitude improvement in lookup performance.
Of course that will expose how bad the hash function really is. Saving a few cycles in the hash function and then chaining through 17k linked list entries doesn't make any sense.
Re: Hash function performance
#9Why only 11 buckets? That seems like the bigger issue. Converting an O(n) lookup to O(n/10) seems silly. Why not have 1000 buckets and get two more orders of magnitude improvement in lookup performance. Of course that will expose how bad the hash function really is. Saving a few cycles in the hash function and then chaining through 17k linked list entries doesn't make any sense.
Because it was a design decision from 20 years ago for small n hash tables. It's baked into the design of his object db files.
Re: Hash function performance
#10The ignorance in this article is almost embarrassing. Why does Dave Winer keep getting posts on HN?