从容器角度搞懂hashCode和equals关系

发表于   |   分类于   |     |   本文总阅读量 次

　Java容器框架中有List和Set，其中List允许有重复元素，而Set则不允许有重复元素，Set是如何处理这里重复元素的？肯定是与equals相关，通过迭代来equals()是否相等，但是当数据量大的时候，假如我们往HashSet中添加10000个元素，equals()10000次，效率岂不是很低？我们来看看HashSet是如何实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public V put(K key, V value) {
       //如果key为空的情况
       if (key == null)
           return putForNullKey(value);
       //计算key的hash值
       int hash = hash(key);
       //计算该hash值在table中的下标
       int i = indexFor(hash, table.length);
       //对table[i]存放的链表进行遍历
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           //判断该条链上是否有hash值相同并且key值相同
           //若存在相同，则直接覆盖value，返回旧value
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;//取出old value
               e.value = value;//new value覆盖 old value
               e.recordAccess(this);
               return oldValue;
           }
       }
       //对table[i]存放的链表进行遍历不存在满足条件（该条链上是否有hash值相同并且key值相同），则在该链上添加一个Entry
       //修改次数+1
       modCount++;
       //把当前key，value添加到table[i]的链表中
       addEntry(hash, key, value, i);
       return null;
   }

HashSet内部是使用HashMap来实现的

当调用set.add(1)，实际上set在内部把添加的值1当做key，把空的object对象当做value，使用内部的map添加该key-value

当我们往HashMap中添加一个key-value时，首先会为key计算一个hash值，然后通过该hash值求得该key应该在哈希表的哪个索引位置，然后对该位置的链表进行遍历，如果不存在与该key对应的hash值，则存入；如果存在和key相同的hash值，就调用equals方法比较key是否相等来匹配这两个元素是否相同。

　　从上面可以看到，Set其实是通过hashcode来减少了euqals的次数，从而提升效率，也就是说hashcode和euqals是紧密联系的。

#hashCode和equals

在Effective Java中的第8条和第9条中分别提到了对equals和hashCode的规则

对于euqals应该遵守如下约定：
　　1、自反性：x.equals(x) 必须为true
　　2、对称性：如果x.equals(y)，则y.euqals(x)必须为true
　　3、传递性：如果x.equals(y)返回是“true”，而且y.equals(z)返回是“true”，那么z.equals(x)也应该返回是“true”
　　4、一致性：如果x.equals(y)返回是“true”，只要x和y内容一直不变，不管你重复x.equals(y)多少次，返回都是“true”
　　5、任何情况下，x.equals(null)，永远返回是“false”；x.equals(和x不同类型的对象)永远返回是“false”
　　6、覆盖equals时总是要覆盖hashCode

对于hashCode应该遵守如下约定：
　　1、在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。
　　2、如果两个对象根据equals(Object o)方法是相等的，则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。
　　3、如果两个对象根据equals(Object o)方法是不相等的，则调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，则可能提高散列表的性能。

　　总结：
　　1、如果x.equals(y)返回“true”，那么x和y的hashCode()必须相等。
　　2、如果x.equals(y)返回“false”，那么x和y的hashCode()有可能相等，也有可能不等。

举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Student{
    int age;
    int sex;
    String name;
    public Student(int age, int sex, String name) {
        super();
        this.age = age;
        this.sex = sex;
        this.name = name;
    }
    //省略get和set方法
    @Override
    public int hashCode() {
        System.out.println("调用了hashCode方法...");  
        int hashResult = 1;  
        hashResult = (hashResult + Integer.valueOf(age).hashCode() + name.hashCode()) * 99;  
        System.out.println("name:"+name +" hashCode:" + hashResult);  
        return hashResult;  
    }
    @Override
    public boolean equals(Object obj) {
        System.out.println("调用了equals方法...");
        if(obj == null) 
            return false;
        if(obj == this) 
            return true;
        if(obj.getClass() != this.getClass()) 
            return false;
        Student p = (Student) obj;
        if(getAge() != p.getAge() || getSex() != p.getSex()) 
            return false;
        if(getName() != null){
            if(!getName().equals(p.getName()))
                return false;
        }
        return true;
    }
}
public class Equals1 {
    public static void main(String[] args){
        Student p1 = new Student(1, 1, "张三");
        Student p2 = new Student(2, 1, "李四");
        Student p3 = new Student(1, 1, "张三");
        Student p4 = new Student(1, 1, "李四");
        System.out.println("p1==p3 : " + (p1 == p3));
        System.out.println("p1.equals(p3) : " + (p1.equals(p3)));
        System.out.println();
        HashSet<Student> set = new HashSet<Student>();
        set.add(p1);
        set.add(p2);
        set.add(p3);
        set.add(p4);
        System.out.println("set.size : " + set.size());
    }
}

结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p1==p3 : false
调用了equals方法...
p1.equals(p3) : true
调用了hashCode方法...
name:张三 hashCode:78610752
调用了hashCode方法...
name:李四 hashCode:67229415
调用了hashCode方法...
name:张三 hashCode:78610752
调用了equals方法...
调用了hashCode方法...
name:李四 hashCode:67229316
set.size : 3

　分析：
　　1、p1 和 p3 的属性相同，但是他们指向不同的对象，所以p1==p3为false
　　2、p1 和 p3 虽然指向不同的对象，但属性相同，因此equals返回true
　　3、Student类覆盖了hashCode和equals方法，且hashcode值通过类的age和name属性来求得，p1 和 p3 具有相同的属性，当增加p3时，由于hashcode相同，因此会调用equals，最后发现值相同，所以去除重复

热评文章