哈希指针及数据结构

公众号回复“1”，拉你进区块链技术讨论微信群

来源：物流与区块链

本文约1600字+，阅读（观看）需要10分钟

哈希指针是一种数据结构，确切地说，是一个指向数据存储位置的指针，同时也是位置数据的哈希值。

跟普通的指针相比，哈希指针不但可以告诉你存储的位置，并且还可以验证数据没有被篡改过。通常我们用下图来表示哈希指针。

书中提到了两种带哈希指针的数据结构，一种是区块链，另一种是梅克尔树。

我们通过哈希指针建一个链表，这个数据结构就称为区块链。普通链表中有一系列区块，每个区块既有数据也有一个指向上一个区块的指针。而在区块链中，指向上一个区块的指针是哈希指针。所以，每个区块不仅能告诉我们上一个区块的值在哪里，还包含了其哈希值。我们可以用下图的样式表示哈希指针。

我们都知道区块链的一个应用就是“防篡改”，我们可以来看下，如果在区块链中篡改数据会发生什么样的后果。

假设有人改变了上图最左侧区块的数据，那么后面一个区块上方的哈希值就会不匹配。如果对方继续尝试，并篡改下一个区块的哈希值（上图中间）来掩盖这次篡改，那么再后面一个区块的哈希值（上图右侧）就会不匹配。对方可以一直篡改下去，直到到达链表最末端的H( )。只要最后的这个H( )存储在对方无法改动的地方，那么对方就无法在不被检测到的情况下篡改任何区块。

因此只要记住了最末端的哈希值，整个链表就是防篡改的。

另一个带哈希指针的有用的数据结构是二叉树，也称为梅克尔树(Merkle trees），以其发明者的名字命名。

如下图所示，最下方的数据区块为树的叶子，我们将区块两两分组，然后为每一组建立一个有两个哈希指针的数据结构，每个指针指向一个区块。这些指针区块就构成了树的下一层次，同样再将这些区块两两分组并建立指针，直到最后得到一个树根节点（下图最上方）。

看到上面结构的时候，我们很容易理解这个结构的防篡改特性，同区块链的结构一样，除非对方能够更改最上方根节点上的哈希值，否则，任何一个区块上的数据改动，都会导致和上一层的哈希指针不匹配，而被发现。

除了上面这点外，梅克尔树还有另外两个优点：

一是它可以实现简洁的隶属证明。假设某人想要证明某个区块属于梅克尔树，他只需要展示从这个区块通往根节点的路径上的区块，而忽略树的其它部分。也就是说，假设整棵树上有n个节点，只需要展示log(n)个项目便可以证明隶属关系——这代表验证所花的时间较短。

二是，如果我们将梅克尔树的底层的数据排序（按字母表、词典排序、数字化排序或其它约定的方式），我们就可以在log(n)复杂度的条件下验证某个数据区块不属于某梅克尔树。方法是通过展示被验证区块之前的区块路径，以及被验证区块之后的区块路径。如果之前、之后两个区块在树上是连续的，就说明了被验证区块并不属于该梅克尔树。

这一节的困惑：

1.这一节最大的疑问是，在区块链的部分看到“表头”及“头部数据”（这个并非翻译的问题，中文英文都是一样的意思）的时候，直觉的反应是这应该在区块链的最前端或者说应该是它的第一个数据，但事实上“头部数据”代表的却是区块链最末端的哈希指针——在看到梅克尔树中的描述时通常就明白了。而在1.3节中说到数字签名时，这点就更明白了。

2.这一节的另外一个疑惑是log(n)。我知道lg(n)代表底数是10，ln(n)代表底数是e，然后log(n)是什么东东？查了下，才知道log(n)没写底数，底数可以是10，可以是e，也可以是底数不重要时的任何底数——看具体用在什么情况下，但在计算机上一般代表底数是2。数学本来就不好的人深深体会到了与时俱进的压力。

文章发布只为分享区块链技术内容，版权归原作者所有，观点仅代表作者本人，绝不代表区块链兄弟赞同其观点或证实其描述。