最酷的數據結構是什麼？

要我投票的話，我覺得最酷的數據結構是 Merkle樹。要理解 Merkle樹，我們首先要了解哈希指針，這是Merkle樹的概念基礎。

哈希指針就是一對值：

哈希指針=（指針，哈希值）

這個指針具體指一個內存地址。這和鏈表和樹形圖的指針沒有區別。

有趣的一點是，哈希值域包含各種內容的散列，卻被指向。

如下圖所示：

紅色箭頭表示存儲內存地址的指針，H()暗示哈希值的存儲。

當我們採用常規數據結構，並用哈希指針取代指針時，哈希指針的作用是很明顯的。舉個例子，當你做一個鏈表，但是使用的是哈希指針，而不是常規指針時，你會得到一個叫“數據區塊鏈”的數據結構：

數據區塊鏈的神奇之處在於，它提供篡改檢測。如果有人試圖改變某一節點的數據，那麼哈希值就會改變，那麼就會與哈希指針上報告的哈希值不符。

數據區塊鏈最著名的應用就是比特幣，這是一種新型網絡貨幣，它每十分鐘被區塊收集一次。因為數據區塊鏈提供篡改檢測，並可以記錄最後一個擁有哈希指針的人，也就是說，它可以記錄整個交易過程，即使是比特幣的交易也能做到。

這就帶我們來到了最後一個環節——Merkle樹。Merkle樹是一種二進制樹，它的指針也被換成了哈希指針，而數據儲存在“樹葉”中。舉個例子：

和數據區塊鏈差不多，Merkle樹也是防篡改的，因為它也依靠哈希指針。最後一個用戶只需要在腳本上儲存最後一次的哈希指針就可以。

Merkle樹的酷就酷在它能有效證明身份。如果有人告訴你一個儲存在Merkle樹“樹葉”裡的具體區塊，nn字節，你可以讓他們直接告訴你從腳本到“樹葉”lognlogn字節。如果哈希指針有效，這意味著每一個哈希指針都儲存著正確的信息，那麼身份就得以證明了。另一方面，如果想用區塊證明身份，需要提供現在至一千個區塊以前，這段範圍的所有區塊。

Merkle樹有無數應用，包括GIT版本控制、比特幣區塊儲存，還有很多其他的應用，它們會自己證明自己的價值。