雜湊演算法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

雜湊演算法(Hashing algorithms)

目錄

什麼是雜湊演算法

  雜湊(Hashing) 是電腦科學中一種對資料的處理方法,通過某種特定的函數/演算法(稱為雜湊函數/演算法)將要檢索的項與用來檢索的索引(稱為雜湊,或者雜湊值)關聯起來,生成一種便於搜索的數據結構(稱為雜湊表)。也譯為散列。舊譯哈希(誤以為是人名而採用了音譯)。它也常用作一種資訊安全的實作方法,由一串資料中經過雜湊演算法 (Hashing algorithms) 計算出來的資料指紋 (data fingerprint),經常用來識別檔案與資料是否有被竄改,以保證檔案與資料確實是由原創者所提供。

  如今,雜湊演算法也被用來加密存在資料庫中的密碼 (password) 字串,由於雜湊演算法所計算出來的雜湊值 (Hash Value) 具有不可逆 (無法逆向演算回原本的數值) 的性質,因此可有效的保護密碼。

常見的雜湊演算法

  有時候雜湊函數是一個壓縮映像,因此不可避免會發生衝突,因此在建造hash’函數的時候不僅要設定一個好的hash函數,還要設定一種處理衝突的方法,哈希造表,散列表。

  1、直接定址法 :地址集合和關鍵字集合大小相同

  2、數字分析法 :根據需要hash的 關鍵字的特點選擇合適hash演算法,儘量尋找每個關鍵字的不同點。

  3、平方取中法:取關鍵字平方之後的中間極為作為哈希地址,一個數平方之後中間幾位數字與數的每一位都相關,取得位數由表長決定。比如:表長為512,=2^9,可以取平方之後中間9位二進位數作為哈希地址。

  4、摺疊法:關鍵字位數很多,而且關鍵字中每一位上的數字分佈大致均勻的時候,可以採用摺疊法得到哈希地址,

  5、除留取餘法除P取餘,可以選P為質數,或者不含有小於20的質因數的合數

  6、隨機數法:通常關鍵字不等的時候採用此法構造哈希函數較恰當。

  實際工作中需要視不同的情況採用不同的hash函數:

  1、考慮因素:計算哈希函數所需要的時間,硬體指令等因素。

  2、關鍵字長度

  3、哈希表大小

  4、關鍵字分佈情況

  5、記錄查找的頻率。(huffeman樹)

  處理衝突的方法:

  開放地址法:現行探測再散列,只要哈希表為填滿,總能找到一個不衝突的地址,二次探測再散列 表長為素數時才可能保證總能找到一個不衝突的地址,隨機探測再散列取決於偽隨機數列。

  再哈希法:不易發生聚集,但是增加了計算的時間

  鏈地址法;Chord協議中,一致性hash有應用。

  對不同hash函數以及處理衝突的方法,計算了查找成功的平均長度以及不成功的平均長度。這些結果主要取決於裝填因數,裝填因數,可以將平均查找長度限定在一個範圍內。

本條目對我有幫助1
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您認為本條目還有待完善,需要補充新內容或修改錯誤內容,請編輯條目

本条目由以下用户参与贡献

苏青荇.

評論(共0條)

提示:評論內容為網友針對條目"雜湊演算法"展開的討論,與本站觀點立場無關。

發表評論請文明上網,理性發言並遵守有關規定。

打开APP

以上内容根据网友推荐自动排序生成