hashCode with same elements but different values

Question

This is my Heap 12 File i keep on getting an error on my hashCode()... Please help, I am getting an assertion error when it should be even It looks similar to my peer's codes and the tutors cannot figure it out either. http://ieng6.ucsd.edu/~cs12s/Assignments/P4/README.html <--- this link may help.

import java.util.*;
import junit.framework.*;                        //Used for JUnit

public class Heap12<E extends java.lang.Comparable<? super E>> implements PQueue<E>
{

private int size; //initialize the size
private E[] listArr; //initialize the list

public Heap12()
{
    size = 0; //size is zero
    listArr = (E[]) new Comparable[5]; //the capacity is starting at 5
}

public Heap12(Heap12<E> present) 
{
    listArr = (E[]) new Comparable[present.listArr.length];
    for(int i = 0; i < present.listArr.length; i++) //this is used to copy
        listArr[i] = present.listArr[i];
    size = present.size; //set the size
} 

public void add(E e)
{   
    if(e == null) //if there is nothing to add
        throw new NullPointerException();
    else if(size == listArr.length) //if the size is equal
    {                                                             //to the length
        E[] duplicate = (E[]) new Comparable[listArr.length * 2];
        for(int i = 0; i < listArr.length; i++) //make the length longer
            duplicate[i] = listArr[i]; //duplicate the array
        listArr = duplicate; //make listArr equal to the duplicate
    }

    listArr[size] = e; //add the element
    size++; //incremenet the size
    bubbleUp(size-1); //update treee
}

public boolean equals(java.lang.Object o)
{
    if(o == null) //if o is a null object.
        return false; 
    else if(o instanceof Heap12) // if the compared hting does not equal 0
        return false;
    else if(((Heap12<E>)o).size() != this.size())
        return false; //check if the size matches
    for(int i = 0; i < listArr.length; i++) //go through every value
        if(((Heap12<E>)o).listArr[i] != this.listArr[i])
return false; // in the array and if one does no equal
    return true;
}

public int hashCode()
{
    int hashCode = 1;
    for (E e : listArr)
        hashCode = 31 * hashCode +(e == null ? 0 : e.hashCode());
    return hashCode;
} 

public boolean isEmpty()
{
    if(size == 0) //check if it the heap is empty
        return true;//then return true
    else
        return false;//if its not empty return false
}

public E peek()
{
    if(size == 0) //if there is nothing to peek
        return null;//reutrn null
    return (E) listArr[0]; //return the parent
}

public E remove()
{
    if(size == 0) //if there is nothing to remove
     return null; //reuturn null
    E e = (E)listArr[0]; //save the value of the parent
    listArr[0] = listArr[size-1]; //move the parrent
    size--; //decrement size
    trickleDown(0); //update tree
    return e; //returned delted value
}

public int size()
{
    return size;//return size
}

private Heap12(E[] e)
{
    listArr = e; 
    size = 0; //the size is big as the length 
}

public static <T extends java.lang.Comparable<? super T>> void sort(T[] t)
{
    if(t == null) //throw null Pointer Exception if it is Null.
        throw new NullPointerException();     
    Heap12<T> sortHeap = new Heap12<T>(t);    //instantiate
    for(int i = 0; i < t.length; i++)
        sortHeap.add(t[i]);
    for(int i = sortHeap.size()-1; i >= 0; i--) //sort it
        t[i] = sortHeap.remove();
}

private void bubbleUp(int place)
{
    int parent = (place - 1) / 2; //find where the parent it
    if(place == 0) //return if thereis no parent
        return;
    if( ((E)listArr[place]).compareTo(((E)listArr[parent])) > 0)
        swap(listArr, place, parent); //if the place is greater than parent
    bubbleUp(parent);                             //switch the values and do for all values.
}

private void trickleDown(int place)
{
    int left = (2 * place) + 1; //instantiate left and right
    int right = (2 * place) + 2;
    if(place == size-1)
        return;
    if(left >= size)
        return;
    if(listArr[left] == null)
        return;
    if(size==2) //if only 2 nodes left with parent and left
    {
        if(listArr[place].compareTo(listArr[left]) < 0)
            swap(listArr, place, left);    //swap them
    }
    while( right < size && ((listArr[place].compareTo(listArr[left]) < 0) ||
    (listArr[place].compareTo(listArr[right]) < 0)))    //keep going as long
    {     // as right node isn't null and if there are higher priorites
        if(listArr[left].compareTo(listArr[right]) > 0)
        {   //left child with higher priority
            swap(listArr, place, left);
place = left; //swap left and parent
        }
        else //right child has high priorty
        {
            swap(listArr, place, right);
place = right; //swap parent and right
        }
        left = (2 * place) + 1;
        right = (2 * place) + 2;
    }
}
private void swap(E[] objectA, int place1, int place2)
{
    E temp = objectA[place1]; //save the temp value so it won't
    objectA[place1] = objectA[place2]; //be lost and then replace with
    objectA[place2] = temp; //desired value then switch it
}
}

This is my tester method, That i am tyring to pass hashCode().

import java.util.*;
import junit.framework.*;            //Used for JUnit

public class Heap12Tester extends TestCase
{

public static void main(String args[])
{
  junit.swingui.TestRunner.main(new String[] {"Heap12Tester"}); 
 }

 public void testhashCode()
 {
 Heap12<Integer> sampleHeap = new Heap12<Integer>(); //instantiate two
 sampleHeap.add(100); //add two vales
 sampleHeap.add(0);
 Heap12<Integer> sampleHeap2 = new Heap12<Integer>(sampleHeap);
 assertEquals(sampleHeap.hashCode(), sampleHeap2.hashCode());
 sampleHeap.add(1000); //make the heaps uneven
 assertFalse(sampleHeap.hashCode() == sampleHeap2.hashCode());
 sampleHeap.remove(); //remove the values added

 assertTrue(sampleHeap2.equals(sampleHeap)); // <--------------------- error here
 assertTrue(sampleHeap.hashCode() == sampleHeap2.hashCode()); <--------- andhere
  }
  }

Answer 1

Your remove method does not do what you seem to expect. In particular this:

listArr[0] = listArr[size-1];

changes the order of the elements and therefore the hashcode.

In other words, adding then removing an element does not leave the heap unchanged.

You can iterate over the elements of your two heaps and print them to verify what the difference is.

EDIT

I have slightly amended your test to print the content of your array (which I have made public for this):

public void testhashCode() {
    Heap12<Integer> sampleHeap = new Heap12<Integer>(); //instantiate two
    sampleHeap.add(100); //add two vales
    sampleHeap.add(0);
    Heap12<Integer> sampleHeap2 = new Heap12<Integer>(sampleHeap);
    assertEquals(sampleHeap.hashCode(), sampleHeap2.hashCode());
    System.out.println(Arrays.toString(sampleHeap.listArr));
    sampleHeap.add(1000); //make the heaps uneven
    System.out.println(Arrays.toString(sampleHeap.listArr));
    assertFalse(sampleHeap.hashCode() == sampleHeap2.hashCode());
    sampleHeap.remove(); //remove the values added
    System.out.println(Arrays.toString(sampleHeap.listArr));

    assertTrue(sampleHeap2.equals(sampleHeap));
    assertTrue(sampleHeap.hashCode() == sampleHeap2.hashCode());
}

and it outputs:

[100, 0, null, null, null]
[1000, 0, 100, null, null]
[100, 0, 100, null, null]

So adding and removing has left an extra element in your list.

Answer 2

Just for clarification... what fixes the remove method? I'm not clear on what would fix the issue. Wouldn't the issue lie in the trickledown method?