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 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!
In this lab we will work on problem 1 of Homework 5, implementing a WebpageIndexEntryI. At the end of the lab make sure to submit WebpageIndexEntry.java, your implementation does not need to be finished when you turn it in. If you have already finished this problem feel free to use the lab time to keep working on Homework 5.
Begin by creating WebpageIndexEntry.java, the class that implements WebpageIndexEntryI. Make sure to include a default constructor.
Internally, a WebpageIndexEntryI keeps a String with the address of the webpage, a Set of links the page links to and a List of keywords. Create fields in your class for these, initialize them in the constructor and implement the following methods (i.e. all but getFrequencyMap()):
void setAddress(String url)void addLinks(Set< String > links)void addKeyword(String keyword)String getAddress()Set< String > getLinks()The method getFrequencyMap() converts the List of keywords to a Map where the keys are the number of times a word appears in the keyword list and for each key K, the value is the set of words that appear K number of times in the list of keywords.
| if the list of keywords is | The map will be | |||||||||||||||||
|
|
There are many ways to achieve this, one way involves using a temporary map from keywords to the frequency of the keywords. In our example the map would be:
| Key | Value |
|---|---|
| Cat | 3 |
| Dog | 2 |
| Fish | 2 |
| Bird | 1 |
Once this temporary map is created we can scan each key in the map and insert the keyword into the right place on the final map.
Implement getFrequencyMap(). You may use the temporary map implementation described here or any other implementation you would like. When choosing which Map to instantiate keep in mind the running time of each operation and how you intend to use the Map.
When you hand in your homework make sure to justify why you chose the type of Maps that you did.