есть один тест, с использованием словаря new Dictionary<long, long>(comparer)
где
var comparer = new EqualityComparer();
//...
public class EqualityComparer : IEqualityComparer<long>
{
public int GetHashCode(long obj)
{
return ((int)obj) ^ (int)(obj >> 32);//too slow - default
}
//...
в общем ключи подставляются в словарь такие что их хеш вызывает много коллизий, помогите придумать другую функцию хеширования
Здравствуйте, -rsdn-, Вы писали:
R>есть один тест, с использованием словаря new Dictionary<long, long>(comparer)
R>в общем ключи подставляются в словарь такие что их хеш вызывает много коллизий, помогите придумать другую функцию хеширования
1. Проблема точно в коллизиях хэша, а не в самом алгоритме/выбранном контейнере?
2. Если не подходит простой xor — можно взять классический
public static int CombineHashCodes(int h1, int h2)
{
return (h1 << 5) + h1 ^ h2;
}
(используется в System.Tuple и в ряде других типов) или посмотреть на типовые наборы данных и подобрать для них любую другую функцию.
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, -rsdn-, Вы писали:
R>>есть один тест, с использованием словаря new Dictionary<long, long>(comparer)
R>>в общем ключи подставляются в словарь такие что их хеш вызывает много коллизий, помогите придумать другую функцию хеширования
S>1. Проблема точно в коллизиях хэша, а не в самом алгоритме/выбранном контейнере?
S>2. Если не подходит простой xor — можно взять классический
S>S> public static int CombineHashCodes(int h1, int h2)
S> {
S> return (h1 << 5) + h1 ^ h2;
S> }
S>
S>(используется в System.Tuple и в ряде других типов) или посмотреть на типовые наборы данных и подобрать для них любую другую функцию.
Tuple круто, но у меня long obj параметр хэш функции. дело в том что система которая тестирует код с багами... поэтому можно вести верное решение, ответ будет вроде Runtime Error. решилось все, я использовал | (или) вместо ^. + не прошел, обычно выдавало Runtime Error, хотя я думаю это означало time limit
Здравствуйте, -rsdn-, Вы писали:
R>есть один тест, с использованием словаря new Dictionary<long, long>(comparer)
R>где
R>R>var comparer = new EqualityComparer();
R>//...
R> public class EqualityComparer : IEqualityComparer<long>
R> {
R> public int GetHashCode(long obj)
R> {
R> return ((int)obj) ^ (int)(obj >> 32);//too slow - default
R> }
R>//...
R>
R>в общем ключи подставляются в словарь такие что их хеш вызывает много коллизий, помогите придумать другую функцию хеширования
в общем случае не получится.
нужны грязные подробности: распределение кючей и размер хешмапа
... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>
