hashCode

对于包含容器类型的程序设计语言来说，基本上都会涉及到hashCode。在Java中也一样，hashCode方法的主要作用是为了配合基于哈希的集合一起正常运行，这样的哈希集合包括HashSet、HashMap以及HashTable。

当向集合中插入对象时，如何判别在集合中是否已经存在该对象，也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值，如果table中没有该hashcode值，它就可以直接存进去，不用再进行任何比较了；如果存在该hashcode值，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就哈希其它的地址，所以这里存在一个冲突解决的问题，这样一来实际调用equals方法的次数就大大降低了

通俗来说，Java中的hashCode方法就是根据一定的规则将与对象相关的信息，比如对象的存储地址，对象的字段等，映射成一个数值，这个数值称作为哈希值。

字符串中的hashCode

hashCode就是根据对象存储在内存的地址计算出的一个值。这个值可以标识这个对象的位置。也可以对比两个引用变量是否指向同一个对象。String重写了hashCode方法——改为根据字符序列计算hashCode值，所以String通过 String new("String") 方式创建的两个相同字符串内容的对象他们的hashcode相同。要想获取正确的hashcode，需要使用System.identityHashCode()方法。

public int hashCode() {
    int h = hash;
    if (h == 0) {
    int off = offset;
    char val[] = value;
    int len = count;
        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

public class IdentityHashCodeTest {

  public static void main(String[] args) {
    //下面程序中s1和s2是两个不同对象
    String s1 = new String("Hello");
    String s2 = new String("Hello");

    //String重写了hashCode方法——改为根据字符序列计算hashCode值，
    //因为s1和s2的字符序列相同，所以它们的hashCode方法返回值相同
    System.out.println(s1.hashCode() + "----" + s2.hashCode());

    //s1和s2是不同的字符串对象，所以它们的identityHashCode值不同
    System.out.println(
      System.identityHashCode(s1) + "----" + System.identityHashCode(s2)
    );
    String s3 = "Java";
    String s4 = "Java";

    //s3和s4是相同的字符串对象，所以它们的identityHashCode值相同
    System.out.println(
      System.identityHashCode(s3) + "----" + System.identityHashCode(s4)
    );
  }
}
/*
69609650----69609650
13078969----3154093
28399250----28399250
*/

在有些情况下，程序设计者在设计一个类的时候为需要重写equals方法，比如String类，但是千万要注意，在重写equals方法的同时，必须重写hashCode方法。

class People {
  private String name;
  private int age;

  public People(String name, int age) {
    this.name = name;
    this.age = age;
  }

  public void setAge(int age) {
    this.age = age;
  }

  /* 先注释掉对于hashCode的复写
    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return name.hashCode()*37+age;
    }
    */
  @Override
  public boolean equals(Object obj) {
    // TODO Auto-generated method stub
    return (
      this.name.equals(((People) obj).name) &&
      this.age == ((People) obj).age
    );
  }
}

public class Main {

  public static void main(String[] args) {
    People p1 = new People("Jack", 12);
    System.out.println(p1.hashCode());

    HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
    hashMap.put(p1, 1);

    System.out.println(hashMap.get(new People("Jack", 12)));
  }
}

在这里我只重写了equals方法，也就说如果两个People对象，如果它的姓名和年龄相等，则认为是同一个人。这段代码本来的意愿是想这段代码输出结果为“1”，但是事实上它输出的是“null”。为什么呢？原因就在于重写equals方法的同时忘记重写hashCode方法。

虽然通过重写equals方法使得逻辑上姓名和年龄相同的两个对象被判定为相等的对象(跟String类类似)，但是要知道默认情况下，hashCode方法是将对象的存储地址进行映射。那么上述代码的输出结果为“null”就不足为奇了。原因很简单，p1指向的对象和 System.out.println(hashMap.get(new People("Jack", 12))); 这句中的 new People("Jack", 12) 生成的是两个对象，它们的存储地址肯定不同。

hashCode设计

一个好的hash函数应该是这样的：为不相同的对象产生不相等的hashCode。在理想情况下，hash函数应该把集合中不相等的实例均匀分布到所有可能的hashCode上，要想达到这种理想情形是非常困难的，至少java没有达到。因为我们可以看到，hashCode是非随机生成的，它有一定的规律，就是上面的数学等式，我们可以构造一些具有相同hashCode但value值不一样的，比如说：Aa和BB的hashCode是一样的。

说到这里，你可能会想，原来构造hash冲突那么简单啊，那我是不是可以对HashMap函数构造很多<key,value>不都一样，但具有相同的hashCode，这样的话可以把HashMap函数变成一条单向链表，运行时间由线性变为平方级呢？虽然HashMap重写的hashCode方法比String类的要复杂些，但理论上说是可以这么做的。这也是最近比较热门的Hash Collision DoS事件。

       public final int hashCode() {
           return (key==null   ? 0 : key.hashCode()) ^
                   (value==null ? 0 : value.hashCode());
        }

下面这段话摘自Effective Java一书：

在程序执行期间，只要equals方法的比较操作用到的信息没有被修改，那么对这同一个对象调用多次，hashCode方法必须始终如一地返回同一个整数。

如果两个对象根据equals方法比较是相等的，那么调用两个对象的hashCode方法必须返回相同的整数结果。

如果两个对象根据equals方法比较是不等的，则hashCode方法不一定得返回不同的整数。

对于第二条和第三条很好理解，但是第一条，很多时候就会忽略。在《Java编程思想》一书中的P495页也有同第一条类似的一段话：

设计hashCode()时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该产生同样的值。如果在讲一个对象用put()添加进HashMap时产生一个hashCdoe值，而用get()取出时却产生了另一个hashCode值，那么就无法获取该对象了。所以如果你的hashCode方法依赖于对象中易变的数据，用户就要当心了，因为此数据发生变化时，hashCode()方法就会生成一个不同的哈希码

下面例子中我们展示下不合理的hash函数设计会导致的不一致性：

class People {
  private String name;
  private int age;

  public People(String name, int age) {
    this.name = name;
    this.age = age;
  }

  public void setAge(int age) {
    this.age = age;
  }

  @Override
  public int hashCode() {
    // TODO Auto-generated method stub
    return name.hashCode() * 37 + age;
  }

  @Override
  public boolean equals(Object obj) {
    // TODO Auto-generated method stub
    return (
      this.name.equals(((People) obj).name) &&
      this.age == ((People) obj).age
    );
  }
}

public class Main {

  public static void main(String[] args) {
    People p1 = new People("Jack", 12);
    System.out.println(p1.hashCode());

    HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
    hashMap.put(p1, 1);

    p1.setAge(13);

    System.out.println(hashMap.get(p1));
  }
}

这段代码输出的结果为“null”，想必其中的原因大家应该都清楚了。因此，在设计hashCode方法和equals方法的时候，如果对象中的数据易变，则最好在equals方法和hashCode方法中不要依赖于该字段。

hashCode

hashCode

字符串中的hashCode

hashCode设计

Links