Как улучшить хеширование для коротких строк, чтобы избежать коллизий?

Question

У меня проблема с хеш-коллизиями с использованием коротких строк в .NET4.
РЕДАКТИРОВАТЬ: Я использую встроенную функцию хеширования строк в .NET.

Я реализую кеш, используя объекты, которые хранят направление конвертации, как это

public class MyClass
{
    private string _from;
    private string _to;

   // More code here....

    public MyClass(string from, string to)
    {
        this._from = from;
        this._to = to;
    }

    public override int GetHashCode()
    {
        return string.Concat(this._from, this._to).GetHashCode();
    }

    public bool Equals(MyClass other)
    {
        return this.To == other.To && this.From == other.From;
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;
        if (this.GetType() != obj.GetType()) return false;
        return Equals(obj as MyClass);
    }
}

Это зависит от направления, и from и to представлены короткими строками, такими как «AAB» и «ABA».

Я получаю редкие коллизии хэшей с этими небольшими строками, я пробовал что-то простое, например, добавление соли (не сработало).

Проблема в том, что слишком много моих маленьких строк, таких как «AABABA», сталкивает свой хеш с обратным «ABAAAB» (обратите внимание, что это не реальные примеры, я понятия не имею, если AAB и ABA на самом деле вызывают столкновения!)

и я пошел на тяжелую работу, как реализация MD5 (которая работает, но НАМНОГО медленнее)

Я также реализовал предложение от Джона Скита здесь:
Должен ли я использовать конкатенацию моих строковых полей в качестве хеш-кода? Это работает, но я не знаю, насколько надежно это с моими различными 3-символьными строками.

Как улучшить и стабилизировать хеширование небольших строк, не добавляя слишком много накладных расходов, как MD5?

РЕДАКТИРОВАТЬ: В ответ на несколько опубликованных ответов ... кэш реализован с использованием параллельных словарей с ключом из MyClass, как указано выше. Если я заменим GetHashCode в приведенном выше коде на что-то простое, например код @JonSkeet по ссылке, которую я разместил:

int hash = 17;
hash = hash * 23 + this._from.GetHashCode();
hash = hash * 23 + this._to.GetHashCode();        
return hash;

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

РЕДАКТИРОВАТЬ: Я должен также отметить, что это неправильное поведение зависит от платформы. Он работает, как и предполагалось, на моем полностью обновленном компьютере с Win7x64, но не работает должным образом на компьютере без обновления Win7x64. Я не знаю, в каком объеме отсутствуют обновления, но я знаю, что в нем нет Win7 SP1 ... поэтому я могу предположить, что может быть также и фреймворк SP или обновление, в котором он также отсутствует.

РЕДАКТИРОВАТЬ: Как и предполагалось, моя проблема не была вызвана проблемой с функцией хеширования. У меня было неуловимое состояние гонки, поэтому оно работало на некоторых компьютерах, но не на других, а также почему «медленный» метод хеширования заставлял вещи работать правильно. Ответ, который я выбрал, был наиболее полезным для понимания, почему моя проблема не заключалась в коллизиях хеша в словаре.

Answer 1

Вы уверены, что столкновения - это то, что вызывает проблемы? Когда вы говорите

Я наконец-то обнаружил причину этой ошибки

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

Я вставил небольшой фрагмент кода, чтобы проверить наличие коллизий для трехбуквенных слов. И этот код не сообщает ни об одном столкновении для них. Вы понимаете, о чем я? Похоже, алгоритм встроенного хеширования не так уж и плох.

Dictionary<int, bool> set = new Dictionary<int, bool>();
char[] buffer = new char[3];
int count = 0;
for (int c1 = (int)'A'; c1 <= (int)'z'; c1++)
{
    buffer[0] = (char)c1;
    for (int c2 = (int)'A'; c2 <= (int)'z'; c2++)
    {
        buffer[1] = (char)c2;
        for (int c3 = (int)'A'; c3 <= (int)'z'; c3++)
        {
            buffer[2] = (char)c3;
            string str = new string(buffer);
            count++;
            int hash = str.GetHashCode();
            if (set.ContainsKey(hash))
            {
                Console.WriteLine("Collision for {0}", str);
            }
            set[hash] = false;
        }
    }
}

