有关在HashSet中hashcode冲突的有关问题

有关在HashSet中hashcode冲突的问题
   为什么存放在HashSet里面的对象，如果重写了equals()方法一定要写重写hashcode()方法，也就是说为什么要保证equals()方法比较相等的对象，其hashcode()方法返回值也要一样才可以。
   首先，我给出一个例子大家看看，写一个Person类，只是覆盖了equals()方法。
   

class Person{private String name;private int age;public Person(int age, String name) {super();this.age = age;this.name = name;}public boolean equals(Object obj) {if (this == obj)return true;if (obj == null)return false;if (getClass() != obj.getClass())return false;Person other = (Person) obj;if (age != other.age)return false;if (name == null) {if (other.name != null)return false;} else if (!name.equals(other.name))return false;return true;}@Overridepublic String toString() {return this.name + " :" + this.age;}}   

下面给出测试类的代码：

     public class HashSetResearch {public static void main(String[] args) {         Set<Person> s = new HashSet<Person>();Person p1 = new Person(22,"zhongyao");Person p2 = new Person(22,"zhongyao");s.add(p1);s.add(p2);for(Person temp : s){System.out.println(temp);}}}程序运行结果为：zhongyao :22zhongyao :22    

    在HashSet中，不可以装重复的对象，这个是大家都知道的，具体描述可以见jdk中的HashSet类的相关javadoc描述。

     /**     * Adds the specified element to this set if it is not already present.     * More formally, adds the specified element <tt>e</tt> to this set if     * this set contains no element <tt>e2</tt> such that     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.     * If this set already contains the element, the call leaves the set     * unchanged and returns <tt>false</tt>.     *     * @param e element to be added to this set     * @return <tt>true</tt> if this set did not already contain the specified     * element     */    public boolean add(E e) {return map.put(e, PRESENT)==null;    }    

    e==null ? e2==null : e.equals(e2), 这说明在HashSet里不能拥有和e相同的element的，相同的条件是同时为null或者equals()方法返回true。这时候你可能会问，那为什么上面的p2会被加入到s中呢？
在你调用HashSet的时候发生了很多事情，其中就有用到对象的hashcode()方法，我将把整个流程的调用过程详细列出。

public boolean add(E e) {return map.put(e, PRESENT)==null;}这个HashSet源代码中的add方法。map是HashSet实例中的一个成员变量：private transient HashMap<E,Object> map;PRESENT也是一个成员变量，不过比较特别：// Dummy value to associate with an Object in the backing Mapprivate static final Object PRESENT = new Object();    这个只是一个”傀儡值”，后面你会看到，在放入到map中是会作为value。既然它调用了HashMap的put(K k, V v)方法，我们就去看看这个方法。这个代码不是很长，认真看还是很好懂的。为了方便，我还是把我的个人理解的注释放到代码之中了    public V put(K key, V value) {        if (key == null)            return putForNullKey(value);//这个就是键值为空，不用多说了        //获取你放入的key对象的hashcode，看上面就知道这个key指向的就是你想要        //插入的对象，当然在HashMap里做了进一步的处理，事实上就是一些逻辑运算        //有兴趣的可以自己查看        int hash = hash(key.hashCode());        //这个i很有用处，从下面的代码可以看出它是定位你要插入的对象放入到table中的        //位置的，这个table是一个Entry类的数组，是个成员变量，后面会给大家看这个类的        //源代码。从indexFor()的源代码来看只有一行，简单的说就是i=hash&（talbe.length-1）        //有点hash函数的味道。        int i = indexFor(hash, table.length);        //这个for循环就是为你要插入的对象找到一个更精确的位置，可能在table中i的地方已经有        //人了，那么就要找下一个，如果大家有比较好的数据结构的功底的话应该比较容易理解，        //这里处理hash冲突的方法就是在表中具有相同hashcode那一项做链表处理（链地址法）        //这些仅仅从for语句的括弧中的三句就可以看的出来        for (Entry<K,V> e = table[i]; e != null; e = e.next) {            Object k;            //以下的这个条件满足，你要插入的对象才不会被插入            //首先第一个就是hashcode，这个不难理解，记得运算是可逆的            //((k = e.key) == key这个的意思是你要插入的对象和当前遍历到的e指向同一个对            //像，当然不能被加入。后面这个key.equals(k)就不多说了。            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {                V oldValue = e.value;                e.value = value;                e.recordAccess(this);// do nothing                //以上是存在相同时做出新值代替旧值                return oldValue;            }        }        modCount++;        //通过上面的for循环找到一个位置了，那么就可以在该方法里直接加如就可以了，这个        //就交给你们去查看了        addEntry(hash, key, value, i);        return null;} 

