You can probabilistically compare two unsorted vectors (u,v) in O(n) - SO

U= xor(h(u[0]), h(u[1]), ..., h(u[n-1]))
V= xor(h(v[0]), h(v[1]), ..., h(v[n-1]))

If U==V then the vectors are probably equal. h(x) is any non-cryptographic hash function.