区块链运作基础（2）哈希指针

本篇文章将为大家讲述哈希指针及其应用。哈希指针是应用在区块链技术中的一种数据结构。普通的指针储存了一段数据的内存位置，而哈希指针除了储存数据位置之外，还储存了这段数据的哈希值。普通的指针只能检索到数据，哈希指针还可以告诉我们数据是什么以及是否被更改。

如图所示，一个哈希指针包含了一段数据的位置和这段数据原始的哈希值。我们可以使用哈希指针取代普通指针去创建各种类型的数据结构,链表，二叉树等等。

如图所示，在区块链中，我们就是用哈希指针建立一个链表。普通链表的一个区块储存了数据及指向前一个区块的指针。而区块链用哈希指针取代了传统指针，除了能表示前一个区块的位置还能告诉我们前个区块的所有内容。哈希指针很重要的一个作用就是防止日志被篡改。比如我们用哈希指针建立了一个数据结构日志去储存大量数据，日志的尾部可以添加新的数据，但是如果有人篡改了之前区块的数据我们就会察觉到。区块链的这种防篡改属性是如何实现的呢？

如图所示，如果攻击者想篡改这个区块内的数据，那么这个区块就和其哈希指针表示的哈希值无法对应。由于哈希函数的无碰撞属性，我们可以判断出这个区块出现错误。所以，攻击者必须再次篡改前一个区块内的哈希指针使二者保持一致。但是对前一个区块的更改又会使之和前前区块的哈希指针不一致…..

所以，如果攻击者想篡改数据的话需要依次更改整条链表中所有区块的数据直到第一个区块。只要我们记住表头第一个区块的哈希指针，攻击者就无法完成数据篡改，因为整条区块链的数据会无法对应。我们通常把第一个区块称为创世区块。

我们可以用哈希指针去建立另外一种数据结构:二叉树。使用哈希指针构建的二叉树通常被称为默克尔树（Merkle tree）

默克尔树将所有数据两两分为一组，每一组的哈希值储存在上一个节点中，而上一个节点中的哈希值也将两两储存在上上节点中。最顶层的节点被称为根节点而其余节点叫做叶子节点。和区块链一样，你只要记住根节点的哈希指针，就可以向下遍历所有叶子节点的值，并且可以保证所有数据无法被篡改。因为如果攻击者试图篡改某个数据，他就必须篡改整条链上的哈希指针直到根节点。而根节点的值我们已经牢牢记住。

默克尔树另一个优势是可以比区块链更快的遍历查找一个数据块是否属于这个树。

也就是说我们只要从根节点依次验证和该数据相连的区块，而不用理会树的其它部分。如此所见，验证某一区块数据的时间复杂度为O(log n),而区块链需要依次遍历整条链才能完成验证，时间复杂度为O(n),这大大提高了效率。

由于哈希指针的这些优点，我们可以在所有非循环的，基于指针的数据结构中使用它。而循环的数据结构并不能使所有的区块和哈希指针相匹配。在非循环的数据结构中，我们可以从不带指针的链尾数据依次算到链表头部，而只记住链表头部的一个哈希指针即可保证整个链表的正确性。而循环的数据结构无法按此方法进行计算。