什麼是哈希(Hash)

什麼是哈希(Hash)

什麼是哈希(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等。

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *