Basically David's approach: we fix $M$ = number of bits storage, and compute the indicator $ h = XOR \( hash_M (a [i] ) \) $

where $hash_M$ is a hash function to $M$ bits (eg MD5 masked to M bits). We decide that it is a permutation without repetitions by comparing with the same indicator for the ordered array (1..N). This is order N. And there is a probability of error which should be around $1/2^M$... if I'm not mistaken.

Basically David's approach: we fix $M$ = number of bits storage, and compute the indicator $h = XOR(\operatorname{hash}_M(a[i]))$ where $\operatorname{hash}_M$ is a hash function to $M$ bits (eg MD5 masked to M bits). We decide that it is a permutation without repetitions by comparing with the same indicator for the ordered array (1..N). This is order N. And there is a probability of error which should be around $1/2^M$... if I'm not mistaken.