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.