Эффективное хеширование дерева

Question

Я часто искал большой лес для множества разных фрагментов дерева и хотел бы, чтобы часть проверки равенства выполнялась быстрее, чем O (N). Идея заключается в «хэш-фрагменте» фрагментов дерева и рассматривает конфликты как равенство.

Моя древовидная структура представляет собой стандартный объект Node с полем значений int и дочерним полем. Я хотел бы, чтобы хэш-значение дерева, укорененного на определенном узле, зависело только от его дочерних элементов, и что, учитывая, что хэш-код ребенка изменился, относительно дешевого обновления можно применить к хэш-коду родителя ребенка. Если мы сможем выполнить операцию обновления O (1), то изменение значения на листовом узле приведет к появлению цепной реакции O (log n) вверх по дереву.

Я прочитал следующий вопрос: Hashing a Tree Structure

, который дает большой ответ. Однако у меня возникают проблемы с алгоритмом. Поскольку строки неотменяемы в Java, обновление в дочернем узле будет переводить на операцию обновления файла() в родительском элементе. Пожалуйста, исправьте меня здесь, если кажется, что я неправильно понял ответ выше.

Что такое возможная хеш-функция для того, что я ищу?

Answer 1

Если я правильно понял вас, вам не нужен хеш, если вы просто хотите проверить равенство двух деревьев. Да! вам понадобится хорошая хеширующая функция, если вы помещаете свое дерево в какую-либо структуру данных коллекции и пытаетесь получить к ним доступ с помощью некоторых ключей. «Идея заключается в« хэш-фрагменте »фрагментов дерева и рассматривать столкновение как равенство» Это неверный оператор, и вы не должны этого делать. Тот же хеш-код не означает равенства вообще. Концепция равенства не имеет ничего общего с хешированием функции. Хеширование выполняется для более быстрого поиска/доступа элементов в какой-либо коллекции, например hashmap или hashtable.

Answer 2

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

class Node{ 
    int value; 
    List<Node> children; 

    @Override 
    public int hashCode(){ 
     int childCount = children.size(); 
     int sum = 0; 
     for Node child : children: 
      sum += child.hashCode(); 
     int hashCode = childCount * 2^31 + value * 2^23 + sum * 2^13; 

     return hashCode; 
    } 
} 

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