Java高级系列——散列与散列码

使用散列的目的：想要使用一个对象查找另一个对象。

散列的价值：散列的价值在于速度，散列使得查询得以快速进行。

设计hashCode()时最重要的因素：无论何时，对同一个对象调用hashCode()都会产生同样的值。如果将一个对象用put()添加进HashMap时产生一个hashCode()值，而用get()取出时却产生了另外一个hashCode()值，那么就无法重新取得该对象了。

想要使hashCode()实用，它必须速度快，并且必须有意义。也就是说，它必须基于对象的内容生成散列码。散列码不必是独一无二的（应该关注生成速度，而不是唯一性），但是通过hashCode()和equals()，必须能够完全确定对象的身份。

好的hashCode()应该产生分布均匀的散列码。如果散列码都集中在一块，那么HashMap或者HashSet在某些区域的负载会很重，这样就不如分布均匀的散列函数快。

hashCode()基本指导

1、给int变量result赋予某个非零值常量，例如17.

2、为对象内每个有意义的域f（即每个可以做equals操作的域）计算出一个int散列码c：

域类型	计算
boolean	c = (f ? 0 : 1)
byte、char、short或int	c = (int)f
long	c = (int)(f^(f>>>32))
float	c = Float.floatToIntBits(f)
double	long l = Double.doubleToLongBits(f); c = (int)(l^(l >>> 32))
Object，其equals()调用这个域的equals()	c = f.hashCode()
数组	对每个元素应用上述规则

注：如果1中给定的初始值为0，那么计算出来的散列值将不受域类型的影响，从而可能会增加冲突的可能性。

3、合并计算得到的散列码：result=37 * result + c;
乘法运算使得散列值依赖于域的顺序，如果一个类包含多个相同的域，那么乘法运算会产生更好的散列函数。
我们来看看在标准类库中String类的hashCode()方法：

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
}

假如String类也根据上面的步骤来建立散列函数，并且把乘法部分省去（即将 h = 31 * h + val[i]改为 h = val[i]），则那些仅仅是字母顺序不同的所有字符串，都会有同样的散列码。

我们之所以将乘数选为37，是因为他是一个奇素数。如果乘数是偶数，并且乘法溢出的话，则会信息丢失，因为与2相乘等价于移位运算。

4、返回result；
5、检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。
根据以上步骤实现的一个例子如下：

package containers;

import java.util.*;

public class CountedString {
    private static List<String> created = new ArrayList<String>();
    private String s;
    private int id = 0;

    public CountedString(String str) {
        s = str;
        created.add(s);
        for (String s2 : created)
            if (s2.equals(s))
                id++;
    }

    public String toString() {
        return "String: " + s + " id: " + id + " hashCode(): " + hashCode();
    }

    public int hashCode() {
        int result = 17;
        result = 37 * result + s.hashCode();
        result = 37 * result + id;
        return result;
    }

    public boolean equals(Object o) {
        return o instanceof CountedString && s.equals(((CountedString) o).s) && id == ((CountedString) o).id;
    }

    public static void main(String[] args) {
        Map<CountedString, Integer> map = new HashMap<CountedString, Integer>();
        CountedString[] cs = new CountedString[5];
        for (int i = 0; i < cs.length; i++) {
            cs[i] = new CountedString("hi");
            map.put(cs[i], i);
        }

        System.out.println(map);

        for (CountedString cstring : cs) {
            System.out.println("Looking up " + cstring);
            System.out.println(map.get(cstring));
        }
    }
}