Hash的主要原理就是把大范圍映射到小范圍；所以，你輸入的實際值的個數必須和小范圍相當或者比它更小。不然沖突就會很多。

不同的應用對Hash函數有著不同的要求；比如，用于加密的Hash函數主要考慮它和單項函數的差距，而用于查找的Hash函數主要考慮它映射到小范圍的沖突率。

下面介紹一些常用的用于查詢Hash函數。

加法Hash

public class AdditiveHash {@Testpublic void additionHashDemo() {int result = this.additiveHash("mykey", 31);System.out.println(result);}/*** 加法hash, 把輸入元素一個一個的加起來構成最后的結果* @param prime 任意的質數。質數可以降低碰撞的概率* @return 結果在 [0, prime-1]*/private int additiveHash(String key, int prime) {int hash;int i;for (hash = key.length(), i = 0; i < key.length(); i++ ) {hash += key.charAt(i);}return hash % prime; //除以 一個prime的目的只是為了保證結果的范圍} }

位運算Hash

@Test public void rotatingHashDemo() {int hash = this.rotatingHash("key", 31);System.out.println(hash); }/*** 標準的旋轉hash， 通過先移位，在進行各種位運算。 比如某個學校同一系的新生，學號前5位相同，最后2位不同，* 將最后2位旋轉放置前兩位，其余的右移。這樣只要輸入前兩位，就可以快速查出學生的信息。* @param key hash key* @param prime 任意的質數。質數可以降低碰撞的概率*/ private int rotatingHash(String key, int prime) {int hash;int i;for (hash = key.length(), i = 0; i < key.length(); i++) {hash = (hash<<4)^(hash>>28)^key.charAt(i);}return (hash % prime); //除以 一個prime的目的只是為了保證結果的范圍 }

乘法Hash

@Test public void bernsteinHashDemo() {int result = this.bernsteinHash("key", 31);System.out.println(result); }@Test public void RSHashDemo() {int result = this.RSHash("key");System.out.println(result); }/*** jdk5.0 中 string 的 hashCode() 方法使用的就是這種乘法hash. 乘數可以是31， 131， 1313。。。<br/>* @param key hash key* @param prime 質數*/ private int bernsteinHash(String key, int prime) {int hash = 0;int i;for (i = 0; i < key.length(); i++) {hash = prime * hash + key.charAt(i);}return hash; }/*** 乘以一個不斷該不變的數* @param key hash key* @return hash value*/ private int RSHash(String key) {int b = 37855;int a = 63689;int hash = 0;for (int i = 0; i < key.length(); i++) {hash = hash * a + key.charAt(i);a = a * b;}return (hash & 0x7FFFFFFF); }

總結

以上是生活随笔為你收集整理的常见的一些 Hash 函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。