Console.WriteLine("Generated {0} of {1} hashes", set.Count, count);

Хотя вы можете выбрать практически любую из известных хеш-функций (как упомянул Дэвид) или даже выбрать «идеальный» хеш, поскольку похоже, что ваш домен ограничен (например, минимальный идеальный хеш) ... Было бы здорово понять, действительно ли источником проблем являются столкновения.

Обновление

Что я хочу сказать, так это то, что встроенная хеш-функция .NET для строки не так уж и плоха. Это не дает столько коллизий, сколько вам потребуется для написания собственного алгоритма в обычных сценариях. И это не зависит от длины струн. Если у вас много 6-символьных строк, это не означает, что ваши шансы увидеть столкновение выше, чем при использовании 1000-символьных строк. Это одно из основных свойств хеш-функций.

И снова, еще один вопрос: с какими проблемами вы сталкиваетесь из-за столкновений? Все встроенные хеш-таблицы и словари поддерживают разрешение коллизий. Поэтому я бы сказал, что все, что вы можете видеть, это просто ... возможно, некоторая медлительность. Это твоя проблема?

Что касается вашего кода

return string.Concat(this._from, this._to).GetHashCode(); 

Это может вызвать проблемы. Потому что при каждом вычислении хеш-кода вы создаете новую строку. Может быть, это то, что вызывает ваши проблемы?

int hash = 17; 
hash = hash * 23 + this._from.GetHashCode(); 
hash = hash * 23 + this._to.GetHashCode();         
return hash; 

Это был бы гораздо лучший подход - просто потому, что вы не создаете новые объекты в куче. На самом деле, это один из основных пунктов этого подхода - получить хороший хэш-код объекта со сложным «ключом» без создания новых объектов. Так что если у вас нет единственного значения ключа, это должно работать для вас. Кстати, это не новая хеш-функция, это просто способ объединить существующие хеш-значения без ущерба для основных свойств хеш-функций.

Answer 2

Любая обычная хеш-функция должна подходить для этой цели.Если вы получаете столкновения на таких коротких строках, я бы сказал, что вы используете необычно плохую хеш-функцию.Вы можете использовать Jenkins или Knuth's без проблем.

Вот очень простая хеш-функция, которая должна быть адекватной.(Реализовано в C, но должно легко переноситься на любой подобный язык.)

unsigned int hash(const char *it)
{
 unsigned hval=0;
 while(*it!=0)
 {
  hval+=*it++;
  hval+=(hval<<10);
  hval^=(hval>>6);
  hval+=(hval<<3);
  hval^=(hval>>11);
  hval+=(hval<<15);
 }
 return hval;
}

Обратите внимание, что если вы хотите обрезать биты вывода этой функции, вы должны использовать младшие значащие биты.Вы также можете использовать мод, чтобы уменьшить выходной диапазон.Последний символ строки имеет тенденцию влиять только на младшие биты.Если вам нужно более равномерное распределение, измените return hval; на return hval * 2654435761U;.

Обновление :

public override int GetHashCode()
{
    return string.Concat(this._from, this._to).GetHashCode();
}

Это не работает.Он обрабатывает from = "foot", to = "ar" так же, как from = "foo", to = "tar".Поскольку ваша функция Equals не считает их равными, ваша хеш-функция не должна.Возможные исправления включают в себя:

1) Сформируйте строку из, "XXX", и хэшируйте ее.(Предполагается, что строка «XXX» почти никогда не появляется в ваших входных строках.

2) Объедините хеш «from» с хешем «to».Вам придется использовать умную функцию комбинирования.Например, XOR или сумма заставят from = "foo", to = "bar" хэшировать так же, как from = "bar", to = "foo".К сожалению, выбрать правильную функцию объединения нелегко, если не знать внутреннюю часть функции хеширования.Вы можете попробовать:

int hc1=from.GetHashCode();
int hc2=to.GetHashCode();
return (hc1<<7)^(hc2>>25)^(hc1>>21)^(hc2<<11);