Задать вопрос
@daniil14056

Как хешировать в хеш таблице узлы дерева?

Или какой другой способ или подход пока не думал. Каждый узел имеет вычисленное значение хешкода.
Как сделать быстрый поиск ключа по значению, как переопределить Equals? Без рекурсии?
// код тут написал примерный
  class A{
  A nodeChild1; 
  A  nodeChild2;
  int data; //  только на самом вверху дерева , 2^(n-1)-1 узлов 
 // int casheHashCode; 

 private bool _equalrecursion(A? x, A? y)
   {
 if(x.GetHashCode()==y.GetHashCode(){
        if(x.Child1.GetHashCode()==y.Child1.GetHashCode())
             if(x.Child2.GetHashCode()==y.Child2.GetHashCode()){
                  if(_equalrecursion(x.Child1,y.Child1)
                             if(x.Child1!=null...)
                           return  _equalrecursion(x.Child2,y.Child2)
                             else return x.Value==y.value;
}
}
return false;
} public bool Equals(А? x, А? y)=>_equalrecursion(A,Б);
}

В таком решении для того что бы проверить 2 равных узла будет 2^n сравнений выдающих true
Как можно сократить число вычислений допутсим до 3, можно составить такую хеш функцию, что бы гарантировано(или с какой-то высокой вероятностью), не было коллизий между узлами на соседней высоте. Типа что бы хеш дочерних узлов влиял на хеш узла?
Что бы допустим для узла с хешом S на высоте- 10 если бы нашелся бы узел с хешом S, то он мог быть либо искомым значением, либо узлом на какой-то другой высоте, допустим 20, и легко не выдерживал проверку lдочерних узлов.
Типа что бы максимум проверить сам узел, и 2 его потомков? А п коллизии хешей могут быть только у узлов на 2 порядка выше меньше.
Может как-то можно хеш-функцию составить хитро, сдвинуть байты( Какие есть статьи по написанию хеш функций, как там подбираются параметры типа обычно что-то такое. a*434334^b*1122121... как эти числа подбираются)

Из задачи, Ключ в Dictionary сравнивается по значению, полей. Так как каждый раз перед поиском создается объект из комбинации узлов. Задача проверить, если такая комбинация узлов в хештаблице? Избежав коллизий.
Поиск должен быть быстрым, а все остальное неважно. Пока у мен решение(не решение), рекурсивное сравнение всех узлов. Но хотелось бы ограничиться так что бы проверки детей было достаточно.( Из условия видно, что число вариантов узлов на каждой высоте дерева известен 2^n, вот можно составить так функцию что бы все комбинации давали достоверно разный результат, допустим на высоте дерева 10, может быть 1024 вариантов узлов, и 1024^2 их вариантов. (тут возможно я сам ответил на вопрос, для 2^16 комбинаций, которые укладываются в 32 бита) Может там как-то индексировать, и хранить индексы.
Да и дерево только растет, все значения уникальны, а каждый верхний узел на высоте N может иметь только узлы высотой N-1
И вопрос, к примеру для каждой высоты дерева придумать уникальную хеш функцию. вычисления ее родителя, таким образом надо 32 функции придумать,
К примеру для дерева высотой 4
Для 2 высоты (2^2) узла будет искаться f1(x1,x2)
Для 3 высоты (2^3) узла будет искаться f2(x1',x2')=f2( f1(x11,x21),f1(x21,x22);
И так далее.
И можно ли подобрать так, что бы гарантировать что какая-нибудь f4(x1,x2) != f7(x1,x2)?
  • Вопрос задан
  • 163 просмотра
Подписаться 2 Сложный Комментировать
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Итак, у вас ключи - какая-то древовидная структура и вам надо быстро определять, а есть ли такая структура в таблице. Я правильно понял?

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

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

Или можно тупо записать вашу структуру данных в строку (Например, расставив скобки вокруг каждого поддерева вроде "(a(b)(ccc(dd))" - это узел a, у которого есть дети b и ccc, у последнего есть ребенок dd) и потом как угодно хешировать уже строку, тогда ничего самостоятельно реализовавать ничего вообще не надо (to_json и hash от строки возможно уже есть).
Ответ написан
mayton2019
@mayton2019
Bigdata Engineer
Дружище тебе не надо портить дерево. Оно и так хорошо.
Просто заведи отдельную хеш-таблицу и трекай две структуры
одновременно.

LRU например так и делает. Цепной список + Hashtable.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы