Существует ли круговая хеш-функция?

Обновление: Как указал Джон, первый подход не очень хорошо обрабатывает строки с повторением. Проблемы возникают, когда встречаются повторяющиеся пары букв, и в результате XOR становится 0. Вот модификация, которая, как мне кажется, исправляет исходный алгоритм. Он использует последовательности Евклида-Ферма для генерации попарно взаимно простых целых чисел для каждого дополнительного вхождения символа в строку. В результате 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

Вы можете найти детерминированную первую позицию, всегда начиная с позиции с «самой низкой» (с точки зрения алфавитного порядка) подстрокой. Так что в вашем случае вы всегда начинаете с «а». Если бы было несколько букв "а", вам пришлось бы учитывать два символа и т. Д.

Я сделал что-то подобное для проекта в колледже. Я попытался оптимизировать задачу коммивояжера двумя способами.Я думаю, что если элементы НЕ гарантированно уникальны, второе решение потребует немного большей проверки, но первое должно работать.

Если вы можете представить строку как матрицу ассоциаций, 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

Я бы согласился с вашей детерминированной «первой позицией» - найти «наименьший» персонаж; если он появляется дважды, используйте следующий символ как разрешающий момент (и т. д.). Затем вы можете повернуть его в «каноническое» положение и хешировать его обычным способом. Если тай-брейки работают на всем протяжении струны, то у вас есть струна, которая вращается сама по себе (если вы понимаете, что я имею в виду), и не имеет значения, какой из них вы выберете «первым».

Итак:

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

Я уверен, что вы могли бы найти функцию, которая может генерировать один и тот же хеш независимо от позиции символа во входных данных, однако как вы убедитесь, что h (abc) ! = h (efg) для каждого возможного ввода? (Конфликты будут возникать для всех алгоритмов хеширования, поэтому я имею в виду, как вы минимизируете этот риск.)

Вам потребуются дополнительные проверки даже после генерации хеш-кода, чтобы гарантировать, что строки содержат одни и те же символы.