黑马程序员技术交流社区

标题: 今天面试了，惨痛教训(其实主要讲Set集合) [打印本页]
作者: chslzj    时间: 2013-7-13 22:22
标题: 今天面试了，惨痛教训(其实主要讲Set集合)
本帖最后由 chslzj 于 2013-7-13 22:46 编辑

      今天面试，面试老师问了这样一个问题，"Set里面的元素是怎样判断是否重复的?"我答，是通过hashcode方法和equals方法实现的（这里我的表述也有问题，Set自身也有hashcode和equals方法，但是这两个方法做的是Set与Set的比较，里面的元素应该是通过contains方法来判断是否相等，具体的实现应该是元素的hashcode与equals方法来判断的），我觉得面试老师心里面的答案应该不是这个，好吧，这个疑惑一直我心里，面试完了，来逛论坛，发现一帖子，”这几个Java基础面试题不错哟“，
里面的第十三条

13、Set里的元素是不能重复的,那么用什么方法来区分重复与否呢? 是用==还是equals()? 它们有何区别

答:Set里的元素是不能重复的,那么用iterator()方法来区分重复与否。equals()是判读两个Set是否相等

难道真的是iterator？iterator是迭代啊，迭代怎么判断啊？？？？百度了一下，都是这个答案，我就不相信，我要探究竟！！！

我带着怀疑的态度去查API

首先，Set是一个借口类，这个毫无疑问，然后判断是否重复的方法可以从两个方法里面存在，一个是add（添加成功或者失败，因为是否重复），还有一个是contains（是否含有这个元素），但是Set类源码没有具体的实现过程，这里我就选取了HashSet这个实现类的源码来观察这个问题。

首先，

  1.   /**
  2.      * Returns <tt>true</tt> if this set contains the specified element.
  3.      * More formally, returns <tt>true</tt> if and only if this set
  4.      * contains an element <tt>e</tt> such that
  5.      * <tt>(o==null ? e==null : o.equals(e))</tt>.
  6.      *
  7.      * @param o element whose presence in this set is to be tested
  8.      * @return <tt>true</tt> if this set contains the specified element
  9.      */
  10.     public boolean contains(Object o) {
  11.         return map.containsKey(o);
  12.     }
复制代码
这是hashSet的contains方法，它调用了一个map对象的方法，然后通过这个我们去看看这个map对象是什么吧
  1.    private transient HashMap<E,Object> map;
复制代码
下面HashSet的空的构造方法
  1.    public HashSet() {
  2.         map = new HashMap<E,Object>();
  3.     }
复制代码
看到这里，我想大家应该都明白了，HashSet其实就是一个包装后的HashMap，并且把HashSet里面的元素作为HashMap的Key值，现在我们去这个HashMap里面去看看他的containsKey方法是怎样实现的。
  1.   /**
  2.      * Returns <tt>true</tt> if this map contains a mapping for the
  3.      * specified key.
  4.      *
  5.      * @param   key   The key whose presence in this map is to be tested
  6.      * @return <tt>true</tt> if this map contains a mapping for the specified
  7.      * key.
  8.      */
  9.     public boolean containsKey(Object key) {
  10.         return getEntry(key) != null;
  11.     }
复制代码
好吧，又失败，它还是调用getEntry（key）方法，判断有没有得到一个元素来实现，继续找getEntry(key)方法
  1.     /**
  2.      * Returns the entry associated with the specified key in the
  3.      * HashMap.  Returns null if the HashMap contains no mapping
  4.      * for the key.
  5.      */
  6.     final Entry<K,V> getEntry(Object key) {
  7.         int hash = (key == null) ? 0 : hash(key.hashCode());
  8.         for (Entry<K,V> e = table[indexFor(hash, table.length)];
  9.              e != null;
  10.              e = e.next) {
  11.             Object k;
  12.             if (e.hash == hash &&
  13.                 ((k = e.key) == key || (key != null && key.equals(k))))
  14.                 return e;
  15.         }
  16.         return null;
  17.     }
复制代码
真像了，这个方法首先得到key的hashcode值，再hash一次，得到一个hash的table（table其实是一个Entry[]），然后遍历这个table，如果存在元素，判读元素的hashcode值是否是否与key的hashcode相等并且key指向了同一个元素或者里面的值可以通过equals方法返回真（不等于空我就不说了，感觉不好描述啊），然后选择返回对象e（成功找到对象，说明存在）或者返回null（就是不存在啦），好吧，到这里的结论是,HashSet底层的是由元素的hashcode方法与equals方法得到是否存在相同元素的，当然问题也不是这样结束了，我们还没有看Add方法呢

这是HashSet的Add方法

  1.    /**
  2.      * Adds the specified element to this set if it is not already present.
  3.      * More formally, adds the specified element <tt>e</tt> to this set if
  4.      * this set contains no element <tt>e2</tt> such that
  5.      * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
  6.      * If this set already contains the element, the call leaves the set
  7.      * unchanged and returns <tt>false</tt>.
  8.      *
  9.      * @param e element to be added to this set
  10.      * @return <tt>true</tt> if this set did not already contain the specified
  11.      * element
  12.      */
  13.     public boolean add(E e) {
  14.         return map.put(e, PRESENT)==null;
  15.     }
