标签: hashtree

我正在尝试使用自定义类作为关键字unordered_map,如下所示:

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector<int> v) {
        sort(v.begin(), v.end());
        a = v[0];       
        b = v[1];       
        c = v[2];       
    }

    bool operator==(Node i) {
        if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    unordered_map<Node, int> m;    

    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(9);
    Node n(v);

    m[n] = 0; …

我刚刚发现了AWS Glacier服务,并希望编写一个小型 Python应用程序来通过REST API上传文件.我看了看所需的标题,偶然发现了x-amz-sha256-tree-hash.我需要计算整个文件的SHA-256哈希值以及每个1 MB块的所有哈希值的父哈希值.这导致以下树:

(图片来自这里)

我已经创建了一个读取1 MB块的函数和一个即时计算其哈希值的类,但后来我完全挣扎:

在我的应用程序中,我创建了一个类chunk,它接受数据并计算__init__方法中的哈希值,并保存父项和子项(如常规树).当用户打开文件时,将使用各自的哈希值(在此示例中为7个块实例)正确生成这些块实例.

现在我有两个相互联系的大问题:

1. 如何反向构建这棵树？我基本上需要为最低层上的每两个块实例创建一个新块,并根据这两个哈希值计算哈希值.但是我在哪里存储那个父母？在父母的孩子和反向树行走？
2. 如何与奇数个孩子一起工作？如果我有一个遍历每个父层的算法,那么我会错过最后一个(0.5 MB)块.

我在SO上查看了这个主题但是这个方法只适用于偶数儿童计数,但并不总是这样.

你能帮我找到解决这个问题的方法/算法/方法吗？

提前致谢!

保罗

Merkle树(又名哈希树)用于"Cassandra"和"Dynamo"中的数据同步.

与任何散列函数一样,不同数据可能具有相同的散列值:

存在一个x和y,其中[y!= x]但[hash(x)= hash(y)]

随着NOSQL中的"大数据"增长,遇到此类数据的概率变得更高.

这意味着随着数据集变大,几乎可以肯定Merkle树中的不同节点将产生相同的父哈希.

在这种情况下,当群集中的两台不同的机器遍历他们的merkle树时,他们会得到误报,他们的数据是一致的.如果没有更多数据写入树的该分支,则计算机将永远保持不同步.

这是怎么处理的？

我想实现一个需要使用哈希树的算法.什么是一些好的,易于理解的Java哈希树实现？是否有互联网上的书籍,网站或PDF可以很好地解释哈希树的工作方式以及如何实现它？

与哈希表相比，使用Merkle 树有什么优点？哈希表是2层结构，Merkle树是log n层结构。两者都可用于验证其中一个节点是否已更改。哈希列表将更快地完成此任务。那么为什么要使用默克尔树呢？