Хеширование древовидной структуры ⇐ C#

[Anonymous]

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

Возьмем, к примеру, следующее дерево:

O
/ \
/ \
O O
/|\ |
/ | \ |
O O O O
/ \
/ \
O O


Где каждый O представляет собой узел дерева, является произвольным объектом, имеет связанную с ним хеш-функцию. Таким образом, проблема сводится к следующему: учитывая хэш-код узлов древовидной структуры и известную структуру, какой алгоритм является подходящим для вычисления (относительно) свободного от коллизий хеш-кода для всего дерева?

Несколько замечаний о свойствах хеш-функции:

• Хеш-функция должна зависеть от хеш-кода каждого узла в дереве, а также его положение.
• Переупорядочение дочерних узлов должно заметно изменить результирующий хэш-код.
• Отражение любой части дерева должно явно изменить результирующий хеш-код

Если это помогает, я использую C# 4.0 в своем проекте, хотя в первую очередь ищу теоретическое решение, поэтому псевдокод, описание или код на другом императивном языке подойдут.



ОБНОВЛЕНИЕ

Ну, вот мое собственное решение. Несколько ответов здесь очень помогли.

Каждый узел (поддерево/листовой узел) имеет следующую хеш-функцию:

Код: Выделить всё

public override int GetHashCode()
{
int hashCode = unchecked((this.Symbol.GetHashCode() * 31 +
this.Value.GetHashCode()));
for (int i = 0; i < this.Children.Count; i++)
hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode());
return hashCode;
}

На мой взгляд, в этом методе приятно то, что хеш-коды можно кэшировать и пересчитывать только при изменении узла или одного из его потомков. (Спасибо Ватину и Джейсону Орендорффу за указание на это).

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

Подробнее здесь: https://stackoverflow.com/questions/198 ... -structure