hadoop基础:Java中的Hash值介绍-Java语言-about云开发

问题导读:

1.什么是hashcode?

2.如何计算hashcode?

3.hashcode有什么好处?

我们在学习hadoop过程中,经常遇到hashcode,那么hash到底是什么?

我们可以把它理解一个数字,如果到了这里,其实已经差不多了。那么下面如果想详细了解,可以往下面看:

hashcode实例

  1.   /**

  2.      * Returns a hash code for this string. The hash code for a

  3.      * <code>String</code> object is computed as

  4.      * <blockquote><pre>

  5.      * s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

  6.      * </pre></blockquote>

  7.      * using <code>int</code> arithmetic, where <code>s[i]</code> is the

  8.      * <i>i</i>th character of the string, <code>n</code> is the length of

  9.      * the string, and <code>^</code> indicates exponentiation.

  10.      * (The hash value of the empty string is zero.)

  11.      *

  12.      * @return  a hash code value for this object.

  13.      */

  14.     public int hashCode() {

  15. int h = hash;

  16. if (h == 0) {

  17.    int off = offset;

  18.    char val[] = value;

  19.    int len = count;

  20.             for (int i = 0; i < len; i++) {

  21.                 h = 31*h + val[off++];

  22.             }

  23.             hash = h;

  24.         }

  25.         return h;

  26.     }

复制代码

以字符串”123″为例:

字符’1’的ascii码是49

hashCode = (49*31 + 50)*31 + 51

或者这样看:

hashCode=(’1′ * 31 + ‘2’ ) * 31 + ‘3’

可见实际可以看作是一种权重的算法,在前面的字符的权重大。

这样有个明显的好处,就是前缀相同的字符串的hash值都落在邻近的区间。

好处有两点:

1.可以节省内存,因为hash值在相邻,这样hash的数组可以比较小。比如当用HashMap,以String为key时。

2.hash值相邻,如果存放在容器,比好HashSet,HashMap中时,实际存放的内存的位置也相邻,则存取的效率也高。(程序局部性原理)

以31为倍数,原因了31的二进制全是1,则可以有效地离散数据。

上面我们看到了hashcode具体是什么样子,下面我们从概念的角度来理解

hashcode理论

1、Hash值有什么用?

     HashMap、HashTable、HashSet,所以涉及到使用Hash值进行优化存储的地方,都会用到HashCode。HashCode是Key,这种计算为提高计算的性能。想想看,一般来说,数组算是比较快的集合类了吧,直接用index定位元素,简直就是O(1)的级别。但是添加元素就不这么乐观了。但是使用hash类的集合,添加元素,移动的元素少,只影响一小块,并且查找元素,由于hash值已经进行了定位分组,所以也会大大缩小涉及面,快速定位。

2、Hash值应该怎么计算?

   A、简单计算就是组成成员的hash值直接相加即可。比如ObjectA有三个属性,propA、propB和propC,最直接的计算方式就是propA.hashcode+propB.hashcode+propC.hashcode。

   B、但是如果遇到有顺序相关的怎么办?比如String类型是由char数组组成,并且这些数组是有顺序的。如果使用第一种计算方法,则“ABCD”和“BCDA”就会产生同样的hashCode,那么怎么办呢?最直接想到的办法就是加权,不同的index加不同的权值,这个权值的确定最直接的方法就是某个常数值的几次幂。比如为String的计算hash值为K^0*A.hashCode+K^1*B.hashCode+K^2*C.hashCode+K^3*D.hashCode。K的选择也有说法,最好不要是偶数,因为偶数的相乘会造成信息的丢失(乘以2就是左移1位,一旦溢出就会造成信息的丢失,这种计算会造成溢出后的值与某个看似不相关的数值得到的结果是一样的),所以最好是奇数,在这一点上比较推荐使用7,因为7=8-1=2^3-1,这样计算的时候,直接左移几位再进行一次普通的加减法即可(Java中常用的是31(32-1=2^5-1))。

来源URL:http://www.aboutyun.com/thread-7560-1-1.html