有循环散列函数吗?

我会按照你确定的“第一个位置”——找到“最少”的字符;如果它出现两次,就用下一个字符作为断开连接的字符(等等)。然后你可以旋转到一个“规范”的位置,并以普通的方式散列它。如果绳子的整个过程都是断绳器,那么你就得到了一根自转的绳子(如果你明白我的意思的话),你选哪个做“第一”并不重要。

所以:

"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!)

正如Jon指出的,第一种方法不能很好地处理重复字符串。当遇到重复的字母对并且结果为0时,会出现问题。这里有一个修改,我相信修正了原来的算法。它使用 Euclid-Fermat sequences

我还稍微清理了一下算法。注意,包含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

第一个版本(尚未完成):

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

通过始终从“最低”(按字母顺序排列)子字符串的位置开始,可以找到确定的第一个位置。所以在你的情况下,你总是从“a”开始。如果有多个“a”,你必须考虑两个字符等等。

我确信您可以找到一个函数,它可以生成相同的哈希,而不管输入中的字符位置如何,但是,您如何确保 h(abc) != h(efg) 对于每一个可能的输入?(所有哈希算法都会发生冲突,所以我的意思是,如何将这种风险最小化。)

即使在生成哈希之后,也需要进行一些额外的检查,以确保字符串包含相同的字符。

public string ToCanonicalOrder(string input)
{
    char first = input.OrderBy(x => x).First();
    string doubledForRotation = input + input;
    string canonicalOrder 
        = (-1)
        .GenerateFrom(x => doubledForRotation.IndexOf(first, x + 1))
        .Skip(1) // the -1
        .TakeWhile(x => x < input.Length)
        .Select(x => doubledForRotation.Substring(x, input.Length))
        .OrderBy(x => x)
        .First();

    return canonicalOrder;
}

public static class TExtensions
{
    public static IEnumerable<T> GenerateFrom<T>(this T initial, Func<T, T> next)
    {
        var current = initial;
        while (true)
        {
            yield return current;
            current = next(current);
        }
    }
}

示例用法:

var sequences = new[]
    {
        "abcdef", "bcdefa", "cdefab", 
        "defabc", "efabcd", "fabcde",
        "abaac", "cabcab"
    };
foreach (string sequence in sequences)
{
    Console.WriteLine(ToCanonicalOrder(sequence));
}

abcdef
abcdef
abcdef
abcdef
abcdef
abcdef
aacab
abcabc

然后根据需要对结果调用.GetHashCode()。

sequence.ToCanonicalOrder().GetHashCode();

一种可能性是将输入的所有循环移位的散列函数组合成一个不依赖于输入顺序的元散列。

for(int i=0; i<string.length; i++) {
  result^=string.rotatedBy(i).hashCode();
}

你可以用任何其他的交换运算来代替^=。

更举个例子,考虑输入

为了得到我们吃的杂碎

hash(“abcd”)^hash(“dabc”)^hash(“cdab”)^hash(“bcda”)。

我在大学里为一个项目做过类似的事情。我用了两种方法来优化一个旅行推销员问题。我认为如果不能保证元素是唯一的,那么第二个解决方案需要更多的检查,但是第一个应该可以工作。

如果可以将字符串表示为关联矩阵,则abcdef将如下所示

  a b c d e f
a   x
b     x
c       x
d         x
e           x
f x

另一个更快的技巧是旋转字符串,使“第一个”字母是第一个。那么,如果你有相同的起点,同样的字符串将是相同的。

下面是一些Ruby代码:

def normalize_string(string)
  myarray = string.split(//)            # split into an array
  index   = myarray.index(myarray.min)  # find the index of the minimum element
  index.times do
    myarray.push(myarray.shift)         # move stuff from the front to the back
  end
  return myarray.join
end

p normalize_string('abcdef').eql?normalize_string('defabc') # should return true

可能对每个偏移量使用滚动哈希(类似RabinKarp)并返回最小哈希值?但可能会有碰撞。