是否有任何散列函數爲具有相同元素的向量生成相同的存儲桶，具有相同的相對位置，但是移位了k次？偏移量獨立散列函數
例如：
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]兩種載體應該得到相同的哈希因爲V2是v1左移k = 3次。
但V3 = [1,8,9,7]不保持相同的相對順序和V4 = [1,9,8,5]有不同的值，所以他們都沒有得到哈希B1。
我最初的方法是計算每個向量的最大值並將其位置視爲參考（偏移量= 0）。有了這個，我只需要移動每個向量，使最大值總是在第一個位置。這種方式移動的向量看起來是一樣的。然而，向量可以具有重複的元素，因此最大值具有不同的位置。
找到字典上最小的數組旋轉。
原生方法是檢查O中的所有旋轉，但它可以使用布斯算法，Shiloach的快速優化算法或Duval的Lyndon因式分解算法在線性時間內完成。
有關更多信息，請參見this。
計算旋轉數組的散列。
這可以通過各種方式完成。 Java中，例如，可以按如下方式做到這一點：
hash = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
這不是不可能的，不同的元素陣列將返回相同的值（這是不可避免的散列），但同一陣列的所有旋轉將具有相同的散列。
如果我們串接B1與本身然後我們得到：
[1,9,8,7,1,9,8,7]
此數組包含原始數組的所有循環排列。
如果我們然後計算每個長度爲4的子數組的散列值並加入並組合這些散列值，那麼您將擁有一個唯一的散列值。散列函數計算可能需要進行一些優化，具體取決於陣列的大小。
編輯：每個子數組，除了最後一個，等於第一個！
如果你不太關心偶爾發生的散列衝突，你可以簡單地將所有元素的總和作爲散列（但要小心浮點問題），因爲這對向量的任何旋轉都是不變的。或者，您可以將xor或總和所有單個元素的散列值相加。你也可以根據後續元素的差異來計算某些東西（同時包含最後一個元素到第一個元素）。添加一些旋轉不變的屬性，兩個「不相等」的數組產生相同散列的機率會非常低。也許類似於
n = length(x)
rot_invariant_hash = hash(n) + sum(hash(x[i])) + sum(hash(x[mod(i+1, n)] - x[i]))
您可以在其中替換任何其他可交換（？）操作（如XOR）的所有總和。還要確保應用於差異的散列函數不是標識函數，否則這些部分將全部加起來爲零。所有這些都需要O（n）的計算時間。
只是一個好奇心：你打算的應用是什麼？
我正在嘗試開發循環多邊形的散列函數。因此，輸入向量是外接圓中不同節點的相對距離。 –
無（對於OP）：如果你需要做一個最後的比較（散列之後），你將不得不把你的循環多邊形變成一些規範的形式。 – joop
假設你總是有數字作爲矢量分量，計算：
i，(i+1) mod n） 其中加1的d_i對於所有非負差異並將兩者相乘。
第一個產品從元素的順序抽象出來，這是由第二個產品的模數旋轉重新引入的。如果存在具有相同值的兩個相鄰分量，則將每個差分加1避免映射到0。
獨立的第一個產品是不夠的，因爲它將所有組件排列映射到相同的散列值。因爲它將沿着（1，...，1）偏移的所有向量映射到相同的值，所以獨立的第二個產品是不夠的。
我會試試這個解決方案，但我有一個觀察：如果連續的元素是相等的，那麼相鄰元素的所有差異的乘積就是零，所以我認爲它應該是同一個符號的所有差異加和偏移的乘積差異本身。 –
@PabloFranciscoPérezHidalgo：好的，謝謝。答案調整。 – collapsar
不要散列數組的元素，哈希兩個相鄰單元的差異，而不是：
#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;
}
結果：
./a.out
fee56452
fee56452
1100b22
fca02416
UPDATE：如果你不想{1， 2,3,4}和{} 11,12,13,14散列爲相同的值，可以增加這樣的區別：
#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;
}
我還沒有編碼的，但我認爲它可以工作：
爲了讓您的哈希值，你只需要抓住項目的順序，避免偏移。有點像這樣的項目：
a = [1,9,8,7]
s = sort(a) = [1,7,8,9]
現在捕捉它們之間的順序：
1 => 9
7 => 1
8 => 7
9 => 8
snext = next(s, a) = [9,1,7,8]
現在CONCAT S和snext：
[1,7,8,9,9,1,7,8]
和散列它。
爲了實現next（）函數只使用載體作爲關聯數組和遍歷s個項目。
陣列因爲它共享相同的項目和它們的相對階數等於[9,8,7,1]將產生相同的散列。
然而，陣列[1,8,9,7]產生不同的散列;它共享相同的項目，但它們的相對順序不一樣。
我希望它有幫助。
沒有必要連接向量與自身，只是循環地從每個向量位置迭代，這將提供相同的結果，而不會使內存使用加倍。我認爲你的解決方案在形式上是正確的，但如果我沒有錯，假設每個子陣列哈希計算都是O（n）[在這個例子中n = 4]，那麼你的方法的時間複雜度至少爲O（n^2）。我想知道是否可以改進。 –
它取決於散列函數的計算：假設h（k）= a0 + a1 k^1 + a2 k^2 + ...那麼我們可以用一個常數計算第二個置換的h與第二個置換的h操作次數。因此h（1,9,8,7）可以被重新用來計算h（9,8,7,1），我們可以重用9,8,7部分（用k除）。 – DDW