这个在所有的set中几乎是差不多的，大家可以自己看看。提一点，在TreeSet中，还额外要求compareTo()返回一样，即equals()返回true时，compareTo()要返回0


问题：
    在加入到hashset之后，修改对象的状态和其它的一样，那么也是可以的，不会自动断裂，这个就是我想要了解了，这个破坏了set的唯一性。


hashCode

当使用toString方法的时候返回一个 "类型名@#$%#^%$ "的东西，比如一个****@4e57de。"@ "前面的是你的类名，后面的就是散列码的16进制表示。

hashCode 叫哈希代码或称散列码，简单的说就是通过哈希算法算出来的一大窜数字之类的东西和内存有关。默认的实现是将对象内部地址转化为整数作为HashCode，这当然能保证每个对象具有不同的HasCode，因为不同的对象内部地址肯定不同(废话)。因此你可以简单理解为对象在内存中的地址 担不是绝对物理地址。

hashCode()

Java中的集合（Collection）有两类，一类是List，再有一类是Set。前者集合内的元素是有序的，元素可以重复；后者元素无序，但元素不可重复。

那么这里就有一个比较严重的问题了：要想保证元素不重复，可两个元素是否重复应该依据什么来判断呢？

当我们向HashSet集合中添加元素时，它是按hash算法来存储集合中的元素。首先 HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据该hashCode值决定该对象在HashSet中的存储位置。如果两个元素通过equals方法比较返回true，但它们的hashCode()方法返回值不相等，HashSet将会把它们存储在不同位置，也就添加成功。

简单的说，HashSet集合判断两个元素的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值也相等。看下面例子：

import java.util.*;//类A的equals方法总是返回true,但没有重写其hashCode()方法class A{     public boolean equals(Object obj){          return true;     }}//类B的hashCode()方法总是返回1,但没有重写其equals()方法class B{     public int hashCode(){          return 1;     }}//类C的hashCode()方法总是返回2,但没有重写其equals()方法class C{     public int hashCode()    {          return 2;     }     public boolean equals(Object obj)   {          return true;     }}public class TestHashSet{     public static void main(String[] args){          HashSet books = new HashSet();          //分别向books集合中添加2个A对象，2个B对象，2个C对象          books.add(new A());          books.add(new A());          books.add(new B());          books.add(new B());          books.add(new C());          books.add(new C());          System.out.println(books);     }}

运行上面的程序，看到如下运行结果：

[B@1,B@1,C@2,A@c17164, A@de6ced]

从上面的程序可以看出，即使两个A对象通过equals比较返回true，但HashSet依然把它们当成2个对象；即使2个B对象的hashCode()返回相同的值（都是1），HashSet依然会把它们当成2个对象。

总结：如果需要某个类的对象保存到HashSet集合中，重写这个类的equals()方法和hashCode()方法，应该尽量保证两个对象通过equals比较返回true时，它们的hashCode方法返回值也是相等.

为什么会先调hashCode()方法呢？

大家可以想想，如果集合中现在已经有1000个元素，那么第1001个元素加入集合时，它就要调用1000次equals方法。这显然会大大降低效率。

通过hashCode()方法返回的是hashcode码。这样一来，当集合要添加新的元素时，先调用这个元素的hashCode（）方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

查看更多 下一篇