# Uniqueness of byte arrays

Consider the situation, when you're given M byte arrays of size N, and you need to check if all of them have unique content (so there are no two arrays that have the same sequence of bytes). What would be the best option to check this condition?

From my point of view, there are several approaches available for this problem (the examples provided below are relevant for Go programming language ecosystem):

Compare hash sums

Take some fast non-cryptographic hash (like murmur3) and compute hash sum from the every array. Store every sum in a set and find duplicates. Provided that hash is O(N), the whole operation should be O(M*N):

func unique(arrays [][]byte) bool {
set := newSet()
for _, array := range arrays {
sum := hash(array)
dump := hex(sum)
if set.contains(dump) {
return false
}
}
return true
}


Compare arrays bytewise

In Go there is [bytes.Equal][2] function written in pure assembly which can utilize platform-dependent optimizations. So it's possible to iterate over the arrays and check equality pairwise for O(M^2*N):

func unique(arrays [][]byte) bool {
for i := 0; i < len(arrays); i++ {
for j := i + 1; j < len(arrays); j++ {
if result := bytes.Equal(arrays[i], arrays[j]); result {
return false
}
}
}
return true
}


Despite the fact that this algorithm has worse computational complexity, it may run faster due to above-mentioned optimizations.

String(?) algorithm

1. Take ith byte from every array
2. Compare bytes;
3. If all are unique, return true;
4. If there are repeating values, repeat step #1 for (i+1)th bytes for only those arrays which had equal ith bytes.

This should be also O(M*N), because in the worst case one would have to completely compare all arrays. But it seems like this approach will bring too much overhead (I mean state of algorithm between iterations etc.)