Results 1 to 5 of 5
  1. #1
    j2me64's Avatar
    j2me64 is offline Senior Member
    Join Date
    Sep 2009
    Location
    Zurich, Switzerland
    Posts
    962
    Rep Power
    5

    Default question about HashSet and TreeSet

    as well known the Set interface is used when you don't want any duplicates in your collection. to detect equality when using add() the HashSet uses the (overriden) methods hashCode and equals(). the hashCode identify the bucket in the collection and if there are already objects in it the method equals() is used to detect equality on the objects. i would say, what happens behind the scenes with HashSet is clear to me. but with the TreeSet, it seems this class uses only the comparator or comparable to detect equality. Reading the java api 7, I would say yes:

    Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.
    using this class

    Java Code:
    public class Person implements Comparable<Person>{
    	private String name;
    	private int age;
    	
    	public Person(String n, int a) {
    		this.name = n;
    		this.age= a;
    	}
    	
    	@Override
    	public String toString() {
    		return name + "(" + age+ ")";
    	}
    	
    	public String getName() {
    		return name;
    	}
    
    	public int getAge() {
    		return age;
    	}
    
    	@Override
    	public boolean equals(Object o) {
    		if (o instanceof Person && this.getName().compareTo(((Person)o).getName()) == 0 
    				&& this.getAge()-((Person)o).getAge()==0) {
    			return true;
    		} else {
    			return false;
    		}
    	}
    	
    	@Override
    	public int hashCode() {
    		int result = 37;
    		result += result + this.getName().hashCode();
    		result += result + this.getAge();
    		return result;
    	}
    	
    	@Override
    	public int compareTo(Person p) {
    		return this.getName().compareTo(p.getName());
    	}
    }
    and this code to add two person objects

    Java Code:
    	Set<Person> set = new TreeSet<Person>();
    	boolean[] b = new boolean[2];
    	Person p1 = new Person("Harry", 48);
    	Person p2 = new Person("Harry", 17);
    	b[0] = set.add(p1);
    	b[1] = set.add(p2);
    the boolean inside b[1] is false, so p2 was not added. why?
    Last edited by j2me64; 03-03-2012 at 06:35 PM.

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: question about HashSet and TreeSet

    Add some debug printlns to your methods to see when they are called and what the values they return are.
    The output should show you what the code is doing.

  3. #3
    j2me64's Avatar
    j2me64 is offline Senior Member
    Join Date
    Sep 2009
    Location
    Zurich, Switzerland
    Posts
    962
    Rep Power
    5

    Default Re: question about HashSet and TreeSet

    ok, I added some System.out.println inside hashCode(), equals() and compareTo(). When I add the two persons to the TreeSet only the output inside the compareTo is prompted. It still seems that the TreeSet internally doesn't care about hashCode() and equals().

    For testing purposes I also added this two lines inside main()

    Java Code:
    System.out.println("p1.hashCode()==p2.hashCode: " + (p1.hashCode()==p2.hashCode()));
    	   System.out.println("p1.equals(p2): " + p1.equals(p2));
    with this output:

    p1.hashCode()==p2.hashCode: false
    p1.equals(p2): false

    so my code fullfil the 2. contract requirement of equals and hashcode
    1. if x.equals(y) returns true, then x.hashCode()==y.hashCode() must true!
    2. x.hashCode()!=y.hashCode() then x.equals(y) must return false!

    looking inside the implementation of the class TreeSet just before the method add() I got this comments

    /**
    * Adds the specified element to this set if it is not already present.
    * More formally, adds the specified element {@code e} to this set if
    * the set contains no element {@code e2} such that
    * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.eq uals(e2))</tt>.
    * If this set already contains the element, the call leaves the set
    * unchanged and returns {@code false}.
    so my question is still open: why p2 is not added to the TreeSet?

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,306
    Rep Power
    25

    Default Re: question about HashSet and TreeSet

    why p2 is not added to the TreeSet?
    Because compareTo says p1 and p2 are the same.
    When I add the two persons to the TreeSet only the output inside the compareTo

  5. #5
    j2me64's Avatar
    j2me64 is offline Senior Member
    Join Date
    Sep 2009
    Location
    Zurich, Switzerland
    Posts
    962
    Rep Power
    5

    Default Re: question about HashSet and TreeSet

    Ok, I got an other confirmation from www.coderanch.com:

    Unlike other Set implementations, TreeSet doesn't actually use equals() at all. It uses compareTo() instead - if compareTo() returns zero, that means the two objects are "equal" as far as the TreeSet is concerned. Right now, both your Lamborghinis have the same age, and compareTo says they are therefore equal to each other, and the TreeSet allows only one of the Lamborghinis to remain in the set as a result.

    If you want to test your hashCode() and equals() methods, use a HashSet, not a TreeSet.

    If you want to use a TreeSet and still see all three cars, you need to modify compareTo() so that two different Lamborghinis are not equal. Perhaps after you compare the ages, if the ages are equal, don't return 0 (yet) but instead compare something else, like vehicleID.
    I modified my compareTo() to

    Java Code:
    	@Override
    	public int compareTo(Person p) {
    		if (this.getName().compareTo(p.getName()) == 0 ) {
    		return this.getAge()-p.getAge();
    		} else {
    			return this.getName().compareTo(p.getName());
    		}
    	}
    and now also p2 is added to the TreeSet and moreover I found out why!!!!

    @norm: thanks for the assistance.
    Last edited by j2me64; 03-03-2012 at 09:17 PM.

Similar Threads

  1. problems with a TreeSet
    By j2me64 in forum Advanced Java
    Replies: 1
    Last Post: 01-10-2011, 03:40 PM
  2. Please Help - TreeSet
    By Riftara in forum New To Java
    Replies: 1
    Last Post: 10-21-2010, 08:33 PM
  3. Replies: 1
    Last Post: 08-25-2010, 07:57 PM
  4. Working with HashSet and TreeSet
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-15-2008, 07:34 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •