雜湊函式在電腦科學中廣泛使用，並在概率資料結構和演算法中非常有用。我們都知道資料結構是大多數演算法的構建塊。一個糟糕的選擇可能會導致出現一個困難和低效的解決方案，而不是優雅和高效的解決方案。正如Linus Torvalds在談論Git時所說: 事實上，我非常支援圍繞資料設計程式碼。相反，我認為這也是Git取得成功的原因之一(*)。辨別是否是一個糟糕程式設計師之間的一個好方法是考慮他的程式碼或資料結構更重要的是。糟糕的程式設計師擔心程式碼。優秀的程式設計師擔心資料結構及其關係。如果你是一名電腦科學家、工程師或程式設計師，你會非常清楚不同層次的資料結構的細節。與任何程式設計師進行十分鐘的交談可能會得到以下資訊:連結串列、樹、堆積、地圖等等。我已經和同事和朋友討論過關於掌握這些資料結構的重要性，這取決於你的工作內容。大多數情況下，如果您使用高階語言進行程式設計，那麼這是一種重新發明的輪子。大多數框架都內建了這些資料結構，或者有一些非常高效的庫，這些庫可以讓你進行更好的工作狀態。從另一個角度來看，大多數人在維護軟體或者資源約束不是問題的地方工作。專注於將效能或資源消耗作為資料結構或演算法的唯一度量標準是非常不明智的。這取決於你要解決的問題以及它的規模。但有時資源約束確實是一個問題，在這種情況下，您應該考慮工具箱中的一個重要工具:概率資料結構。它們犧牲了相當可觀的資源需求的精確性。如果您正在解決一個記憶體空間不受限制的小問題，計算不是瓶頸，精確的精度是必需的，那麼在使用它們之前，您可能會三思而後行。如果不是這樣，你應該知道它們存在的意義。另外，它們學起來很有趣。有很多書、論文和文章都在討論這個話題。在這裡，我將討論其中兩個我認為非常漂亮並且在實際問題中大量使用的方法。我將使用一些數學言語，但不是很詳細，因為網上有很多優秀的資源。即使你不懂數學，你也會得到它們的基本概念(這就是我們的目標)。布隆過濾器（Bloom filters）如果我沒記錯的話，布隆過濾器是我幾年前在閱讀somepetascale資料庫時聽說的第一個概率資料結構。與許多其他概率資料結構一樣，考慮到它們所需的空間和計算非常少，您會對它們的有效性感到非常驚訝。假設你有一個很大的整數集S，你想要檢查S是否包含一個元素i。你可以使用一個簡單的帶有空間/時間O(n)/O(n)的連結串列來解決這個問題。同樣，嘗試一個平衡的二叉樹，包含O(n)/O(log(n))。或者顯然是O(n)/O(1)的對映。似乎大多數選項都需要與S的基數線性的記憶體空間有關，這聽起來很合理，因為如果我們不儲存S的每個元素的值，我們如何檢查S中是否存在元素?布隆的思想是將整個集合S編碼成一個固定長度的二進位制字串，我們將其稱為q。這是透過對Swithin q中的每個元素進行編碼來實現的。讓我們看一個布隆的典型示例。假設我們將Q定義為一個長度固定為64位的二進位制字串。同時，我們選擇k個不同的雜湊函式，如MD5或SHA-1。接下來，我們做以下工作:· 取S中的第一個元素· 使用k個雜湊函式對元素進行雜湊，並取它們的模64在Q中生成k個索引。· 在之前計算的索引處，設定為Q中的每一位1· 對於S中剩下的每個元素，是否執行前面的兩個步驟當我們完成時，我們有一個64位的值Q，其中一些位被設定為1，另一些為0。如上所述檢查位應該是在問:如果還沒有設定相應的k位,我們可以確定元素並不是在美國，如果他們都準備好了,我們可以說之前的元素可能被許多其他元素設定為1。事實上，當你不斷地在S中新增元素時，越來越多的位在Q中被設定為1，因此你不斷地增大了這個概率。Bloom filters可以產生誤報，但不會產生漏報。如果我們增加Q的大小，從而避免了誤報的概率。k值對碰撞概率也有影響。這是大小(Q)和k以及誤報率之間的權衡。如果你對計算誤報率感興趣，你可以在這裡閱讀。同時，您可以在這裡看到考慮到S或期望的誤報率的最佳大小(Q)和k。還有一個更重要的需要考慮:在q中選擇雜湊函式來生成索引，之前我提到過MD5或SHA-1，但這些並不是真正明智的選擇。加密貨幣雜湊函式試圖生成不可逆轉的輸出。這在這裡不是問題。我們對隨機輸出和儘可能快地進行計算感興趣，因此有更好的選擇。
大多數實現使用一個雜湊函式來生成所需的k個輸出。特別是MurmurHash 函式，其中計算了一些輸出的常數基集，然後透過組合這些雜湊值生成k個輸出。還有另一種概率資料結構，稱為Count-min sketch，用於估計集合中每一項的概率。其思想與Bloom的工作原理非常相似，因此您可能有興趣。如果您對以太坊感興趣，可以使用Bloom檢查某個塊是否包含與特定主題相關的日誌。在以太坊中，主題與事件和索引引數相關。輕量級客戶機不儲存關於世界狀態、事務或收據的任何資料，它可以非常快速地檢查一個塊是否包含與感興趣的任何主題相關的日誌。如果Bloom filter檢查匹配，考慮到誤報的可能性很小，我們可以非常確定這個塊包含查詢主題的日誌條目。分析所有塊的所有交易的所有收據的永久成本要大於分析所有塊的所有交易的永久成本。HyperLogLogHyperLogLog是對以前的LogLog和線性計數等思想的改進，這些思想涉及到可數異的問題。假設你想知道一個集合S i的基數。e:在s中有多少不同的元素?我們還想在O(1)時空中做這個。引用最初提出這個想法的論文:例如,新演算法可以估計基數遠遠超出10⁹典型的準確性為2%。這種資料結構中的形式數學要比bloom複雜得多，但其背後的主要思想相當簡單。假設您有一個由8000個隨機生成的二進位制字串組成的集合。我們期望有多少個前導至少是3個0 ?至少有3個前導0的概率是1/8，所以，大約，我們可以估計有1000個前導0。當然，由於這是一個隨機過程，我們可以從0個二進位制字串中看到滿足這個屬性的字串，直到8000，但是每種情況的概率都很重要。更普遍的是,如果我們有n個前導0,然後似乎是合理的基數是2 ^ n。這和投擲一枚硬幣100次得到50次正面和50次反面是一樣的。當你深入研究細節時，你很快就會意識到差異是個問題。這是一個很大的問題，因為每一個誤差單位都會對估計產生指數級的影響。換種說法，如果我們碰巧有K+1個前導零而不是K個前導零，那麼我們的估計就會加倍。改進這方面的思想是將集合劃分為多個子集，並使用每個子集中最大前導零的平均值。從LogLog到HyperLogLog的一個演進是改變估計的均值型別，以控制對異常值的敏感性。特別是，LogLog使用算術平均值，而超LogLog使用調和平均值。此外，偏置校正係數被用來校正更多的剩餘偏置。透過將集合劃分為多個集合來重複這個實驗是很好的，但是它會產生另一個問題:如果集合的基數太小，那麼我們將沒有足夠的資料來進行統計。就像在Bloom中一樣，每個子集中的每個元素都經過雜湊函式處理，以將其轉換為一個固定長度的二進位制字串，我們可以從該字串中遵循上面的邏輯。總結我們可以看到，在所有這些情況下，雜湊函式都發揮著至關重要的作用。它們優雅地提供了許多對於概率資料結構和演算法非常有用的特性:· 它們將非均勻分佈的資料轉換成均勻分佈的資料，這為概率假設提供了一個起點。· 資料的統一可以促使資料自動重複或刪除，這有助於快速的解決問題。利用雜湊值不可逆性不是一個必然要求，因為非加密雜湊函式可以作為一個選擇，可以更快地幫助演算法的速度。更多區塊鏈資訊：www.qukuaiwang.com.cn/news
