[Problem Description]

A map is a data structure for storing and accessing a collection of object pairs, which are commonly referred to as <key, value> pairs. For example, a dictionary can be stored in a map, where the keys are the words and the values are the meanings of the words, e.g. <"River", "A stream of water.">.  For this assignment, you are going to implement a generic HashMap<K,V> class, which uses a hash table to manage the <key, value> pairs. In particular, HashMap<K,V> provides at least the following methods:

• (15pt) HashMap<K,V>() - Constructor, where K is the type for the keys and V is the type for the values. The default size of the hash table is 17.
• (20pt) void insert(K key, V value) - inserts a <key, value> pair into the map. If the key is already in the map, replaces the old value with the inserted value, i.e. there should not be duplicate keys in the map.
• (20pt) V remove(K key) - removes a <key, value> pair from the map, and returns the removed value, or null if the key is not in the map.
• (10pt) V get(K key) - retrieves the value associated with the given key, or null if the key is not in the map.
• (5pt) boolean contains(K key) - checks whether the key is in the map.
• (5pt) int size() - returns the number of <key, value> pairs stored in the map.
• (5pt) void clear() - removes all <key, value> pairs from the map.
• (20pt) void resize() - doubles (roughly) the size of the hash table. Since we want to keep the size of hash table a prime number, if the current size of the table is s, then after resize(), the size should be increased to the smallest prime number that is larger than 2*s.

[About Hashing]

For hash function, you may use key.hashCode()%ht.size, where key.hashCode() is the hashCode() of the key object, and ht.size is the size of the hash table.

For collision resolution, you must use quadratic probing. Note that in order for quadratic probing to work properly, you must call resize() whenever the hash table is half full. Also note that when you create a new array for the enlarged hash table, you cannot simply copy over the elements from the old array, because the hash index of a <key, value> pair may have changed; so instead, you should do a re-hashing, which basically takes the data from the old hash table and re-insert them into the new hash table.