Question on HashSet

[Amit Mukherjee]

Hi,

Could someone please explain the following to me?

import java.util.*;

public class TestSet
{
	public static void fill(Collection c)
	{
		for(int i=0; i<5; i++)
			c.add(Integer.toString(i));
	}

	public static void print(Collection c)
	{
		for(Iterator it=c.iterator(); it.hasNext();)
			System.out.println(it.next());
	}

	public static void testSet(Set a)
	{
		fill(a);
		a.addAll(a);
		print(a);
	}

	public static void main(String[] args)
	{
		testSet(new HashSet());
	}
}

The output is:

3
2
1
0
4
3
2
1
0
4

I expected the output to be just one set of values :
3
2
1
0
4

Tha javadoc says: If the specified collection is also a set, the addAll operation effectively modifies this set so that its value is the union of the two sets.

Then why are the values coming twice? Has it got something to do with the hashcode of the objects?

Thanks.

[James Ward]

You are indeed adding the values to hashset twice!

# fill(a); //once here
# a.addAll(a); //again here

So, the result is correct and expected.

[Amit Mukherjee]

James Ward wrote:You are indeed adding the values to hashset twice!

# fill(a); //once here
# a.addAll(a); //again here

So, the result is correct and expected.

Thanks James. But what I intended was that even if I add twice, HashSet should store it only once as duplicate values are not allowed in HashSet.

For e.g. If I do this:
fill(a);
fill(a);
a.add("1");

the result is still:
3
2
1
0
4

[Campbell Ritchie]

I tried it and got

campbell@queeg:~/java$ java TestSet
3
2
1
0
4
campbell@queeg:~/java$ javac TestSet.java

[Dhaval Hansaliya]

Hi Amit,

i have executed your code on my machine. it gives below output:

3
2
1
0
4

as expected.

thanks,

[Amit Mukherjee]

Now I am doubly confused!

Someone please help!! Why am I getting a different output? I have java version "1.6.0_13"

[James Ward]

From JavaDocs (http://java.sun.com/j2se/1.4.2/docs/api/java/util/AbstractCollection.html#addAll(java.util.Collection))

Adds all of the elements in the specified collection to this collection (optional operation). The behavior of this operation is undefined if the specified collection is modified while the operation is in progress. (This implies that the behavior of this call is undefined if the specified collection is this collection, and this collection is nonempty.)

That explains it?

[Amit Mukherjee]

Ahh..that might explain. Thanks a lot James.

What's surprising is the output changes with java versions. So with java version "1.4.2_14" the output is
3
2
0
4
1

whereas with java version 1.5 and higher, the output is:

3
2
1
0
4
3
2
1
0
4

Is this a bug with java 1.5 & higher versions?

[Henry Wong]

Amit Mukherjee wrote:
Is this a bug with java 1.5 & higher versions?

Well, "bug" implies that it is not working as specified. If the documentation states that the result is undefined, then how can it be considered a "bug"?

Henry

[Campbell Ritchie]

I got only one lot of output with Java6.

I went into src.zip and the addAll method appears to be un-overridden from AbstractCollection, and here it is:

    /**
     * {@inheritDoc}
     *
     * <p>This implementation iterates over the specified collection, and adds
     * each object returned by the iterator to this collection, in turn.
     *
     * <p>Note that this implementation will throw an
     * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
     * overridden (assuming the specified collection is non-empty).
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     * @throws IllegalStateException         {@inheritDoc}
     *
     * @see #add(Object)
     */
    public boolean addAll(Collection<? extends E> c) {
	boolean modified = false;
	Iterator<? extends E> e = c.iterator();
	while (e.hasNext()) {
	    if (add(e.next()))
		modified = true;
	}
	return modified;
    }

So I looked up add in HashSet and found this:

    /**
     * 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 ? e2==null : 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;
    }

Can't see how you manage to double the contents of a Set like that. I altered the original class like this

import java.util.*;
import static java.lang.System.*;

public class TestSet
{
	public static void fill(Collection c)
	{
		for(int i=0; i<5; i++)
		{
		    Object obj = Integer.toString(i);
			c.add(obj);
			out.printf("Type = %s, hash code = %h, value = %<s%n", obj.getClass().getName(), obj);
		}
	}

	public static void print(Collection c)
	{
		for(Iterator it=c.iterator(); it.hasNext();)
			System.out.println(it.next());
	}

	public static void testSet(Set a)
	{
		fill(a);
		out.printf("%sadding elements%n", a.addAll(a) ? "" : "Not ");
		print(a);
	}

	public static void main(String[] args)
	{
		testSet(new HashSet());
	}
}

and got this output

campbell@queeg:~/java$ java TestSet
Type = java.lang.String, hash code = 30, value = 0
Type = java.lang.String, hash code = 31, value = 1
Type = java.lang.String, hash code = 32, value = 2
Type = java.lang.String, hash code = 33, value = 3
Type = java.lang.String, hash code = 34, value = 4
Not adding elements
3
2
1
0
4
campbell@queeg:~/java$

That is behaving as I would expect, using Java6u14.
Maybe somebody who is getting different outputs would like to try those alterations.