Question: Is there any hash function that generates the same bucket for vectors having the same elements, with the same relative positions but shifted **k** times?

For example:

```
hash([1,9,8,7]) -> b1
hash([9,8,7,1]) -> b1

hash([1,8,9,7]) -> b2
hash([1,9,8,5]) -> b3

```

**v1** = [1,9,8,7] **v2** = [9,8,7,1] Both vectors should get the same hash since **v2** is **v1** left shifted k=3 times.

But **v3** = [1,8,9,7] doesn't keep the same relative order and **v4** = [1,9,8,5] has different values so neither of them get the hash b1.

My initial approach was to calculte the max value for each vector and consider its position as a reference (offset = 0). Having that I would only have to shift each vector so that the maximun value would be always at the first position. This way shifted vectors would look the same. However, vectors can have repeated elements and thus the maximun value has different positions.

Answer: 
1. Find the lexicographically minimal array rotation.

The native way is to check all rotations in O(n2), but it can be done in linear time using Booth's Algorithm, Shiloach's Fast Canonization Algorithm or Duval's Lyndon Factorization Algorithm.

See [this](http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation) for more.
2. Calculate the hash of the rotated array.

This can be done in various ways. Java, for example, would do it as follows:

```
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

```

It's not impossible that arrays with different elements will hash to the same value (this is inevitable with hashing), but all rotations of the same array will have the same hash.
Don't hash the elements of the array, hash the differences of two adjacent cells instead:

```
#include <stdio.h>

unsigned hashdiff(unsigned arr[], size_t siz);

        /* toy hash function: don't try this at home ... */
#define HASH1(v) ((v)*7654321)

unsigned hashdiff(unsigned arr[], size_t siz)
{
unsigned idx;
unsigned hash;

if (siz < 1) return 0;
if (siz < 2) return HASH1(arr[0]);

hash = HASH1( arr[0] - arr[siz-1] );

for(idx=1; idx < siz; idx++) {
        hash ^= HASH1(arr[idx] - arr[idx-1] );
        }

return hash;
}

unsigned arr1[] = {1,9,8,7};
unsigned arr2[] = {9,8,7,1 };

unsigned arr3[] = {1,8,9,7 };
unsigned arr4[] = {1,9,8,5 };

int main(void)
{
unsigned hash;

hash = hashdiff (arr1, 4); printf("%x\n", hash);
hash = hashdiff (arr2, 4); printf("%x\n", hash);
hash = hashdiff (arr3, 4); printf("%x\n", hash);
hash = hashdiff (arr4, 4); printf("%x\n", hash);

return 0;
}

```

RESULT:

```
./a.out
fee56452
fee56452
1100b22
fca02416

```

UPDATE: if you don't want {1,2,3,4} and{11,12,13,14} to hash to the same value, you could augment the difference like this:

```
#define HASH1(v) ((v)*7654321)
#define HASH2(a,b) HASH1(3u*(a)-5u*(b))

unsigned hashdiff2(unsigned arr[], size_t siz)
{
unsigned idx;
unsigned hash;

if (siz < 1) return 0;
if (siz < 2) return HASH1(arr[0]);

hash = HASH2( arr[0] , arr[siz-1] );

for(idx=1; idx < siz; idx++) {
        hash ^= HASH2( arr[idx] , arr[idx-1] );
        }

return hash;
}

```