哈希树(Merkle 树)的原理与应用
哪些公司问过
答案要点
- Merkle 树:叶子存数据块哈希,父节点存子哈希拼接后的哈希,直到根
- 任一数据块变化,路径上的哈希和根哈希都会变
- 两份数据比对时只沿哈希不同的分支向下,快速定位差异
- 存在性证明只需路径上的兄弟哈希,长度 O(log n)
- 应用:区块链交易校验、分布式存储反熵修复、P2P 分块校验、Git 对象树
易错点
- 说哈希树能把查找降到 O(1)
- 以为修改一个数据块只影响它自己的哈希
面试官常见追问
- Merkle 树和 Trie 前缀树有什么区别?
- 区块链轻节点怎么验证一笔交易?
- 叶子节点个数是奇数怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场