Equals, hashCode, sets, maps
Adapted from Effective Java, 2nd Edition
- Equals should be overridden in custom objects
- Method should satisfy contract given by http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#equals(java.lang.Object)
- Use == to check to see if parameter is reference to this object
- Use instanceof to check that argument is of correct type (automatically handles nulls)
- Cast the argument into the correct type
- Check if significant fields between objects match
- Make sure it satisfies the properties of reflexive, symmetric, transitive, and consistent
- If you override equals, you should also override hashCode (objects that are equal should have same hashCode)
public class Person {
private String firstName;
private String lastName;
private String email;
...
@Override
public boolean equals(Object o) {
// Check if o is reference to this object
if (this == o) {
return true;
}
// Make sure parameter is instance of Person
if (!(o instanceof Person)) {
return false;
}
// Cast into correct type
Person person = (Person) o;
// Compare significant fields
return (this.firstName.equals(person.firstName) &&
this.lastName.equals(person.lastName) &&
this.email.equals(person.email));
}
}- For any object x, x.equals(x) should yield true
@Test
public void testEqualsReflexive() {
assertTrue(person.equals(person));
}- If two objects x and y are equal, then
- x.equals(y) and y.equals(x) must both be true
@Test
public void testEqualsSymmetric() {
assertTrue(person1.equals(person2));
assertTrue(person2.equals(person1));
}- Given three objects, x, y, z
- If x.equals(y) and y.equals(z), then x.equals(z) must all be true
@Test
public void testEqualsTransitive() {
assertTrue(person1.equals(person2));
assertTrue(person2.equals(person3));
assertTrue(person1.equals(person3));
}- If a null value is passed into equals method, should return false
@Test
public void testEqualsNull() {
assertFalse(person1.equals(null));
}- No great way of testing consistency with junit
- Assume two objects x and y
- Assuming no references in x or_y_ have changed
- Multiple calls to x.equals(y) should return a consistent result
- Override the equals method for the following object
public class ArrayStack {
private int[] data;
private int topOfStack;
}Adapted from Effective Java, 2nd Edition
- Method should satisfy contract given by http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#hsahCode()
- Objects that are equal should have the same hashCode
- The algorithm below can be used to override hashCode
1. Store some constant nonzero value, say, 17, in an int variable called result.
2. For each significant field f in your object (each field taken into account by the equals method, that is), do the following:
a. Compute an int hash code c for the field:
i. If the field is a boolean, compute (f ? 1 : 0).
ii. If the field is a byte, char, short, or int, compute (int) f.
iii. If the field is a long, compute (int) (f ^ (f >>> 32)).
iv. If the field is a float, compute Float.floatToIntBits(f).
v. If the field is a double, compute Double.doubleToLongBits(f), and then hash the resulting long as in step 2.a.iii.
vi. If the field is an object reference and this class's equals method compares the field by recursively invoking equals,
recursively invoke hashCode on the field. If a more complex comparison is required, compute a canonical representation
for this field and invoke hashCode on the canonical representation. If the value of the field is null, return 0
(or some other constant, but 0 is traditional).
vii. If the field is an array, treat it as if each element were a separate field. That is, compute a hash code for each significant
element by applying these rules recursively, and combine these values per step 2.b. If every element in an array field is
significant, you can use one of the Arrays.hashCode methods added in release 1.5.
b. Combine the hash code c computed in step 2.a into result as follows: result = 31 * result + c;
3. Return result.
4. When you are finished writing the hashCode method, ask yourself whether
equal instances have equal hash codes. Write unit tests to verify your intuition!
If equal instances have unequal hash codes, figure out why and fix the problem.
public class hashExample {
private String stringValue;
private boolean booleanValue;
private int intValue;
private long longValue;
private int floatValue;
private int doubleValue;
private Person personValue;
private int[] arrayValue;
@Override
public int hashCode() {
int c;
// Step 1
int result = 17;
// Step 2 a vi
c = stringValue.hashCode();
result = result * 31 + c;
// Step 2 a i
c = booleanValue ? 0 : 1;
result = result * 31 + c;
// Step 2 a ii
c = (int) intValue;
result = result * 31 + c;
// Step 2 a iii
c = (int) (longValue ^ (longValue >>> 32));
result = result * 31 + c;
// Step 2 a iv
c = Float.floatToIntBits(floatValue);
result = result * 31 + c;
// Step 2 a v
c = Double.doubleToLongBits(doubleValue);
result = result * 31 + c;
// Step 2 a vi
c = personValue.hashCode();
result = result * 31 + c;
// Step 2 a viii
c = Arrays.hashCode(arrayValue);
result = result * 31 + c;
// Step 3
return result;
}
}- As long as none of fields used for equals change, then the same object should consistently return the same hashCode
@Test
public void testHashCodeConsistency() {
assertEquals(personA.hashCode(), personA.hashCode());
}@Test
public void testHashCodeEquality() {
// Assuming personA and personB are equal by the .equals method
assertEquals(personA.hashCode(), personB.hashCode());
}- Implement hashCode on your ArrayStack from earlier
- Java Set Interface
- Part of Java collection framework
- Supports, add, remove, and checking for inclusion (but not get)
- Can only contain unique elements
- Generally use HashSet or TreeSet
- Can perform mathematical set operations
- Easy to implement using hash table and only storing keys
- The union of two sets is a set of elements that belong to either A or B or to both A and B
- {1, 3, 5, 7} union {2, 3, 4, 5} = {1, 2, 3, 4, 5, 7}
- The intersection of two sets is a set where elements belong to both A and B
- {1, 3, 5, 7} intersection {2, 3, 4, 5} = {3, 5}
- The difference of two sets is the set of elements that belong to A, but not to B (defined as A - B)
- Different results for B - A
- {1, 3, 5, 7} - {2, 3, 4, 5} = {1, 7}
- {2, 3, 4, 5} - {1, 3, 5, 7} = {2, 4}
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* Perform non-destructive set operations
*
* @author Christe, Anthony
*/
public class SetFun {
/**
* Returns the union of two sets
*
* @param setA the first set
* @param setB the second set
* @return the union of the first and second set
*/
public static Set<Integer> union(Set<Integer> setA, Set<Integer> setB) {
Set<Integer> result = new HashSet<>(setA);
result.addAll(setB);
return result;
}
/**
* Returns the intersection of two sets
*
* @param setA the first set
* @param setB the second set
* @return the intersection of the first and second set
*/
public static Set<Integer> intersection(Set<Integer> setA, Set<Integer> setB) {
Set<Integer> result = new HashSet<>(setA);
result.retainAll(setB);
return result;
}
/**
* Returns the set complement setA - setB
*
* @param setA the first set
* @param setB the second set
* @return the complement of the first and second set
*/
public static Set<Integer> complement(Set<Integer> setA, Set<Integer> setB) {
Set<Integer> result = new HashSet<>(setA);
result.removeAll(setB);
return result;
}
public static void main(String[] args) {
Set<Integer> setA = new HashSet<>();
Set<Integer> setB = new HashSet<>();
setA.addAll(Arrays.asList(1, 3, 5, 7, 9, 4, 6));
setB.addAll(Arrays.asList(0, 2, 4, 6, 8, 10, 12));
System.out.println("setA\t\t\t" + setA);
System.out.println("setB\t\t\t" + setB);
System.out.println("union(setA, setB)\t" + union(setA, setB));
System.out.println("intersection(setA, setB)" + intersection(setA, setB));
System.out.println("complement(setA, setB)\t" + complement(setA, setB));
System.out.println("complement(setB, setA)\t" + complement(setB, setA));
}
}
/*
setA [1, 3, 4, 5, 6, 7, 9]
setB [0, 2, 4, 6, 8, 10, 12]
union(setA, setB) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
intersection(setA, setB) [4, 6]
complement(setA, setB) [1, 3, 5, 7, 9]
complement(setB, setA) [0, 2, 8, 10, 12]
*/- Java Map Interface
- A set of pairs
- Keys must be unique, values may not be unique
- Maps keys to values
- Can map any object to any other object
- Can acquire all keys of a map as a set
- Can test if a key belongs to a map
- Generally use Hashtable, HashMap, TreeMap
- University student maps student id number to name, address, major, gpa, etc
- Customer maps e-mail address to name, address, credit card info, shopping cart, etc
- Inventory item maps part id to description, quantity, manufacturer, cost, price, etc
- Huffman coding maps character to frequency
- Note that it's possible to to have maps where each key maps to another map.
Map<String, Integer> nameToAge = new HashMap<String, Integer>();
nameToAge.put("Anthony", 25);
nameToAge.put("Bob", 30);
nameToAge.put("Alice", 45);
nameToAge.get("Bob); // Returns 30- Hashtables can not be traversed in any meaningful way
- Implemented using Red-Black tree
- Keys are ordered by natural ordering or Comparator
- Provides guaranteed O(log n) times for containsKey, get, put, and remove
- Tree set stores elements in sorted order using natural ordering or comparator
- So we get sorted elements at the price of performance O(1) versus O(log n)