Order insensitive hash function for an array

Question

I'm looking for a hash-function which will produce the same result for unordered sequences containing same elements.

For example:

Array_1: [a, b, c]
Array_2: [b, a, c]
Array_3: [c, b, a]

The hash-function should return the same result for each of these arrays.

How to achieve this?

The most popular answer is to sort elements by some rule, then concatenate, then take hash.

Is there any other method?

Answer 1

if a,b,c are numbers, you could sum up and then build a hash on the sum. You may multiply, too. But take care about zeros! XOR-ing numbers is also an approach.

for very small numbers you may consider to set the bit indexed by the number. This means building a long (64bit) as input for the hash allows only element numbers in range 0-63.

The more elements you have the more collisions you will get. In the end you map n elements with m bits (resulting to 2^(m*n) range) to a hash value with k bits. Usually m and k is a constant but n varies.

Please aware any access as by a hash requires a test whether to get the correct element. In general a hash is NOT unique.

otherwise sort the element and then do the hash as proposed

Regarding the comment from CodesInChaos:

in order to be able to omit a test, the numbers of bits of the hash should be much greater than the sum of elements bits. Say at least 64 bits more. In general this situation is not given.

One common case of secure hash/unique id is a guid. This means effectively 128 bits. A random sequence of text char reaches this number of bits within 20-25 characters. Longer texts are very likely to produce collisions. It depends on the use case whether this is still acceptable.