Общий словарь и создание хэш-кода для ключа из нескольких частей

Question

У меня есть объект с ключом из нескольких частей, и я изо всех сил пытаюсь найти подходящий способ переопределить GetHashCode. Пример того, как выглядит класс:

public class wibble{
   public int keypart1 {get; set;}
   public int keypart2 {get; set;}
   public int keypart3 {get; set;}
   public int keypart4 {get; set;}
   public int keypart5 {get; set;}
   public int keypart6 {get; set;}
   public int keypart7 {get; set;}
   public single value {get; set;}
}

Обратите внимание, что почти в каждом экземпляре класса не более 2 или 3 клавиш имеют значение больше 0.

Есть идеи, как лучше создать уникальный хэш-код в этой ситуации?

Я также занимался созданием ключа, который не был бы уникальным, но распределял объекты равномерно между корзинами словарей, а затем сохранял объекты с совпадающими хэшами в List <> или LinkedList <> или SortedList <>.
Есть мысли по этому поводу?

Answer 1

Решарпер дает вам следующее:

    public override int GetHashCode()
    {
        unchecked
        {
            int result = keypart1;
            result = (result * 397) ^ keypart2;
            result = (result * 397) ^ keypart3;
            result = (result * 397) ^ keypart4;
            result = (result * 397) ^ keypart5;
            result = (result * 397) ^ keypart6;
            result = (result * 397) ^ keypart7;
            result = (result * 397) ^ (value != null ? value.GetHashCode() : 0);
            return result;
        }
    }

Я предположил, что single является ссылочным типом. Обратите внимание на блок unchecked для предотвращения исключений переполнения.

Answer 2

Самый простой способ - использовать XOR.Чуть лучше метод, рекомендованный Джошем Блохом в Effective Java.См. здесь .

Относительно использования хеш-кода: ожидается, что иногда будут возникать коллизии, и это не должно вызывать проблем (слишком большое количество коллизий сделает ваш код медленным, ноэто все еще должно работать).Если у вас может быть несколько значений для одного и того же ключа, вы должны использовать что-то вроде Dictionary<Foo, List<Bar>> или Lookup.Если хэши ключей случайно сталкиваются, но ключи разные, вам не нужно делать ничего особенного.Dictionary автоматически обрабатывает эту ситуацию, если ваша реализация Equals верна.

Answer 3

Хеш-код не должен быть уникальным. Поскольку хеш-код всего 32 бита, даже получить уникальный код невозможно, если данные больше 32-х бит.

Единственное требование - чтобы хеш-код всегда был одинаковым для любого конкретного набора соответствующих данных в классе. Это означает, что работает даже постоянный хеш-код:

public int GetHashCode() {
   return 1;
}

Это не очень хорошо, так как дистрибутив ужасен, но все же работает.

Вы можете начать с очень простой реализации хеш-кода, например:

public int GetHashCode() {
   return
     keypart1 ^ keypart2 ^ keypart3 ^ keypart4 ^
     keypart5 ^ keypart6 ^ keypart7 ^ value.GetHashCode();
}

Для чего-то более сложного вы можете умножить на простое число:

public int GetHashCode() {
   return
     ((((((keypart1 * 13 + keypart2) * 13 + keypart3) * 13 + keypart4) * 13 +
     keypart5) * 13 + keypart6) * 13 + keypart7) * 13 + value.GetHashCode();
}

Answer 4

Идя по пути преждевременной оптимизации, вы можете попробовать

public override int GetHashCode()
{
    return 
       keypart1.GetHashCode() ^
       keypart2.GetHashCode() ^
       keypart3.GetHashCode() ^
       keypart4.GetHashCode() ^
       keypart5.GetHashCode() ^
       keypart6.GetHashCode() ^
       keypart7.GetHashCode();
}

Интересно в сторону: У меня нет IDE, удобной для тестирования прямо сейчас, но если я правильно помню, получение хэш-кода типа int просто возвращает сам объект int. Это означает, что если это правда, вы можете исключить все эти вызовы GetHashCode.

Answer 5

Как сказал keltex, но с одним важным дополнением: если вы переопределяете GetHasCode, вы также должны переопределять equals! Отсюда: http://msdn.microsoft.com/en-us/library/ms173147(VS.80).aspx

public override bool Equals(System.Object obj)
{
    // If parameter is null return false.
    if (obj == null)
    {
        return false;
    }

    // If parameter cannot be cast to wibblereturn false.
    wibble p = obj as wibble;
    if ((System.Object)p == null)
    {
        return false;
    }

    // Return true if the fields match:
    return (Your comparison);
}

Answer 6

Вы можете сделать что-то очень простое, как это:

public override int GetHashCode()
{
    return (keypart1.ToString() + ":"
      keypart2.ToString() + ":" + ... etc).GetHashCode();
}

Существуют численные методы, которые, вероятно, быстрее, но это сделало бы работу без преждевременной оптимизации.