如何計算樹的哈希值

計算Tree的哈希值的最佳方法是什麼？如何計算樹的哈希值

我需要比較幾棵樹之間的相似度O（1）。現在，我想要預先計算哈希值並在需要時進行比較。但後來我意識到，散列樹不同於散列序列。我無法想出一個好的散列函數。

什麼是計算樹的散列值的最佳方法？

注：我將實施在C函數/ C++

來源

2013-08-24 Bidhan Roy

你在這裏定義的等價樹是什麼？ –

類似的樹不一定會有相似的散列。如果你想檢查樹的平等性，比較哈希是好的，但大多數哈希解決方案不適合計算相似性。 –

如果對於任意節點r1（r1屬於T1）和r2（r2屬於T2），如果我們認爲r1是T1的根，而r2是T2的根，那麼兩棵樹T1和T2是等價的，其餘樹可以以T1和T2彼此同構的方式重新排列。 –

兒童哈希應該由質數&添加依次相乘。節點本身的哈希值應該乘以不同的素數&。

緩存整個樹的哈希值 - 如果我有一個包含AST的包裝器對象，我寧願將它緩存在AST節點之外。

public class RequirementsExpr { 
    protected RequirementsAST ast; 
    protected int hash = -1; 

    public int hashCode() { 
     if (hash == -1) 
      this.hash = ast.hashCode(); 
     return hash; 
    } 
} 

public class RequirementsAST { 
    protected int nodeType; 
    protected Object data; 
    // - 
    protected RequirementsAST down; 
    protected RequirementsAST across; 

    public int hashCode() { 
     int nodeHash = nodeType; 
     nodeHash = (nodeHash * 17) + (data != null ? data.hashCode() : 0); 
     nodeHash *= 23;   // prime A. 

     int childrenHash = 0; 
     for (RequirementsAST child = down; child != null; child = child.getAcross()) { 
      childrenHash *= 41; // prime B. 
      childrenHash += child.hashCode(); 
     } 
     int result = nodeHash + childrenHash; 
     return result; 
    } 
}

這樣做的結果，是在不同的位置該子/後代節點總是由不同的因素相乘;並且節點本身總是與任何可能的子/後代節點乘以不同的因子。

請注意，其他素數也應該用於構建節點數據本身的nodeHash。這有助於避免例如。 nodeType的不同值與data的不同值相沖突。

在32位散列的限制範圍內，該方案總體上爲樹形結構（例如，轉置兩個兄弟）或值的任何差異提供了非常高的唯一性機會。

一旦計算出來（在整個AST上）哈希效率非常高。

來源

2013-08-24 11:26:00

我建議將樹轉換爲規範序列並散列序列。（轉換的細節取決於您對等效的定義，例如，如果樹是二叉搜索樹並且等價關係是結構性的，那麼轉換可以按照預先排序的順序枚舉樹，因爲二叉搜索樹的結構可以從前序枚舉中恢復。）

Thomas's answer乍一看，將多元多項式與每棵樹相關聯，並在特定位置評估多項式。目前有兩個步驟必須憑信仰假設;首先是地圖不會將不等價的樹發送給相同的多項式，其次是評估方案不會引入太多的衝突。我目前無法評估第一步，儘管有一些合理的等效定義可以從兩變量多項式中重建。第二個理論上沒有問題，但可以通過Schwartz - Zippel來完成。

來源

2013-08-24 14:46:53

如何計算樹的哈希值

回答

相關問題