Краткий ответ: Да.
Но короткие ответы не забавны, не так ли?
При реализации 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)
}
}
Это будет согласовано в пределах данного использования, но не согласовано от использования к использованию, поэтому злоумышленник не может создать входные данные, чтобы заставить их быть DoS-отказом. Между прочим, 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();
}
}
person
Jon Hanna
schedule
12.01.2012
