3 ms·
That's a great article, and I agree with most of it (e.g., that a balanced binary tree should be the default set/map data structure in programming languages; un
by jemfinch 16y ago
That's a great article, and I agree with most of it (e.g., that a balanced binary tree should be the default set/map data structure in programming languages; unfortunately it seems only C++ gets that right), but its reference to FNV as a good hash function is anachronistic.
For a more modern and much faster hash, see http://sites.google.com/site/murmurhash/ http://sites.google.com/site/murmurhash/ . Murmurhash3 is an order of magnitude faster than FNV: http://code.google.com/p/smhasher/wiki/MurmurHash3 http://code.google.com/p/smhasher/wiki/MurmurHash3 .
- chc 16y agoThe article actually just says FNV is popular, not good. The point (as I understand it) was how common bad hash functions are.
- eru 16y agoHaskell also gets it right. Look at Data.Map and Data.Set.
- jemfinch 16y agoHaskell "gets it right" because you can't write an applicative hash table with the same computational complexity as a mutable one. Haskell's option is either "ordinary balanced binary trees" or "hash table in the IO monad".