Краткий ответ: Да.
Но короткие ответы неинтересны, не так ли?
При реализации GetHashCode() вы должны предоставить следующую гарантию:
Когда GetHashCode() вызывается для другого объекта, который следует считать равным этому, в этом Домене приложения будет возвращено то же значение.
Вот и все. Есть некоторые вещи, которые вам действительно нужно попробовать (распределить биты между неравными объектами настолько, насколько это возможно, но не занимайте так много времени, что это перевешивает все преимущества хеширования в первую очередь) и ваш код будет сосать, если вы этого не сделаете, но на самом деле он не сломается. Это сломается, если вы не зайдете так далеко, потому что тогда, например ::
dict[myObj] = 3;
int x = dict[myObj];//KeyNotFoundException
Хорошо. Если я реализую GetHashCode(), почему я могу пойти дальше, а почему нет?
Во-первых, почему я не могу?
Возможно, это немного другая версия сборки, и я улучшил (или хотя бы попытался) между сборками.
Может быть, один 32-битный, а другой 64-битный, и я сходил с ума по эффективности и выбрал разные алгоритмы для каждого, чтобы использовать разные размеры слов (это не неслыханно, особенно при хешировании объектов, таких как коллекции). или строки).
Может быть, какой-то элемент, который я решаю учитывать при принятии решения о том, что составляет "равные" объекты, сам по себе меняется в зависимости от системы.
Может быть, я на самом деле намеренно представляю другое начальное число с разными сборками, чтобы поймать любой случай, когда коллега ошибочно зависит от моего хэш-кода! (Я слышал, что MS делает это с их реализацией для string.GetHashCode(), но не помню, слышал ли я это из достоверного или надежного источника).
В основном это будет одна из первых двух причин.
Теперь, почему я могу дать такую гарантию?
Скорее всего, если я это сделаю, это будет случайно. Если элемент можно сравнить на равенство только на основе одного целочисленного идентификатора, то это то, что я собираюсь использовать в качестве моего хеш-кода. Все остальное будет больше работать для менее хорошего хэша. Я не могу изменить это, поэтому я мог бы.
Другая причина, по которой я могу это сделать, заключается в том, что я хочу получить эту гарантию сам. Мне нечего сказать, я не могу это предоставить, просто мне не нужно.
Хорошо, давайте перейдем к чему-то практичному. В некоторых случаях вам может потребоваться независимая от машины гарантия. Бывают случаи, когда вам может понадобиться обратное, к которому я немного позже.
Сначала проверь свою логику. Вы можете справиться со столкновениями? Хорошо, тогда мы начнем.
Если это ваш собственный класс, то реализуйте его, чтобы предоставить такую гарантию, запишите его, и все готово.
Если это не ваш класс, то реализуйте IEqualityComparer<T> таким образом, чтобы обеспечить его. Например:
public class ConsistentGuaranteedComparer : IEqualityComparer<string>
{
public bool Equals(string x, string y)
{
return x == y;
}
public int GetHashCode(string obj)
{
if(obj == null)
return 0;
int hash = obj.Length;
for(int i = 0; i != obj.Length; ++i)
hash = (hash << 5) - hash + obj[i];
return hash;
}
}
Затем используйте это вместо встроенного хеш-кода.
Есть интересный случай, когда мы можем захотеть обратного. Если я могу контролировать набор строк, которые вы хэшируете, то я могу выбрать набор строк с одинаковым хеш-кодом. Производительность вашей коллекции, основанной на хешах, будет хуже, и будет довольно жестокой. Скорее всего, я могу продолжать делать это быстрее, чем вы можете справиться с этим, поэтому это может быть атака типа «отказ в обслуживании». Это не так много случаев, но важным является случай, когда вы обрабатываете отправляемые XML-документы, и вы не можете просто исключить некоторые элементы (многие форматы допускают свободу элементов внутри них). Тогда NameTable внутри вашего парсера будет поврежден. В этом случае мы каждый раз создаем новый хэш-механизм:
public class RandomComparer : IEqualityComparer<string>
{
private int hashSeed = Environment.TickCount;
public bool Equals(string x, string y)
{
return x == y;
}
public int GetHashCode(string obj)
{
if(obj == null)
return 0;
int hash = hashSeed + obj.Length;
for(int i = 0; i != obj.Length; ++i)
hash = hash << 5 - hash + obj[i];
hash += (hash << 15) ^ 0xffffcd7d;
hash ^= (hash >>> 10);
hash += (hash << 3);
hash ^= (hash >>> 6);
hash += (hash << 2) + (hash << 14);
return hash ^ (hash >>> 16)
}
}
Это будет непротиворечиво в пределах данного использования, но не будет непротиворечивым от использования к использованию, поэтому злоумышленник не может создать ввод, чтобы заставить его быть DoSsed. Между прочим, NameTable не использует IEqualityComparer<T>, потому что он хочет иметь дело с массивами символов с индексами и длинами без построения строки без необходимости, но он делает что-то подобное.
Между прочим, в Java хэш-код для string указан и не изменится, но это может быть не так для других классов.
Редактировать: Проведя некоторое исследование общего качества подхода, принятого в ConsistentGuaranteedComparer выше, я больше не доволен наличием таких алгоритмов в моих ответах; хотя он служит для описания концепции, он не имеет такого хорошего распределения, как хотелось бы. Конечно, если кто-то уже реализовал такую вещь, то нельзя изменить ее без нарушения гарантии, но если бы я сейчас рекомендовал использовать эту мою библиотеку, написанную после указанного исследования , следующим образом:
public class ConsistentGuaranteedComparer : IEqualityComparer<string>
{
public bool Equals(string x, string y)
{
return x == y;
}
public int GetHashCode(string obj)
{
return obj.SpookyHash32();
}
}
Это для RandomComparer выше не так плохо, но также может быть улучшено:
public class RandomComparer : IEqualityComparer<string>
{
private int hashSeed = Environment.TickCount;
public bool Equals(string x, string y)
{
return x == y;
}
public int GetHashCode(string obj)
{
return obj.SpookyHash32(hashSeed);
}
}
Или для еще более сложной предсказуемости:
public class RandomComparer : IEqualityComparer<string>
{
private long seed0 = Environment.TickCount;
private long seed1 = DateTime.Now.Ticks;
public bool Equals(string x, string y)
{
return x == y;
}
public int GetHashCode(string obj)
{
return obj.SpookyHash128(seed0, seed1).GetHashCode();
}
}