哈希--常見的演算法介紹

　　哈希（Hash）又稱為散列，它是一個很常見的演算法。在Java的HashMap資料結構中主要就利用了雜湊。哈希演算法包括了哈希函數和哈希表兩部分。我們陣列的特性可以知道，可以透過下標快速（O(1)）的定位元素，同理在雜湊表中我們可以透過鍵（雜湊值）快速的定位某個值，這個哈希值的計算就是透過哈希函數(hash(key) = address )計算出來的。透過雜湊值即能定位元素[address] = value，原理同數組類似。

最好的雜湊函數當然是每個key值都能計算出唯一的雜湊值，但往往可能存在不同的key值的雜湊值，這就造成了衝突，評判一個雜湊函數是否設計良好的兩個面向：

##　　1.衝突少。

　　2.計算快。

　　下面給出幾種常用的雜湊函數，它們的背後都有一定的數學原理且經過大量實踐，其數學原理不在這裡探究。

BKDR雜湊函數（h = 31 * h + c）

#　　這個雜湊函數被應用在

Java的字串雜湊值計算。

 

//String#hashCodepublic int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];    //BKDR 哈希函数，常数可以是131、1313、13131……        }
        hash = h;
    }return h;
}

 

#DJB2 雜湊函數（#h = h << 5 + h + c = h = 33 * h + c）

　　ElasticSearch

就利用了DJB2雜湊函數對要索引文件的指定key#進行雜湊。

SDBM雜湊函數（SDBM雜湊函數（h = h << 6 + h << 16 - h + c = 65;< 16 - h + c = 65;< 16 - h + c = 6555599999999999999 * h + c

）

#　　在

SDBM

（簡單的資料庫引擎）中被應用。 　　以上只是列舉了三種雜湊函數，我們做下試驗，看看它們的衝突情況是怎麼樣的。

　　

Java

##100萬、200萬的衝突數情況：

###############　　反覆試驗實際上三種雜湊函數的衝突數差不多。 ###### 　　######Python######3############

 1 package com.algorithm.hash; 2  3 import java.util.HashMap; 4 import java.util.UUID; 5  6 /** 7  * 三种哈希函数冲突数比较 8  * Created by yulinfeng on 6/27/17. 9  */10 public class HashFunc {11 12     public static void main(String[] args) {13         int length = 1000000;   //100万字符串14         //利用HashMap来计算冲突数，HashMap的键值不能重复所以length - map.size()即为冲突数15         HashMap<String, String> bkdrMap = new HashMap<String, String>();16         HashMap<String, String> djb2Map = new HashMap<String, String>();17         HashMap<String, String> sdbmMap = new HashMap<String, String>();18         getStr(length, bkdrMap, djb2Map, sdbmMap);19         System.out.println("BKDR哈希函数100万字符串的冲突数：" + (length - bkdrMap.size()));20         System.out.println("DJB2哈希函数100万字符串的冲突数：" + (length - djb2Map.size()));21         System.out.println("SDBM哈希函数100万字符串的冲突数：" + (length - sdbmMap.size()));22     }23 24     /**25      * 生成字符串，并计算冲突数26      * @param length27      * @param bkdrMap28      * @param djb2Map29      * @param sdbmMap30      */31     private static void getStr(int length, HashMap<String, String> bkdrMap, HashMap<String, String> djb2Map, HashMap<String, String> sdbmMap) {32         for (int i = 0; i < length; i++) {33             System.out.println(i);34             String str = UUID.randomUUID().toString();35             bkdrMap.put(String.valueOf(str.hashCode()), str);   //Java的String.hashCode就是BKDR哈希函数， h = 31 * h + c36             djb2Map.put(djb2(str), str);    //DJB2哈希函数37             sdbmMap.put(sdbm(str), str);    //SDBM哈希函数38         }39     }40 41     /**42      * djb2哈希函数43      * @param str44      * @return45      */46     private static String djb2(String str) {47         int hash = 0;48         for (int i = 0; i != str.length(); i++) {49             hash = hash * 33 + str.charAt(i);    //h = h << 5 + h + c = h = 33 * h + c50         }51         return String.valueOf(hash);52     }53 54     /**55      * sdbm哈希函数56      * @param str57      * @return58      */59     private static String sdbm(String str) {60         int hash = 0;61         for (int i = 0; i != str.length(); i++) {62             hash = 65599 * hash + str.charAt(i);    //h = h << 6 + h << 16 - h + c = 65599 * h + c63         }64         return String.valueOf(hash);65     }66 }

###

　　雜湊表是一種資料結構，它需要配合雜湊函數使用，用於建立索引，以便快速查找——#《演算法筆記》。一般來講它就是一個定長的儲存空間，例如HashMap預設的雜湊表就是定長為16#的Entry陣列。有了定長的儲存空間過後，剩下的問題就是如何將值放入哪個位置，通常如果雜湊值是m，長度為 n，那麼這個值就放到m mod n位置。

 

　　上圖是雜湊和雜湊表，以及產生衝突的解決方法（拉鍊法）。產生衝突後的解決辦法有很多，有再哈希一次直到沒有衝突，也有向上圖一樣採用拉鍊法利用鍊錶將相同位置的元素串聯。

　　想像一下，上面的例子哈希表的長度為10，產生了##1次衝突，如果哈希表長度為20，那麼就不會產生衝突查找更快但會浪費更多空間，如果雜湊表長度為2，將會倒置3次衝突查找更慢但這樣又會節省不少空間。 所以哈希表的長度選擇至關重要，但同時也是一個重要的難題。

補充：

　　哈希在很多方面有應用，例如在不同的值有不同的雜湊值，但也可以將雜湊演算法設計精妙使得相似或相同的值有相似或相同的雜湊值。也就是說如果兩個物件完全不同，那麼它們的雜湊值也完全不同；如果兩個物件完全相同，那麼它們的雜湊值也完全相同；兩個物件越相似，那麼它們的雜湊值也就越相似。這其實就是相似性問題，也就是說這個想法可以被推廣應用在相似性的計算（例如Jaccard距離問題），最後應用到廣告精準投放、商品推薦等。

　　另外，一致性雜湊也可應用在負載平衡，如何保證每台伺服器能均勻的分攤負載壓力，一個好的雜湊演算法也可做到。

以上是哈希--常見的演算法介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！