In the hashing department: - Zobrist hashing. It's completely incredible that such a trivial scheme is a near-perfect hash for sets. That's before you even c

In the hashing department: - Zobrist hashing. It's completely incredible that such a trivial scheme is a near-perfect hash for sets. That's before you even consider the useful ability to compute hashes of related sets with added/removed-elements by simple XORing. (Caveat: I'm repeatedly tempted to use this magic for large sets; but it stops working well when number of elements > number of bits, because the matrix is over-determined, so there are easy-to-find subsets that contribute 0) - Cuckoo hashing. Before going into the specific way it pushes around elements to usually fit exactly 1 per slot, there is a basic idea to grok that makes 2 possible places for an element work much better than 1: "the power of 2 choices". This is also the reason even a little load-balancing is effective. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8277 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.8... is a great overview. - Merkle DAGs. Immutable content hashes are about the only non-painful form of distributed pointers humanity has found. OK, that's an idea not exactly an algorithm, but for example the easy ability to recursively diff 2 git trees is a neat algorithm.