是否有循环散列函数？

Question

考虑到关于测试字符串旋转的这个问题,我想知道:是否存在循环/循环散列函数？例如

h(abcdef) = h(bcdefa) = h(cdefab) etc

用于此的包括可伸缩算法,其可以相互检查n个字符串以查看一些是其他的旋转.

我想哈希的本质是提取特定于订单但不是位置特定的信息.也许某些东西找到了确定性的"第一个位置",旋转到它并散列结果？

这一切似乎都是合情合理的,但此刻略显超出我的掌握; 它必须已经在那里......

Answer 1

我会同意你的确定性"第一个位置" - 找到"最少"的角色; 如果它出现两次,请使用下一个字符作为平局破坏者(等).然后,您可以旋转到"规范"位置,并以正常方式散列.如果断路器在弦乐的整个过程中运行,那么你有一个自身旋转的弦(如果你看到我的意思),你选择哪个"第一"并不重要.

所以:

"abcdef" => hash("abcdef")
"defabc" => hash("abcdef")
"abaac" => hash("aacab") (tie-break between aa, ac and ab)
"cabcab" => hash("abcabc") (it doesn't matter which "a" comes first!)

Answer 2

更新:正如Jon指出的那样,第一种方法不能很好地处理重复的字符串.当遇到重复的字母对并且得到的XOR为0时出现问题.这是我认为修改原始算法的修改.它使用Euclid-Fermat序列为字符串中每个额外出现的字符生成成对互质整数.结果是重复对的XOR不为零.

我也稍微清理了算法.请注意,包含EF序列的数组仅支持0x00到0xFF范围内的字符.这只是演示算法的廉价方式.此外,算法仍然具有运行时O(n),其中n是字符串的长度.

static int Hash(string s)
{
    int H = 0;

    if (s.Length > 0)
    {
        //any arbitrary coprime numbers
        int a = s.Length, b = s.Length + 1;

        //an array of Euclid-Fermat sequences to generate additional coprimes for each duplicate character occurrence
        int[] c = new int[0xFF];

        for (int i = 1; i < c.Length; i++)
        {
            c[i] = i + 1;
        }

        Func<char, int> NextCoprime = (x) => c[x] = (c[x] - x) * c[x] + x;
        Func<char, char, int> NextPair = (x, y) => a * NextCoprime(x) * x.GetHashCode() + b * y.GetHashCode();

        //for i=0 we need to wrap around to the last character
        H = NextPair(s[s.Length - 1], s[0]);

        //for i=1...n we use the previous character
        for (int i = 1; i < s.Length; i++)
        {
            H ^= NextPair(s[i - 1], s[i]);
        }
    }

    return H;
}


static void Main(string[] args)
{
    Console.WriteLine("{0:X8}", Hash("abcdef"));
    Console.WriteLine("{0:X8}", Hash("bcdefa"));
    Console.WriteLine("{0:X8}", Hash("cdefab"));
    Console.WriteLine("{0:X8}", Hash("cdfeab"));
    Console.WriteLine("{0:X8}", Hash("a0a0"));
    Console.WriteLine("{0:X8}", Hash("1010"));
    Console.WriteLine("{0:X8}", Hash("0abc0def0ghi"));
    Console.WriteLine("{0:X8}", Hash("0def0abc0ghi"));
}

输出现在是:

7F7D7F7F
7F7D7F7F
7F7D7F7F
7F417F4F
C796C7F0
E090E0F0
A909BB71
A959BB71

第一个版本(不完整):使用可交换的XOR(顺序无关紧要)和另一个涉及互质的小技巧,以组合字符串中的有序字母对的哈希值.这是C#中的一个例子:

static int Hash(char[] s)
{
    //any arbitrary coprime numbers
    const int a = 7, b = 13;

    int H = 0;

    if (s.Length > 0)
    {
        //for i=0 we need to wrap around to the last character
        H ^= (a * s[s.Length - 1].GetHashCode()) + (b * s[0].GetHashCode());

        //for i=1...n we use the previous character
        for (int i = 1; i < s.Length; i++)
        {
            H ^= (a * s[i - 1].GetHashCode()) + (b * s[i].GetHashCode());
        }
    }

    return H;
}


static void Main(string[] args)
{
    Console.WriteLine(Hash("abcdef".ToCharArray()));
    Console.WriteLine(Hash("bcdefa".ToCharArray()));
    Console.WriteLine(Hash("cdefab".ToCharArray()));
    Console.WriteLine(Hash("cdfeab".ToCharArray()));
}

输出是:

4587590
4587590
4587590
7077996