Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, hardcase, Вы писали:
H>>А я вот умножение на простые числа использую.
А>А почему именно на простые?
Допустим есть поля: a, b, c.
Примерный алгоритм алгоритм:
var h = K;
h = h * T + a.GetHashCode();
h = h * T + b.GetHashCode();
h = h * T + c.GetHashCode();
return h;
где K и T — простые числа, также можно использовать взаимно-простые числа.
Использование достаточно больших простых чисел позволяет лучше "перемешивать" биты, тем самым мы минимизируем возможное число коллизий.
"Исключающее или" также неплохо перемешивает биты, да только имеет побочный эффект. Если a и b — равны, то a xor b даст 0, это используется например для загрузки константы 0 в регистр в x86 архитектурах.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[4]: Почему для реализации GetHashCode так часто использую
Здравствуйте, hardcase, Вы писали:
H>>>А я вот умножение на простые числа использую. А>>А почему именно на простые? H>Допустим есть поля: a, b, c. H>Примерный алгоритм алгоритм:
H>var h = K;
H>h = h * T + a.GetHashCode();
H>h = h * T + b.GetHashCode();
H>h = h * T + c.GetHashCode();
H>return h;
H>где K и T — простые числа, также можно использовать взаимно-простые числа.
А какой тип имеют K и T? Как [без ксора] побеждается возможность переполнения?
Help will always be given at Hogwarts to those who ask for it.
Re[5]: Почему для реализации GetHashCode так часто использую
Здравствуйте, Аноним, Вы писали:
А>Почему для реализации GetHashCode так часто используют XOR ?
XOR — это простая операция, которая позволяет перемешать биты. Т.е. это просто один из способов получения хеша.
При этом xor обычно используют в паре с другой операцией, например умножением на простые числа, сложением и т.д.
Домножение обычно используется, чтобы получить более хорошее распределение и соответственно меньше коллизий хеш-функции.
При использовании простых чисел в хеш-алгоритмах получается более хорошее распределение результата хеш-функции.
Но вообще xor это не единственно верный путь написания хеш-функции. Например можно использовать умножение + сложение. Главное не использовать одну операцию, иначе будет много коллизий. Поэтому, повторюсь, обычно используют пару операций, одной из которых часто является xor в виду своей простоты и способности за раз перемешать много битов.
На сегодняшний день уже выведены наиболее эффективные алгоритмы хеш-функций. У большинства наиболее популярных хешей разница находится в пределах 10-20% по скорости и по числу коллизий.
Здравствуйте, MozgC, Вы писали:
MC>Чтобы каждый раз не вспоминать как правильно написать реализацию GetHashCode() и не сделать ошибки можно написать generic реализацию.
Это все здорово, но только если мы имеем дело с типами-значениями, для ссылочных типов (например строк), которые вообще-то могут быть null-ами нужно использовать System.Collections.Generic.EqualityComparer.Default.
Кстати, если мне не изменяет память аналогичный алгоритм подсчета хэша реализует компилятор C# для анонимных типов.
ЗЫ. В Nemerle есть соответствующий макрос называется StructuralHashCode.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[3]: Почему для реализации GetHashCode так часто использую
Здравствуйте, hardcase, Вы писали:
MC>>Чтобы каждый раз не вспоминать как правильно написать реализацию GetHashCode() и не сделать ошибки можно написать generic реализацию.
H>Это все здорово, но только если мы имеем дело с типами-значениями, для ссылочных типов (например строк), которые вообще-то могут быть null-ами нужно использовать System.Collections.Generic.EqualityComparer.Default.
Для чего?
Help will always be given at Hogwarts to those who ask for it.
Re[4]: Почему для реализации GetHashCode так часто использую
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, hardcase, Вы писали:
MC>>>Чтобы каждый раз не вспоминать как правильно написать реализацию GetHashCode() и не сделать ошибки можно написать generic реализацию.
H>>Это все здорово, но только если мы имеем дело с типами-значениями, для ссылочных типов (например строк), которые вообще-то могут быть null-ами нужно использовать System.Collections.Generic.EqualityComparer.Default.
_FR>Для чего?
MozgC привел хэлпер который считает хэш на генериках. Если передать null, его методы навернуться с NRE.
Чтобы означенная универсальная версия работала нужно обращаться к GetHashCode посредством:
Здравствуйте, hardcase, Вы писали:
MC>>>>Чтобы каждый раз не вспоминать как правильно написать реализацию GetHashCode() и не сделать ошибки можно написать generic реализацию. H>>>Это все здорово, но только если мы имеем дело с типами-значениями, для ссылочных типов (например строк), которые вообще-то могут быть null-ами нужно использовать System.Collections.Generic.EqualityComparer.Default. _FR>>Для чего? H>MozgC привел хэлпер который считает хэш на генериках. Если передать null, его методы навернуться с NRE. H>Чтобы означенная универсальная версия работала нужно обращаться к GetHashCode посредством:
По спецификации equality-компараторов они должны ANE бросать при null-аргументе (здесь и здесь)
Так что то, что они что-то делают, является скорее удобнейшей фичей, эмулировать которую очень просто любой константой или напрмер через typeof(T).GetHashCode(). Но рассчитывать на то, что для null они вернут какое-то значение я б не рекомендовал.
Help will always be given at Hogwarts to those who ask for it.
Re[6]: Почему для реализации GetHashCode так часто использую
Здравствуйте, _FRED_, Вы писали:
_FR>По спецификации equality-компараторов они должны ANE бросать при null-аргументе (здесь и здесь) Я и не подозревал.
_FR>Так что то, что они что-то делают, является скорее удобнейшей фичей, эмулировать которую очень просто любой константой или напрмер через typeof(T).GetHashCode(). Но рассчитывать на то, что для null они вернут какое-то значение я б не рекомендовал.
Ну что-ж, это тот редкий случай, когда отступление от спецификации есть наиболее ожидаемое поведение системы.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[3]: Почему для реализации GetHashCode так часто использую
Здравствуйте, hardcase, Вы писали:
H>Это все здорово, но только если мы имеем дело с типами-значениями, для ссылочных типов (например строк), которые вообще-то могут быть null-ами нужно использовать System.Collections.Generic.EqualityComparer.Default.
EqualityComparer в некоторых ситуациях может не подходить по производительности.
Поэтому сделал так:
public static class HashHelper
{
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
where T1 : class
where T2 : class
{
unchecked
{
return 31
* (arg1 != null ? arg1.GetHashCode() : 0)
+ (arg2 != null ? arg2.GetHashCode() : 0);
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
where T1 : class
where T2 : class
where T3 : class
{
unchecked
{
int hash = (arg1 != null ? arg1.GetHashCode() : 0);
hash = 31 * hash + (arg2 != null ? arg2.GetHashCode() : 0);
return 31 * hash + (arg3 != null ? arg3.GetHashCode() : 0);
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
where T1 : class
where T2 : class
where T3 : class
where T4 : class
{
unchecked
{
int hash = (arg1 != null ? arg1.GetHashCode() : 0);
hash = 31 * hash + (arg2 != null ? arg2.GetHashCode() : 0);
hash = 31 * hash + (arg3 != null ? arg3.GetHashCode() : 0);
return 31 * hash + (arg4 != null ? arg4.GetHashCode() : 0);
}
}
public static int GetHashCode<T>(T[] list)
where T : class
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + (item != null ? item.GetHashCode() : 0);
}
return hash;
}
}
public static int GetStructArrayHashCode<T>(T[] list)
where T : struct
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
public static int GetHashCode<T>(IEnumerable<T> list)
where T : class
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + (item != null ? item.GetHashCode() : 0);
}
return hash;
}
}
public static int GetStructEnumerableHashCode<T>(IEnumerable<T> list)
where T : struct
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
/// <summary>
/// Gets a hashcode for a collection for that the order of items does not matter.
/// So {1, 2, 3} and {3, 2, 1} will get same hash code.
/// </summary>public static int GetHashCodeForOrderNoMatterCollection<T>(IEnumerable<T> list)
where T : class
{
unchecked
{
int hash = 0;
int count = 0;
foreach (var item in list)
{
if(item != null)
hash += item.GetHashCode();
count++;
}
return 31 * hash + count.GetHashCode();
}
}
/// <summary>
/// Gets a hashcode for a collection for that the order of items does not matter.
/// So {1, 2, 3} and {3, 2, 1} will get same hash code.
/// </summary>public static int GetHashCodeForOrderNoMatterCollectionOfStructs<T>(IEnumerable<T> list)
where T : struct
{
unchecked
{
int hash = 0;
int count = 0;
foreach (var item in list)
{
hash += item.GetHashCode();
count++;
}
return 31 * hash + count.GetHashCode();
}
}
/// <summary>
/// Alternative way to get a hashcode is to use a fluent interface like this:<br />
/// return 0.CombineHashCode(field1).CombineHashCode(field2).CombineHashCode(field3);
/// </summary>public static int CombineHashCode<T>(this int hashCode, T arg)
where T : class
{
unchecked
{
return 31*hashCode + (arg != null ? arg.GetHashCode() : 0);
}
}
/// <summary>
/// This method accepts two hashcodes and returns resulting hashcode. We avoid generic type
/// arguments here, because it may be unnacceptable for perfomance to pass big structs to the method
/// </summary>public static int CombineHashCode(this int hashCode1, int hashCode2)
{
unchecked
{
return 31 * hashCode1 + hashCode2;
}
}
}
Соответственно, если у нас все поля — классы, то пишем так:
(здесь и здесь)
Я и не подозревал.