get(Key k): Returns the value to which this map maps the specified key.
put(Key k, Value v): Associates the specified value with the specified key in this map (optional operation).
remove(Key k): Removes the mapping for this key from this map if it is present (optional operation).
size(): Returns the number of key-value mappings in this map.
isEmpty(): Returns true if this map contains no key-value mappings.
keysSet(): Returns a set view of the keys contained in this map.
values(): Returns a collection view of the values contained in this map.
clear(): Removes all mappings from this map (optional operation).
containsKey(Key k): Returns true if this map contains a mapping for the specified key.
containsValue(Value v): Returns true if this map maps one or more keys to the specified value.
entrySet(): Returns a set view of the mappings contained in this map.
putAll(Map m): Copies all of the mappings from the specified map to this map (optional operation).
The SortedMap interface provides additional methods that permits access to subsets of the current map, defined by intervals in the key-space.
Additional functions:
comparator(): Returns the comparator associated with this sorted map, or null if it uses its keys' natural ordering.firstKey(): Returns the first (lowest) key currently in this sorted map.headMap(Key toKey): Returns a view of the portion of this sorted map whose keys are strictly less than toKey.lastKey(): Returns the last (highest) key currently in this sorted map.subMap(Key fromKey, Key toKey): Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to toKey, exclusive.tailMap(Key fromKey): Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey.keySet() and values() return ordered sets of the keys and values as opposed to random ordering (As in HashMap).
get(Key k): O(log n).
put(Key k, Value v): O(log n).
remove(Key k): O(log n).
size(): O(1).
isEmpty(): O(1).
keysSet(): O(n).
values(): O(n).
containsKey(Key k): O(log n).
containsValue(Value v): O(n).
mod N with N the capacity of the table. This implementation doubles the size of the array whenever the load factor reaches a given threshold (Default 0.75).
get(Key k): O(d).
put(Key k, Value v): O(d).remove(Key k): O(d).
size(): O(1).
isEmpty(): O(1).
keysSet(): O(N).
values(): O(N).
containsKey(Key k): O(d).
containsValue(Value v): O(N).
Where d = max number of collisions and N = capacity of hash table.
A LinkedHashMap is the same as a regular HashMap with the addition of a doubly-linked list between all the entires. This doubly-linked list orders the entries in the hash table by insertion or access order. These can be maintained in constant time so add little overhead to the HashMap implementation.
Insertion order: Signifies that the collections returned by the keySet() and values() method iterates over elements in the same order as they were inserted into the map. Note that insertion order is not affected by an update (i.e. calling put() on an existing key).
Access order: Signifies that the collections returned by keySet() and values() method iterates over elements in the order they were accessed from least recent to most recent. An access is defined by either a call to get() or a call to put().
Note that the use of a doubly linked list to connect all entries changes the running time of the following methods:
keysSet(): O(n).
values(): O(n).
containsValue(Value v): O(n).
A Set is a simplified Map. Recall that a Map is a collection of key, value pairs. A Set on the other hand is a collection of keys only. Like a Map, the keys in a Set are unique and cannot be repeated. The two interfaces are very similar, so much so that the primary Java implementations of the Set and SortedSet interfaces, HashSet and TreeSet, are actually adapters of HashMap and TreeMap!
We'll use SortedSet (or SortedMap) to calculate some basic statistics from a list of Grade objects. Implement the following methods in class called GradeStats:
GradeStats(List<Grade> grades): Create a new GradeStats object with the given list.averageGrade(): Calculates the average grade.maxGrade(): Returns the highest grade.medianGrade(): Returns the median grade.minGrade(): Returns the smallest grade.List<Integer> passingStudents(int passingGrade): Returns a list of student IDs of those students who have a grade greater than or equal to passingGrade.What are the expected running time of the above query methods?
The file GradeStats.java is a stub file you can use. Also included is GradeGen which can generate random lists for you to test your code on.