|
Java SE 8 Documentation
Exercises
equals() and hashCode()
As we have previously learned, in Java, every type is derived from java.lang.Object if there is no direct base class. In other cases (that is, there is a base class), java.lang.Object is still going to be a base class, due to the transitivity of the inheritance relation, however indirectly. That is important because it has some methods that are worth to be implemented almost every time: those are equals(), hashCode(), and toString(). For what it is worth, the latter one has been already featured earlier, but the others ones were not really discussed further.
The equals() method implements how to determine if two objects are equal to each other, it defines an equivalence relation. That is why the following expectations have to be fulfilled by this operation (just like in mathematics): let it be
- reflexive,
- symmetric,
- transitive,
- and always false for
null values.
Note that another java.lang.Object is passed as a parameter for this method. In result, it cannot be taken for sure that its type will match with that of the actual object, so it has to be verified first in order to the actual comparison (see later in the code example below).
public boolean equals(Object o);
The hashCode() method can be used for generating a so-called "hash code" for the object, which is a 32-bit integer. This code is exploited in the implementation of certain data structures, such as sets or hash tables (see later). That is why it is expected from this method that:
it shall always return the same value for the same object. if two objects are considered the same by equals() then the result of hashCode() must be also the same for both of them. hash code for two different objects may match — although this will lead to a so-called hash code collision that may have certain consequences.
Now let us see an example for putting everything together:
class Point3D {
private double x;
private double y;
private double z;
public Point3D(double x, double y, double z) {
this.x = x;
this.y = y;
this.z = z;
}
@Override
public boolean equals(Object obj) {
if (obj != null && obj instanceof Point) {
Point other = (Point) obj;
return (other.x == this.x && other.y == this.y &&
other.z == this.z);
}
return false;
}
@Override
public int hashCode() {
return new Double(2 * x + 3 * y + 4 * z).hashCode();
}
@Override
public String toString() {
return String.format("Point3D { x = %.3f, y = %.3f, z = %.3f }",
x, y, z);
}
}
Note the @Override in the code snippet above. That is called an annotation. There are many annotations in Java, but we will only use this for the moment. The purpose of the @Override annotation is help the compiler with checking if the given method was overridden properly (that is what "override" here actually means). That is, the compiler now can tell if the overriden method still has the same name, return value, and list of parameters as it has been originally defined in the base. That is considered a valid overriding, since that is when one of the operations from the base class was indeed redefined.
But because such methods could be quite easy to miss, it may happen that only a method similar to that of in the base is created accidentally, so that will not work properly. That is why it was explicitly confirmed. Annotations are not mandatory, but they are highly recommended.
Generic (or Parametric Polymorphic) Classes
In the Java language, inheritance is not the only way to implement reusable classes in the programs. There are also generic class definitions where a template is created. In this template, there is not a concrete type but a parameter is used through the definition of the class. Then that is replaced with some type once it is specified, and gives defines a concrete class.
In order to illustrate this, let us now consider Store<T>, an improved version of the previously implemeneted IntList class, where it is parametrized over the type of the elements to store.
class Store<T> {
private Object[] store;
public Store(int size) {
store = new Object[size];
}
public void add(T x) {
store = Arrays.copyOf(store, store.length + 1);
store[store.length - 1] = x;
}
public void add(int i, T x) {
if (i >= size()) return;
add(x);
for (int j = size() - 1; j > i; j--) {
set(j, get(j - 1));
}
set(i, x);
}
public void concat(Store<T> list) {
for (Object x : list.store) {
add((T) x);
}
}
public T get(int i) {
return ((T) store[i]);
}
public void set(int i, T x) {
store[i] = x;
}
public void remove(int i) {
if (i < 0 || i >= size()) return;
for (int j = i; j < size() - 1; ++j) {
set(j, get(j + 1));
}
store = Arrays.copyOf(store, store.length - 1);
}
public int indexOf(T x) {
for (int i = 0; i < size(); ++i) {
if (get(i).equals(x))
return i;
}
return (-1);
}
public int size() {
return store.length;
}
public void clear() {
store = new Object[0];
}
public T[] toArray(T[] dummy) {
return (T[]) Arrays.copyOfRange(store, 0, store.length);
}
public String toString() {
return "Store<T> " + Arrays.toString(store);
}
}
Note that that is going to be completely generic definition, because the objects inside are stored in an array that contains elements of type java.lang.Object. But since that class is a base for every other in the language, this will not cause any problems. This implementation detail will not be visible from the outside of the class, and it is also enforced through the public methods that only elements of the value of the type parameter may be handled.
Obviously, if there was not any restriction on the type, any elements in the array could be stored so they could be mixed in arbitrary fashion, such as the following:
Object[] array = new Object[] { 1, 'a', "hello", new Object() };
Note that this can now explain why the toArray() method above has an extra, seemingly unused parameter: in order to return an array of the appropriate type, some run-time information is needed. The T parameter will go away once the code is compiled, so that remains the only the way to regain this information in run time. (For what it is worth, it is not actually verified if the type of passed array will match.)
Generic Data Structures, Java Collections
Generic data structures are of a great importance in the Java language. They are introduced as part of the "Java Collections" framework, the deep knowledge and efficient use of that is technically essential for developing simpler and easier-to-maintain programs. All the methods that could be used for every Java collection are defined as part of the java.util.Collections class.
Lists
A kind of collections is the lists. Lists logically implement the classical linked list data structure but in many different ways. The two most popular variation on that is the java.util.LinkedList and the java.util.ArrayList. java.util.LinkedList is the one that was actually implemented as a (double, that is back and forth) linked list, while java.util.ArrayList is the one that implements the interface as a dynamically growing array.
Deques
Deques are like lists, they also store elements in a linear fashion, and they support access, insertion, and removal from the beginning and the end. That is why the name "deque" itself refers to a "double-ended queue". Deques can be used for implementing the classical queue (which is FIFO, First-In-First-Out), and stack (which is LIFO, Last-In-First-Out) data structures, because they are actually specializations of a deque. Deque is implemented by java.util.ArrayDeque and java.util.LinkedList.
Sets
A potential area of use of the previously presented equals() and hashCode() methods is the set, that is the java.util.Set container type. Sets contain elements only once (similarly to mathematical sets) and they are not sorted, because the order of elements does not matter. Therefore equivalence of sets could be determined by deciding if they have the same elements. This is implemented by the java.util.HashSet (more efficient) and java.util.TreeSet (sorted) classes.
Hashtables (Finite Maps)
The java.util.HashMap class is a data structure that is based on the use of hash codes that it makes possible to store pairs of keys and associated values. An advantage of the application of java.util.HashMap is that any element in the container can be accessed with the same cost if its key is known. (In other cases, all the container has to be traversed to find the element, so it is recommended to sort the contents, see below.)
Operations:
HashMap<Integer, String> map = new HashMap<Integer, String>();
map.put(21, "Twenty One");
map.put(21.0, "Twenty One"); // build error: 21.0 is not an Integer
Integer key = 21;
String value = map.get(key);
System.out.println("Key: " + key + " value: " + value);
map.put(21, "Twenty One");
map.put(31, "Thirty One");
Iterator<Integer> keySetIterator = map.keySet().iterator();
while (keySetIterator.hasNext()) {
Integer key = keySetIterator.next();
System.out.println("key: " + key + " value: " + map.get(key));
}
// or more simply, with the help of the "for each" construct:
for (Integer key : map.keySet()) {
System.out.println("key: " + key + " value: " + map.get(key));
}
- Get size and remove element:
System.out.println("Size of Map: " + map.size());
map.clear(); // empties the whole container, removes all the elements
System.out.println("Size of Map: " + map.size());
- Determine if a key or value is present:
System.out.println("Does HashMap contain 21 as key: " + map.containsKey(21));
System.out.println("Does HashMap contain 21 as value: " + map.containsValue(21));
System.out.println("Does HashMap contain Twenty One as value: " + map.containsValue("Twenty One"));
boolean isEmpty = map.isEmpty();
System.out.println("Is HashMap empty: " + isEmpty);
Integer key = 21;
Object value = map.remove(key);
System.out.println("The following value has been removed from Map: " + value);
Sort: java.util.HashMap objects are not sorted, neither by key, nor by value. If it is important for us to store the elements in some order, it is better to convert it to some java.util.SortedMap type, such as java.util.TreeMap. This class has a constructor that takes a java.util.HashMap argument and sorts all the contained elements by their default ordering or by the specified java.util.Comparator.
That is needed because Collections.sort() cannot be applied to Map objects.
map.put(21, "Twenty One");
map.put(31, "Thirty One");
map.put(41, "Thirty One");
System.out.println("Unsorted HashMap: " + map);
TreeMap sortedHashMap = new TreeMap(map);
System.out.println("Sorted HashMap: " + sortedHashMap);
Exercises
Implement a class that represents a time of day with the name Time and override the equals() and hashCode() methods for it. Write a program that counts how many different characters appear in the text received from the standard input. There is no need to distinguish between lower- and uppercase letter, and ignore all the other types of characters. Write a program that reads a dictionary from a file, where each of the lines form an entry in the format word -> word. With the help of this dictionary, read some text from the standard input and translate all the words in the dictionary that appears in the text to their pairs. Write a program that reads time of day information from a file into objects of type Time, for example in the following format: <hour> <minute> <second> and prints them to the standard output, but only once. Write a program that counts the occurences of words in a text file. There is no need to distinguish lower- and uppercase characters. The name of the file shall be received from the command line. Implement a simple hash table in the SimpleMap class that supports all the operations on hash tables.
Links
Related sources
Front page
Back
|