Наиболее эффективный способ получения хэшируемого объекта для произвольного набора ключей (произвольного типа данных)

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

Пока лучший алгоритм, который я придумал, состоит в том, чтобы взять ToHashCode() для каждого поля, а затем присоединить полученные хэш-коды к строке, используя какой-то символ разделителя (например, "|" ), а затем использовать это в результате получается строка как уникальный ключ для словаря.

Кто-нибудь знает более эффективный способ сделать это? Я думал, что, возможно, есть способ взять хэш-код каждого поля и выполнить некоторую математическую операцию, чтобы объединить их в уникальное количество хэшируемых чисел, но это было всего лишь предположение.

Спасибо за любую помощь.

EDIT: Я думаю, люди могут быть в замешательстве относительно того, что я имею в виду. Кортежи не будут работать в этой ситуации, потому что мне нужно произвольное количество полей, которые будут объединены в один хешируемый объект. Количество полей известно только во время выполнения, а не во время разработки.

Другое решение, связанное с математическим объединением всех хэш-кодов в новый хэш-код, также не будет работать, потому что мне нужен объект, который можно использовать в качестве ключа в словаре. Я считаю, что использование хэш-кода в качестве ключа в словаре очень опасно.

ИЗМЕНИТЬ 2: Подумав об этом, я думаю, что мое оригинальное решение не очень хорошее. В предельном случае, когда есть одно поле, мое решение выродилось на то, чтобы помещать строчную версию хэш-кода в словарь.

Я думаю, возможно, лучшим решением является создание нового типа, который перечислит в своем конструкторе и реализует GetHashCode(). Функция GetHashCode() затем пробивает каждое значение перечислимого и выполняет обычный тип логики аккумулятора в хэш-кодовых функциях. Таким образом, объект может застревать в словаре, hashset и т.д. И вести себя так, как вы ожидали.

4 ответа

Ключевым моментом здесь было осознание того, что любой произвольно подобранный набор объектов можно хэшировать, просто рассматривая его как IEnumerable, чей хэш-код зависит от содержимого перечисления.

Для этого я просто создал класс ValueAwareEnumerable, который реализует IEnumerable. Этот класс перечислит в своем единственном конструкторе. Затем он переопределяет GetHashCode() и Equals(), чтобы они зависели от содержимого перечислимого. Метод GetHashCode просто:

public override int GetHashCode()
{
 unchecked
 {
 int hash = 983;
 foreach (var item in _wrappedEnumerable)
 if(item != null)
 hash = hash * 457 + item.GetHashCode();
 return hash;
 }
}

и равно:

public override bool Equals(object obj)
 {
 if (ReferenceEquals(null, obj)) return false;
 if (ReferenceEquals(this, obj)) return true;
 if (obj.GetType() != typeof (ValueAwareEnumerable<t>)) return false;
 return Equals((ValueAwareEnumerable<t>) obj);
 }
 public bool Equals(ValueAwareEnumerable<t> other)
 {
 if (ReferenceEquals(null, other)) return false;
 if (ReferenceEquals(this, other)) return true;
 return _wrappedEnumerable.SequenceEqual(other); 
 }
</t></t></t>

Опасность здесь заключается в том, что она зависит от порядка перечислимого. Если необходимо, можно сделать его независимым от порядка, просто сделав GetHashCode() и Equals() отсортированным перечислимым перед повторением через него.

Чтобы закончить, просто добавьте метод расширения где-нибудь для хорошей меры:

public static IEnumerable<t> ToValueAwareEnumerable<t>(this IEnumerable<t> enumerable)
{
 return new ValueAwareEnumerable<t>(enumerable);
}
</t></t></t></t>

И вы можете делать такие вещи, как:

var dictionary = new Dictionary<ienumerable<int>>();
var veryImportantNumbers = new[] { 5, 8, 13, 20, 3, 100, 55, -5, 0 };
dictionary[veryImportantNumbers.ToValueAwareEnumerable()] = "Pastrami";
</ienumerable<int>

Это будет работать для любого типа данных и даже смешанных типов данных, если вы рассматриваете их как IEnumerable<object>.</object>


Самый простой способ - использовать Tuple <> для объединения хэш-кодов ваших полей.

var dict = new Dictionary<tuple<int, string="">, MyClass>();
dict[Tuple.Create(myObj.Num, myObj.Str)] = myObj;
</tuple<int,>

Вы также можете комбинировать хеши сами, но вы рискуете ошибиться.


Я думал, возможно, есть какой-то способ взять хэш-код каждого поля и выполнить некоторую математическую операцию, чтобы объединить их в уникальное количество хэшируемых чисел, но это было просто предположение.

Да, это именно то, что вы должны делать. Здесь общая реализация:

unchecked
{
 int hash = 983;
 hash = hash * 457 + x.GetHashCode();
 hash = hash * 457 + y.GetHashCode();
 hash = hash * 457 + (z != null ? z.GetHashCode() : 0);
 return hash;
}

Обратите внимание, что вы не должны использовать хеш-код в качестве словарного ключа, поскольку он не будет уникальным (столкновения, как правило, будут редкими, но они не невозможны). Если вы хотите использовать сам объект как ключ, вы также должны переопределить Equals, чтобы if x.Equals(y), тогда x.GetHashCode() == y.GetHashCode() (обратное не должно быть истинным)


В этом случае вы не можете безопасно использовать стандартную таблицу (если вы не можете предоставить дополнительные ограничения).

Дополнительная информация необходима, чтобы обеспечить хорошую альтернативу, но у меня есть одно предложение ниже. Дополнительная информация может включать:

  • Use Case (как вы используете систему поиска, почему вам нужны поля в ключе)
  • Являются ли поля, которые могут быть объединены, определены во время разработки (обратите внимание: это не то, сколько или какие поля объединяются. Вместо этого оно относится к тому, где/когда/как эти поля определены так, что их можно объединить).
  • Если поля определены во время выполнения, сколько полных полей есть (количество всех полей).
  • Какие данные хранятся для этого странного ключа?
  • Как часто будут записываться/читаться данные?

Быстрое решение: Используйте вложенные хэш-таблицы. Для этого решения вам понадобятся ваши поля для сортировки. Первое поле является ключом для первой таблицы. Это укажет на другую хеш-таблицу, в которой вторым будет ключ. Это будет происходить для каждого поля, пока не появится последнее поле. Последнее поле будет ключевым для данных, которые вы ищете. Чтобы выполнить эту работу, вам нужно будет определить пользовательский объект, у которого есть свойство для данных и свойство для хеш-таблицы.

В то время как это одобренное решение, которое использует существующие структуры данных .net, оно не будет очень эффективным. Для более эффективного решения просьба предоставить дополнительную информацию.

licensed under cc by-sa 3.0 with attribution.