一、容器中的hashcode和euqals

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

    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; 
                e.value = value; 
                e.recordAccess(this); return oldValue; 
            } 
        } 
 //修改次数+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方法来匹配这两个元素是否相同。

  从上面可以看到,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()有可能相等,也有可能不等。

三、举例

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()); 
    } 
}

结果如下:

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,最后发现值相同,所以去除重复

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

Java容器(五):LinkedHashMap实现原理详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。