什麼是哈希(Hash)

資料來源: https://mp.weixin.qq.com/s?__biz=MzAxMTA4Njc0OQ==&mid=2651441053&idx=3&sn=330722bf9ada1ac39ad4ec9abb6ef9f7&chksm=80bb196fb7cc907922adda7bbd3772ef7ac68b0decb4a9b2a64c7831cc0284487be680b51900&scene=126&sessionid=1596418453&key=360754e56e033319080602b9a683ccc725b300a8f539f830e191b56466d225f120f8aa855666e0d4d58ef0dcb63af11f1ab668bee4976a85b8466f3485b54da4c9a4175fd083c7dc964456441c735ed0&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10+x64&version=62090529&lang=zh_TW&exportkey=ArbkjAzclwl%2F4AX799XU3uE%3D&pass_ticket=WNCn7OLBe934iNlPmag9gFlFhBUXpBtmg3NKjWA3RMSMRcRzAd2zqyH2vwqaqgu1

數據結構中我們學習過哈希表也稱為散列表，我們來回顧下散列表的定義。

散列表，是根據鍵直接訪問在指定儲存位置數據的數據結構。通過計算一個關於鍵的函數也稱為哈希函數，將所需查詢的數據映射到表中一個位置來訪問記錄，加快查找速度。這個映射函數稱做「散列函數」，存放記錄的數組稱做散列表。

散列函數能使對一個數據序列的訪問過程更加迅速有效，是一種空間換時間的算法，通過散列函數數據元素將被更快定位。

下圖示意了字符串經過哈希函數映射到哈希表的過程。沒錯，輸入字符串是用臉滾鍵盤打出來的：）

常見的哈希算法有MD5、CRC 、MurmurHash 等算法，簡單介紹一下。

    MD5算法
        MD5消息摘要算法（英語：MD5 Message-Digest Algorithm），一種被廣泛使用的密碼散列函數，可以產生出一個128位（16字節）的散列值（hash value），MD5算法將數據（如一段文字）運算變為另一固定長度值，是散列算法的基礎原理。由美國密碼學家Ronald Linn Rivest設計，於1992年公開並在RFC 1321 中被加以規範。

    CRC算法
        循環冗餘校驗（Cyclic Redundancy Check）是一種根據網絡數據包或電腦文件等數據，產生簡短固定位數校驗碼的一種散列函數，由W. Wesley Peterson 於1961年發表。生成的數字在傳輸或者存儲之前計算出來並且附加到數據後面，然後接收方進行檢驗確定數據是否發生變化。由於本函數易於用二進制的電腦硬件使用、容易進行數學分析並且尤其善於檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用。

    MurmurHash
        MurmurHash 是一種非加密型哈希函數，適用於一般的哈希檢索操作。由Austin Appleby 在2008年發明，並出現了多個變種，與其它流行的哈希函數相比，對於規律性較強的鍵，MurmurHash的隨機分佈特徵表現更良好。
        這個算法已經被很多開源項目使用，比如libstdc++ (4.6版)、Perl、nginx (不早於1.0.1版)、Rubinius、 libmemcached、maatkit、Hadoop等。