Databases
StackOverflow2013
Postsdbo
POHashing a Tree Structure
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHashing a Tree Structure
    primarykey
    data
    text
    <p>I've just come across a scenario in my project where it I need to compare different tree objects for equality with already known instances, and have considered that some sort of hashing algorithm that operates on an arbitrary tree would be very useful.</p> <p>Take for example the following tree:</p> <pre> O / \ / \ O O /|\ | / | \ | O O O O / \ / \ O O </pre> <p>Where each <code>O</code> represents a node of the tree, is an arbitrary object, has has an associated hash function. So the problem reduces to: given the hash code of the nodes of tree structure, and a known structure, what is a decent algorithm for computing a (relatively) collision-free hash code for the entire tree?</p> <p>A few notes on the properties of the hash function:</p> <ul> <li>The hash function should depend on the hash code of every node within the tree as well as its position.</li> <li>Reordering the children of a node <em>should</em> distinctly change the resulting hash code.</li> <li>Reflecting any part of the tree <em>should</em> distinctly change the resulting hash code</li> </ul> <p>If it helps, I'm using C# 4.0 here in my project, though I'm primarily looking for a theoretical solution, so pseudo-code, a description, or code in another imperative language would be fine.</p> <hr> <h3>UPDATE</h3> <p>Well, here's my own proposed solution. It has been helped much by several of the answers here.</p> <p>Each node (sub-tree/leaf node) has the following hash function:</p> <pre><code>public override int GetHashCode() { int hashCode = unchecked((this.Symbol.GetHashCode() * 31 + this.Value.GetHashCode())); for (int i = 0; i &lt; this.Children.Count; i++) hashCode = unchecked(hashCode * 31 + this.Children[i].GetHashCode()); return hashCode; } </code></pre> <p>The nice thing about this method, as I see it, is that hash codes can be cached and only recalculated when the node or one of its descendants changes. (Thanks to vatine and Jason Orendorff for pointing this out).</p> <p>Anyway, I would be grateful if people could comment on my suggested solution here - if it does the job well, then great, otherwise any possible improvements would be welcome.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USNoldorin
    1. USNoldorin
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHashing a Tree Structure
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHashing a Tree Structure
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHashing a Tree Structure
      1. This table or related slice is empty.
      1. VTUpMod
    1. COcollision-free is unlikely
      singulars
      1. POHashing a Tree Structure
      1. USEli Bendersky
    2. CO@Eli Bendersky: Indeed. I've modified the question to imply "as collision-free as possible".
      singulars
      1. POHashing a Tree Structure
      1. USNoldorin
    3. CONone of these answers do a great job of explaining it, but a tree is just a tuple (node-local data, subtree0, subtree1, ...). Tuples are hashable. Done. See vatine's and pnm's answers for more details.
      singulars
      1. POHashing a Tree Structure
      1. USJason Orendorff
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload