There's a classic solution to detecting most missing entries: make your value a pair of a signature and the actual value. m signature bits result in a 2^-m false match rate for keys not in the input map.
Again, the MWHC construction does not need to map the hashed keys to ranks, they can map to the values directly.