常见的一些 Hash 函数

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 函数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。