Chapter 7: Generics and Collections Flashcards
What are the 4 rules for a valid .equals override?
- Reflexive: For any reference value x, x.equals(x) always returns true.
- Symmetric: For any reference values x and y. If x.equals(y) returns true, so should y.equals(x);
- Consistent: For any refernce values x and y. Multiple invocations of x.equals(y) should return the same value.
- For any non-null reference value x, x.equals(null) should return false.
True or False:
If x.equals(y) returns true, x.hashCode == y.hashCode may return false.
False, if x.equals(y) returns true, then both objects should generate the same hashcode.
Describe the steps for Hashing retrieval (f.e. HashMap).
- Find the right “bucket” using the hasCode() method of the object.
- Compare all the items in the bucket with the object using the equals method.
True or False:
If x.hashCode == y.hashCode is true, x.equals(y) is always true.
False! x.equals(y) may return false. HashCode only describes in which bucket the object should be stored (f.e. HashMap). However if x.equals(y) indeed returns true, then the hashCode methods should return the same value.
What is wrong with the following hashCode override?
public int hashCode() { return 999; }
It’s a valid override because it doesn’t break the contract. However will be very inefficient when used in Hash retrieval collections.
What are the 3 contract rules for the hashCode method?
- Whenever the method is invoked it should always consitently return the same value for a given object.
- Whenever x.equals(y), both x and y should generate the same hashCode.
- It is NOT required to generate unique hashCode values for two objects that are considered equal (using the equals method) but is recommended because of performance improvements.
What happens if you use a transient instance variable in determining the hashCode?
If you serialize and deserialize the object. The object may suddenly produce a different hashCode because the value is lost in the serialization proces. It will get it’s default value.
What are the basic flavors for Collections?
Lists, Sets, Maps and Queues
What are the sub-flavors for Collections?
Sorted, Unsorted, Ordered, Unordered
What is an ordered collection?
It means you can iterate through a collections in a specific not-random order. (f.e. ArrayList uses the index as the order).
What is an sorted collection?
It means the order in the collection is determined by some rule or rules, known as the sort order.
Describe the three List implementations, and whether they are ordered, unorderd, sorted and/or unsorted.
ArrayList, ordered (by index) but unsorted
Vector, ordered (by index) but unsorted (thread-safe, synchronized). Old java version.
LinkedList, ordered (by index) also implements the queue interface. Elements are linked.
Describe the three Set implementations and whether they are ordered, unorderd, sorted and/or unsorted.
HashSet, unsorted and unordered. Uses hashCodes for placing in the collection.
LinkedHashSet, unsorted but ordered. Use this if you care about the iteration order (order of insertion)
TreeSet, sorted. Using natural order (ascending) or custom defined order using Comparable or Comparator.
Describe the four Map implementations and whether they are ordered, unorderd, sorted and/or unsorted.
HashMap, unsorted and unorderd. Uses hashCodes for placing in the collection. Can contain a single NULL key and many NULL values.
Hashtable, unsorted and unorderd. Old java version. Cant’t contain NULL values as key or value.
LinkedHashMap, unsorted but ordered. Keeps insertion order.
TreeMap, sorted. Keeps natural order or custom order using the Comparable ar Comparator interfaces.
Describe the Queue implementations and whether they are ordered, unorderd, sorted and/or unsorted.
LinkedList, ordered (by index) also implements the queue interface. Elements are linked.
PriorityQueue, sorted by natural order or custom order if defined with a Comparable or Comparator implementation.
What will the compareTo() method return for a valid implenetation of the Comparable interface?
negative -> thisObject < anotherObject
zero -> thisObject == anotherObject
psoitive -> thisObject > anotherObject
What is the difference between the Comparable interface and the Comparator interface?
- Comparable should be implemented by the class you want to sort. Comparator can be any class and can sort any type of object (even final classes because you don’t neet to modify the to be sorted class).
- Comparable uses the method compareTo(objTwo). Comparator uses the method compare(objOne, objTwo).
- Comparable can only define one sort order for an Object. You can create many variants of the Comparator implementation for the same object.
What are the util methods for sorting lists and arrays?
Collections.sort(listToSort)
Collections.sort(listToSort, Comparator)
Arrays.sort(arrayToSort)
Arrays.sort(arrayToSort, Comparator)
What will be the result?
String [] sa = {"1", "2", "3"}
Arrays.sort(sa);
Arrays.binarySearch(sa, "1"); // 1
Arrays.binarySearch(sa, "4"); // 2
List list = Arrays.asList(sa);
ReverseComparator rs = new ReverseComparator()
Collections.sort(list, rs);
Collections.binarySearch(list, “3”, rs); // 3
- 0
- -4 (inertion point is actually 3, but it is returned as a negative number. Because value 0 is still a found match.)
- 0
What is the result? TreeSet times = new TreeSet(); times.add(1205); times.add(1505); times.add(1545); times.add(1830); times.add(2010); times.add(2100);
times. lower(1505); // 1
times. floor(1505); //2
times. higher(1830); //3
times. ceiling(2010); //4
- 1205
- 1505
- 2010
- 2010
// lower: returns the first element that is lower then the given key. // floor: return the first element that is equal or lower then the given key. // higher: returns the first element that is higher then the given key. // ceiling: return the first element that is higher or equal to the given key.
Describe the methods for retrieving (and removing) an item from a TreeSet and TreeMap.
TreeSet.pollFirst();
TreeSet.pollLast();
TreeMap.pollFirstEntry();
TreeMap.pollLastEntry();
TreeSet has lower, floor, etc. methods, what are the equivalents for a TreeMap?
TreeMap.lowerKey(key); the first lower key
TreeMap.floorKey(key); the first lower or equal key
TreeMap.higherKey(key); the first higher key
TreeMap.ceilingKey(Key); the first higher or equal key
What are the items contained in map and submap?
TreeMap map = new TreeMap<>();
map. put(“a”, “ant”);
map. put(“d”, “dog”);
map. put(“h”, “horse”);
SortedMap submap = map.subMap(“b”, “g”);
map. put(“b”, “bat”);
submap. put(“f”, “fish”);
map. put(“r”, “raccoon”);
Map: a=ant b=bat d=dog f=fish h=horse r=raccoon
SubMap
b=bat
d=dog
f=fish
Submap is a backed collection. Anything that is added to the original map that is also in the range defined for the submap (b-g) it is automatically added to the submap. When something is added into the submap it is also added to the original map but only if it’s inside the given range (b-g). If an item is added that is outside the range, (submap.put(“p”, “pig”)) an exception is thrown.
What are the three important PriorityQueue methods?
peek(); // returns the highest priority item without removing it.
poll(); // returns the highest priority item and removes it from the queue.
offer(); // Add element to the queue.
What determines the priority in a PriorityQueue?
1. Natural order PriorityQueue queue = new PriorityQueue();
2. Custom order using comparator PriorityQueue queue = new PriorityQueue(10, myComparator);
What is the order of the queue given the following code?
String[] sa = { “ff”, “ f”, “f “, “FF” }
PriorityQueue queue = new PriorityQueue();
for(String s : sa)
queue.offer(s);
Natural order, because no comparator is given.
” f” => “FF” => “f “ => “ff”
Spaces sort for characters and uppercase letters sort before lowercase letters.
What is the result of compiling and running the following code?
public class Generics {
public static void main(String[] args) {
List strings = new ArrayList();
strings.add("test");
Generics.addThings(strings);
for(String string : strings) {
System.out.println(string);
}
}
public static void addThings(List list) {
list.add(new Integer(1));
}
}
Compiles fine (generics are a compile time protection). Will give an ClassCastException because an Integer cannot be cast to a String.
What is the result of the following? List animals = new ArrayList(); // 1 Animal[] animals2 = new Dog[3]; // 2
- Compiler error.
The type of the declaration and the initialization must be exactly the same. - Compiles fine.
What is the result of the following?
public class Generics {
public static class Animal {}
public static class Dog extends Animal {}
public static class Cat extends Animal {}
public static void main(String[] args) {
Dog[] dogs = { new Dog(), new Dog() };
addThings(dogs);
}
public static void addThings(Animal[] animals) {
animals[1] = new Cat();
}
}
ArrayStoreException (RuntimeException)
Can’t put a Cat into a Dog array.
What is the result of the following?
public void addAnimal(List extends Animal> animals) {
animals.add(new Dog());
}Compiler error.
You can’t add to the list if your using the ? notation.
Will the following compile?
void foo(List < ? implements Serializable> list) {}
No
When using the ? notation you use extends for both super classes and interfaces. F.e.
? extends Serializable
Which of these will compile?
- List> list = new ArrayList();
- List extends Animal> list = new ArrayList();
- List> list = new ArrayList extends Animal>();
- List extends Dog> list = new ArrayList();
- List super Dog> list = new ArrayList();
- List super Animal> list = new ArrayList();
1,2,5
- You cant use a wildcard in the object creation.
- You cant assing an integer list to an variable that takes a Dog list or a subtype of Dog).
- You cant assign a Dog list to a Animal list (or a super type of animal). Dog is to low in the hierachy.
Describe a method that takes a generic argument with no return type.
public void makeMyArrayList(T t);
this.makeMyArrayList(new Dog());
What is wrong?
class X { public X(X x) { } }Nothing.
A class X with a constructor with a genericy typed argument named X.
Given a TreeSet with the following contents:
a, aa, b, bb, c, cc
Complete the following code to get the output:
a, b, null, c
treeSet.(“a”);
treeSet.(“aaa”);
treeSet.(“a”);
treeSet.(“bb”);
floor -> equals or lower
ceiling -> equals or higher
lower -> lower then the given element
higher -> higher then the given element
Treeset is sorted frow lowest value to highest value a > cc
True or False:
A HashSet can contain null values.
True
Your application needs to load a set of key value pairs from a database table which never changes. Multiple threads need to access this information but none of them changes it. Which class would be the most appropriate to store such data?
HashTable HashMap Set TreeMap List
HashMap
HashTable is synchronized and not needed for this situation because it will impact performance
