CODEWITHSUNDEEP
javahashset
Joker
Joker

Reputation: 11146

Hash Set add method is not working fine

I wrote a dummy program , that adds object in Hash Set. I created a class Car that has capacity of 5 people.

Now issue is i got different out put from different Main programs .

Kindly find the 2-Main programs below.

First Main Program is 

  public class Main_1 {
    static int counter = 0;

    public static void main(String args[]) {

        Car car = new Car();
        for (int i = 0; i < 20; i++) {
            car.add(new Person());
        }
        car.done();

    }

     }

The out put of Main_1 is : Exception in thread "main" java.lang.IllegalStateException: I'm full at Car.add(Car.java:10) at Main_1.main(Main_1.java:8)

Second Main program is 

   public class Main_2 {
    static int counter = 0;
    static Car car = new Car();

    public static void main(String args[]) {
        car.add(new RecursivePerson());
        car.done();
    }

    static class RecursivePerson extends Person {
        public int hashCode() {
            if (++counter < 20) {
                car.add(new RecursivePerson());
            }
            return super.hashCode();
        }
    }
}

The out put of Main_2 is I'm a car with 20 people!

Below is the business logic of my program. 

      import java.util.HashSet;
      import java.util.Set;

        public class Car {
        private static final int CAPACITY = 5;
        private Set<Person> people = new HashSet<Person>();

        public synchronized void add(Person p) {
            if (people.size() >= CAPACITY) {
                throw new IllegalStateException("I'm full");
            } else {
                people.add(p);
            }
        }

        public synchronized void done() {
            if (people.size() == 20) {
                // The goal is to reach this line
                System.out.println("I'm a car with 20 people!");
            }
        }
      }

        class Person {
         }

Can some one tell my why java is behaving like this.

Upvotes: 0

Views: 7728

Answers (3)

Alex
Alex

Reputation: 534

It is because in Main_2 you are calling add recursively. The initial call to .add() method will not return to actually increment the size of people list. So, people.size() so it will always return 0, altough you added a lot of elements there.

if you do a little debugging, you will see the callstack after a couple of iterations in Main_2 looks like this:

enter image description here

Upvotes: 0

univise
univise

Reputation: 509

HashSets are implemented using a HashMap. Let us have a look at the source HashSet's source for add, according to GrepCode:

public boolean add(E e) 
{
    return map.put(e, PRESENT)==null;
}

Let us follow this to the put implementation in HashMap, according to GrepCode:

public V More ...put(K key, V value) 
{
     if (key == null)
         return putForNullKey(value);
     int hash = hash(key.hashCode());
     int i = indexFor(hash, table.length);
     for (Entry<K,V> e = table[i]; e != null; e = e.next) 
     {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
         {
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
         }
    }

     modCount++;
     addEntry(hash, key, value, i);
    }

Your object is added in the last line with the use of addEntry. However, hashCode is called in the 3rd line before the entry is added; in the end, this cause put to be called again. Because your hashCode method adds until you have 20 element the size of the set is 20 in the end.

Upvotes: 0

Hoopje
Hoopje

Reputation: 12932

The difference is because of the way that a HashSet works: if you add an new element to it, it first checks if the object is already in the set, and if it isn't, it adds this to the set. In order to check if the object is in the set, it call hashCode() on the object.

Your second program is specifically designed to bypass the capacity check of the car. You override hashCode() in the objects you add to the hashset. This method is called by the HashSet.add method, but before the object was actually added to the set. In the overridden hashCode() method you add the additional elements to the set. That is, if Car.add() is called, the size of the hash set is always 0, and the capacity check will always pass.

Upvotes: 5

Related Questions