问题标签 [hashtree]

我想实现一个需要使用哈希树的算法。有哪些好的、易于理解的 Java 哈希树实现？Internet 上是否有书籍、网站或 PDF 可以很好地解释哈希树的工作原理以及我如何实现它？

我正在查找哈希树的维基百科文章，我对他们的图表感到有些困惑。

叶节点显然包含底层数据的散列。

哈希树中的叶节点是否不同于任何非叶节点？非叶节点是否包含数据散列或散列散列？

鉴于此图：

其中哪一个是Hash 1哈希值？

1. Hash 1-0+Hash 1-1
2. Data block 002+Data block 003

或者哈希树是否因应用程序（rsync、P2P 网络、Git 等）而根本不同？

我正在研究一个逻辑，我想创建一个动态目录来导航用户。

用例说，我们必须有最多 50 个节点，最后一个度节点必须有 50 个叶子。（最后一个条目除外）

这种情况适用于 50 x 50、50 x 50 x 50 等。

任何人都可以建议我使用标准数据结构和逻辑来创建这样一个 n = 50 的 n 数组树，以使树具有最小深度并且在叶子处也同样平衡。

例如。

如果我有一个 6310 的列表，那么我们将有 node1 (2500) node2(2500) & node3(1310) 所以这会造成不平衡，即 level1 只有 3 个节点，但 level 2 有等于 50 个节点，因此分配失败。

在这里，我们还需要 level1 使其具有前 50 个范围，然后是 level2 中的分布。最后一个节点可以保持不均匀。

我刚刚发现了 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 树中的不同节点将产生相同的父哈希。

在这种情况下，当集群中的两台不同的机器遍历它们的默克尔树时，它们会得到一个误报，认为它们的数据是一致的。如果没有更多数据写入树的该分支，则机器将永远保持不同步。

这是如何处理的？

我正在尝试使用自定义类作为 的键unordered_map，如下所示：

但是，g++ 给了我以下错误：

我想，我需要告诉 C++ 如何散列类Node，但是，我不太确定该怎么做。我怎样才能完成这项任务？

我在运行需要读取大量 XML 数据的 SAX 解析器时收到此异常。数据存储在哈希树中。运行大约 15 分钟后，发现了这个异常。这是什么意思？

一次插入可扩展哈希是否可能导致多个目录加倍？我能找到的所有在线资源都只展示了只需要一个双精度的情况。

考虑使用键的 MSB 的示例：

| 0 | -> 00111

| 1 | -> 11110

插入(11111)

结果会是什么？我需要将目录翻倍吗？

从 ext4 维基百科介绍中，我发现 Htree 在 ext4 中用于目录组织和范围组织。

在目录组织场景中，哈希表树可以帮助平衡和改进搜索。

但是在范围组织中使用 Htree 有什么好处呢？

你的智慧坦克:)

我有一个模型标签，它是一个树模型（使用closure_tree），并且由于 gem，我可以执行以下操作：

急切地加载它的孩子。现在，我有一个实例方法，它也使用孩子。因此，当我通过上述查询获得标签时，遍历标签及其子项并调用此实例方法，bulletgem 抱怨我正在执行 N+1 查询并建议我使用include(children). 出现这种情况是因为我没有加载children的children，所以在调用实例方法的时候，我对一级标签的每个子标签的children进行了单独的查询。

我可以通过执行以下操作来解决此问题：

在这种情况下，ActiveRecord 急切地加载标签、它的孩子和它的孩子的孩子。但是，如果只有 3 代，则此方法有效 - 标记是祖父母，然后是父母（它们是根标记的子代）和孙子代（它们是根标记的子代的子代）。如果我有 4 代人，那么我必须这样做：

因此，如果我可以确定depth根标记的最远孙子，有没有办法有条件地构造我的查询 - 如果深度为 2，则使用includes(:children)，如果深度为 3 - 使用includes(children: :children)等等？