黑马程序员技术交流社区

标题: 哈希值的问题 [打印本页]
作者: bigbean    时间: 2014-3-10 00:00
标题: 哈希值的问题
本帖最后由 bigbean 于 2014-3-10 02:18 编辑


  2. import java.util.*;

  4. /*
  5. 往hashSet集合中存入自定对象
  6. 姓名和年龄相同为同一个人，重复元素。





  12. */
  13. class HashSetTest
  14. {
  15.         public static void sop(Object obj)
  16.         {
  17.                 System.out.println(obj);
  18.         }
  19.         public static void main(String[] args)
  20.         {
  21.                 HashSet hs = new HashSet();

  23.                 hs.add(new Person("a1",11));
  24.                 hs.add(new Person("a2",12));
  25.                 hs.add(new Person("a3",13));
  26. //                hs.add(new Person("a2",12));
  27. //                hs.add(new Person("a4",14));

  29.                 //sop("a1:"+hs.contains(new Person("a2",12)));
  30.                         
  31. //                hs.remove(new Person("a4",13));
  32.                

  34.                 Iterator it = hs.iterator();

  36.                 while(it.hasNext())
  37.                 {
  38.                         Person p = (Person)it.next();
  39.                         sop(p.getName()+"::"+p.getAge());
  40.                 }
  41.         }
  42. }
  43. class Person
  44. {
  45.         private String name;
  46.         private int age;
  47.         Person(String name,int age)
  48.         {
  49.                 this.name = name;
  50.                 this.age = age;
  51.         }
  52.         
  53.         public int hashCode()
  54.         {
  55.                 System.out.println(this.name+"....hashCode");
  56.                 return name.hashCode()+age*37;
  57.         }

  59.         public boolean equals(Object obj)
  60.         {

  62.                 if(!(obj instanceof Person))
  63.                         return false;

  65.                 Person p = (Person)obj;
  66.                 System.out.println(this.name+"...equals.."+p.name);

  68.                 return this.name.equals(p.name) && this.age == p.age;
  69.         }

  71.         
  72.         public String getName()
  73.         {
  74.                 return name;
  75.         }
  76.         public int getAge()
  77.         {
  78.                 return age;
  79.         }
  80. }
复制代码


为什么这里 56行的
        public int hashCode()
        {
                System.out.println(this.name+"....hashCode");
                return name.hashCode()+age*37;
        }
要乘以37呢？

作者: 赵卓辉    时间: 2014-3-10 01:42
因为你要先比较哈希值，假如一个叫“王五”的人，名字算出来的哈希值是30，再加上“age=20”，如果不乘37，那么他得哈希值是50.如果另一个人叫“张三”，他名字算出来的哈希值是40，而age=10，那么他的哈希值也是50。可见这里乘以37是为了避免哈希值相等。随便乘个数也可以（如27、22等等）。
作者: bigbean    时间: 2014-3-10 02:18
赵卓辉 发表于 2014-3-10 01:42
因为你要先比较哈希值，假如一个叫“王五”的人，名字算出来的哈希值是30，再加上“age=20”，如果不乘37， ...

好吧，哈希值怎么可能刚好等于30。。。
作者: 赵卓辉    时间: 2014-3-10 02:29
bigbean 发表于 2014-3-10 02:18
好吧，哈希值怎么可能刚好等于30。。。

哈希值是通过一定的哈希算法算出来的。也许会有等于某值的可能，乘一个值可以把这种可能性降低。记得毕老师的视频讲过。
作者: syw02014    时间: 2014-3-10 08:54
    1、Hash值的用途：
    HashMap、HashTable、HashSet，所以涉及到使用Hash值进行优化存储的地方，都会用到HashCode。HashCode是Key，这种计算为提高计算的性能。想想看，一般来说，数组算是比较快的集合类了吧，直接用index定位元素，简直就是O(1)的级别。但是添加元素就不这么乐观了。但是使用hash类的集合，添加元素，移动的元素少，只影响一小块，并且查找元素，由于hash值已经进行了定位分组，所以也会大大缩小涉及面，快速定位。
    2、Hash值应该符合的原则
        A、等幂性。不管执行多少次获取Hash值的操作，只要对象不变，那么Hash值是固定的。如果第一次取跟第N次取不一样，那就用起来很麻烦，需要记录当前是第几次操作，这种需要记录状态的事情，可不是什么好事。
        B、对等性。若两个对象equal方法返回为true，则其hash值也应该是一样的。举例说明：若你将objA作为key存入HashMap中，然后new了一个objB。在你看来objB和objA是一个东西（因为他们equal），但是使用objB到hashMap中却取不出来东西。
        C、互异性。若两个对象equal方法返回为false，则其hash值最好也是不同的，但这个不是必须的，只是这样做会提高hash类操作的性能（碰撞几率低）。
    3、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））。






欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2