> I actually had no idea it was possible to do efficient count-distinct without hashes, but it turns out it is!

Since the final algorithm maintains a Set, doesn't it still perform hashes?

This implementation incidentally uses a hash table, but any set-like data structure would work. This is different from things like HyperLogLog that actually depend on the hash values themselves in order to work.