复制代码
好吧，直接去找hashmap的put方法吧
  1.   /**
  2.      * Associates the specified value with the specified key in this map.
  3.      * If the map previously contained a mapping for the key, the old
  4.      * value is replaced.
  5.      *
  6.      * @param key key with which the specified value is to be associated
  7.      * @param value value to be associated with the specified key
  8.      * @return the previous value associated with <tt>key</tt>, or
  9.      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  10.      *         (A <tt>null</tt> return can also indicate that the map
  11.      *         previously associated <tt>null</tt> with <tt>key</tt>.)
  12.      */
  13.     public V put(K key, V value) {
  14.         if (key == null)
  15.             return putForNullKey(value);
  16.         int hash = hash(key.hashCode());
  17.         int i = indexFor(hash, table.length);
  18.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  19.             Object k;
  20.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  21.                 V oldValue = e.value;
  22.                 e.value = value;
  23.                 e.recordAccess(this);
  24.                 return oldValue;
  25.             }
  26.         }

  28.         modCount++;
  29.         addEntry(hash, key, value, i);
  30.         return null;
  31.     }
复制代码
这里，如果找到了对于的Key值，就把新的值赋给了旧的值，然后返回了旧的值，上面HashSet判断是否添加成功是根据是否返回Null来判断的，这里显然不是NUll，所以是HashSet的添加返回结果是false，然后我们接着看HashMap的代码，如果for循环执行完了，还没有跳出这个方法，说明就不存在这个对象了，然后返回null，表示添加成功，结束了，这就证明了HashSet是根据元素的hashcode方法与equals方法来判断是否重复的。在开始看Set源码的时候，我就知道他们为什么说是根据iterator来判断是否有重复的了，下面贴源码

  2.     /**
  3.      * Returns <tt>true</tt> if this set contains the specified element.
  4.      * More formally, returns <tt>true</tt> if and only if this set
  5.      * contains an element <tt>e</tt> such that
  6.      * <tt>(o==null ? e==null : o.equals(e))</tt>.
  7.      *
  8.      * @param o element whose presence in this set is to be tested
  9.      * @return <tt>true</tt> if this set contains the specified element
  10.      * @throws ClassCastException if the type of the specified element
  11.      *         is incompatible with this set (optional)
  12.      * @throws NullPointerException if the specified element is null and this
  13.      *         set does not permit null elements (optional)
  14.      */
  15.     boolean contains(Object o);

  17.     /**
  18.      * Returns an iterator over the elements in this set.  The elements are
  19.      * returned in no particular order (unless this set is an instance of some
  20.      * class that provides a guarantee).
  21.      *
  22.      * @return an iterator over the elements in this set
  23.      */
  24.     Iterator<E> iterator();
复制代码

坑爹啊有木有，他们是不是草草看了这个源码，把iterator方法的说明看做是contains方法的说明了？？？！！！！，什么根据iterator方法啊？？？

我知道我面试成绩应该很差了，面试的时候确实没有解释清楚，但是，我要跟你们讲，别信什么Set是根据iterator来判断是否重复了的屁话了。

--------------------------------------------------------------------------------------------------------------------

好吧，如果我讲的有错误，请你们指出来，我虚心接受

ps.版主，手抖一抖，技术分,额


作者: 风乐    时间: 2013-7-13 22:29
lz面试多少分，话说我回答的也是hashCode()和equals()方法来判断元素是否相同的，顶楼主
作者: chslzj    时间: 2013-7-13 22:31
风乐 发表于 2013-7-13 22:29
lz面试多少分，话说我回答的也是hashCode()和equals()方法来判断元素是否相同的，顶楼主 ...

还有N多错误，N多不会，惨痛经历，讲出来就是泪，不讲了
作者: 花心々小土豆    时间: 2013-7-14 14:57
我觉得应该是equals()方法吧，HashSet中有hashCode()，如果是TreeSet呢？
就是往Set集合中添加元素时，它会通过equals()方法和集合里的元素比较，然后确保唯一。
HashSet中元素的存储方法和其他不太一样，它是先根据hashCode()得到一个值，这个值会减少新加进来元素与已有元素的比较次数，就是hashCode()得到的值下可能只有很少的几个元素，然后还是用equals()判断是不是重复元素。
TreeSet底层是二叉树存储结构，就是规定根结点的左边比右边的元素小，进来一个新的元素肯定能找到它对应的位置，如果有元素和它相同（用equals()判断）不存。
作者: chslzj    时间: 2013-7-14 17:07
花心々小土豆 发表于 2013-7-14 14:57
我觉得应该是equals()方法吧，HashSet中有hashCode()，如果是TreeSet呢？
就是往Set集合中添加元素时，它会 ...

我就看了hashSet的源码，其他的源码就没有看了:P
作者: a767175432    时间: 2013-7-14 19:00
Set集合是通过equals方法和hashcode方法来判断的,
作者: zhou5852    时间: 2013-7-14 19:07
如果是我说 我就说 Set 是一接口  我的子类中想怎么设计判断都行，我可以只通过hashcode()判断  也可以通过equals()方法判断。。。也可以结合，我还可以在我的对象中再添加一个函数   在Set的类中判断。。。。
作者: 赵乐    时间: 2013-7-15 00:05
我觉得老师没有想要你回答这么详细，  可能是要你回答他两个子类的分别实现唯一的方法吧
Set
        (1)元素无序,唯一。
        (2)Set的两个子类：
                        |--HashSet
                                无序,唯一。
                                如果保证的呢？
                                它依赖于两个方法：hashCode()和equals()
                                首先判断hashCode()值是否相同：
                                        是：继续equals()方法
                                                返回值true：说明元素重复，不添加。
                                                返回值false：直接添加到集合中
                                        否：直接添加到集合中。

                                |--LinkedHashSet
                                        有序,唯一。
                                        通过链表结构保证有序。
                                        通过哈希表结构保证唯一。
                        |--TreeSet
                                有序,唯一
                                如何保证的呢？
                                它根据返回值是否是0来判断是否重复。
                                实现方案：
                                方式1：元素本身具备比较性
                                        实现Comparable接口
                                方式2：集合具备比较性
                                        实现Comparator接口



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2