Java’s Map Interface¶
Although our map implementations will include essentially all the functionality of Java’s Map
interface, you will only need to implement a few of its methods—all the others will have default implementations that use the methods you implement.
Signature | Description |
---|---|
V get(Object key) | Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. |
V put(K key, V value) | Associates the specified value with the specified key in this map. |
V remove(Object key) | Removes the mapping for a key from this map if it is present. |
void clear() | Removes all of the mappings from this map. |
boolean containsKey(Object key) | Returns true if this map contains a mapping for the specified key. |
int size() | Returns the number of key-value mappings in this map. |
Iterator<Entry<K, V| iterator() | Returns an iterator that, when used, will yield all key-value mappings contained within this map. |
Note
The get
, remove
, and containsKey
methods accept any Object
parameters, rather than restricting the key type to K
. This should not cause any issues in your map implementations.
Iterator¶
An iterator is a type of object that lets a client efficiently iterate over a data structure using a forEach
loop. Whenever we write code like:
for (String item : something) {
// ...etc...
}
Java will internally convert that code into the following:
Iterator<String> iter = something.iterator();
while (iter.hasNext()) {
String item = iter.next();
// ...etc...
}
When you call iter.next
for the first time, the iterator will return the first item. If you call it again, it’ll return the second item.
If the user calls iter.next
after the iterator has gone through all items, the method will throw a NoSuchElementException
. iter.hasNext
helps avoid this by returning true if calling iter.next
will safely return a value, and false otherwise.
Notes and Requirements¶
- You may NOT create any new temporary data structures inside of your iterators.
- Your iterator methods must run in constant time with respect to the size of the data structure.
- Your iterators may return entries in any order although the easiest approach is to return them in the same order as your map’s internal representation.
-
You may assume that the user will not modify your maps while your iterators are in use.
For example, the following will never happen:
Iterator<Entry<String, Integer| itr = map.iterator(); itr.next(); // the following line should never happen if the same // iterator instance is used later map.put("hi", "373"); itr.next();
ArrayMap
¶
Task
Implement the basic ArrayMap
, as described in lecture.
Your ArrayMap
class will internally keep track of its key-value pairs by using an array of Map.Entry<K, V>
objects. For example, after running the following code:
Map<String, Integer> map = new ArrayMap<>();
map.put("a", 11);
map.put("b", 22);
map.put("c", 33);
Your map’s internal array should look like this:
And if we add a few more entries:
map.put("d", 44);
map.remove("b");
map.put("a", 55);
Your internal array should now look like the image below.
There are a few important things to notice:
- We’ve updated the old entry for “a” to store the new value.
- We’ve replaced the entry for “b” with the one for “d”. Maps are inherently unordered so when removing an entry, we can simply replace it with the last entry in the array. For example, this is what the call to
map.remove("b")
would do in the example above:
Your implementation should include the following constructors:
Signature | Description |
---|---|
ArrayMap() | Constructs a new ArrayMap with default initial capacity. |
ArrayMap(int initialCapacity) | Constructs a new ArrayMap with the given initial capacity. |
Requirements¶
- All methods must run in time, where is the size of the map.
size
anditerator
must run in time.- The
iterator
must adhere to all the requirements listed in the Iterator section.
Notes¶
- You are NOT required to downsize your array if the user removes many elements.
- Your internal array should store elements of type
SimpleEntry<K, V>
, (take a look atSimpleEntry
for more details—press control or command and click on anySimpleEntry
type in IntelliJ)SimpleEntry<K, V>
implementsEntry<K, V>
, so you can simply return your map’sSimpleEntry
objects when implementingIterator.next
.
-
The test files use AssertJ’s
Map
assertions. Here’s a summary of how each assertion method calls the methods you implement:Methods called by AssertJ assertions
AssertJ Map
assertionMap
methodhasSize
/hasSizeGreaterThan
size
containsKey
/doesNotContainKey
containsKey
containsEntry
get
(andcontainsKey
if value is null)containsAllEntriesOf
get
(andcontainsKey
if value is null)containsExactly
iterator
containsExactlyInAnyOrderEntriesOf
iterator
AssertJ Iterator
assertionIterator
methodhasNext
/isExhausted
hasNext
Tips¶
- If the array is full and a new key is inserted, create a new array and copy over the old elements.
- If you need to check object equality but can’t guarantee that either object is non-null, use
java.util.Objects.equals
—it does all the necessary null checks for you. - By default, IntelliJ’s debugger may attempt to show the entries of your map instead of its fields. To disable this feature, open the project settings and navigate to Build, Execution, Deployment | Debugger | Data Views | Java, then deselect Enable alternative view for Collection classes.
ChainedHashMap
¶
Task
Implement ChainedHashMap
, a map with a hash-table using separate chaining to resolve collisions.
Warning
Correctly implementing your iterator will be tricky. We recommend starting early on it.
When we covered separate chaining in lecture, we used a list as the chaining data structure. In this assignment, instead of a list, you will use your ArrayMap
.
When you first create your array of chains, it will contain only null references. As entries are inserted into the table, you need to create the chains (ArrayMap
s) as required. Let’s say you created a chain array of size 5 (you can choose any initial size), and you inserted the key “a” with the value 11.
Map<String, Integer> map = new ChainedHashMap<>();
map.put("a", 11);
In this example, the key “a” lands in index 2, but the index could change depending on your table size. Also, in this example, the ArrayMap
(chain) has size 3, but you can choose a different initial size for your ArrayMap
.
Now suppose you insert a few more keys:
map.put("f", 13);
map.put("c", 12);
Your internal hash table should now look like the figure below. In this example, keys “a” and “f” both hash to the same index (2).
Your implementation should include the following constructors:
Signature | Description |
---|---|
ChainedHashMap() | Constructs a new ChainedHashMap with default parameters. |
ChainedHashMap(double resizingLoadFactorThreshold, int initialChainCount, int chainInitialCapacity) | Constructs a new ChainedHashMap with the given parameters. |
ChainedHashMap Iterator¶
Info
Watch this video by a former TA that provides an overview of the iterator as used in another Map
implementation.
Info
The following implementation guide is provided only as a suggestion. It is okay if your own implementation diverges from it.
The iterator for ChainedHashMap
should work as follows.
hasNext():
- Determines if there is a next item in the
HashMap
by using the current position (if the current index is not at the end of theHashMap
)
next():
- Check if there is a next item in the
HashMap
. - If there is a next item, determines if the item is a chain (
ArrayMap
) or a specific value (Entry(k, v)
) within the current chain. - If the next item is a specific value, return it with an
iterator
. - If the next item is a chain, follow one of the three scenarios:
- If the chain is empty, move to the next chain.
- If the chain is not empty, iterate through the current chain.
- Otherwise, there are no more chains to iterate through.
Requirements¶
- All methods should run in time in practice (except when resizing, in which case
put
may run in time, where is the size of the data structure). - The
iterator
must adhere to all the requirements listed in the Iterator section.
Notes¶
- The 0-argument constructor requires you to determine and define some reasonable defaults in the final fields at the top of the class.
- The second constructor has some parameters to configure the behavior of the map:
resizingLoadFactorThreshold
: when the load factor exceeds this value, the array of chains resizes.initialChainCount
: the initial number of chains for your hash tablechainInitialCapacity
: the initial capacity of eachArrayMap
chain created by the map
- If your
ChainedHashMap
receives a null key, use a hashcode of 0 for that key. - Do not try to implement your own hash function. Use Java’s
Object.hashCode()
method instead—e.g.,int hashCode = key.hashCode()
. - Use the provided
createChain
method to instantiate yourArrayMap
, rather than calling theArrayMap
constructor.
Tips¶
- We recommend doubling the number of chains when resizing.
- You are NOT required to downsize your hash table if the user removes many elements.
- You should call the
iterator
method on eachArrayMap
inside your chains array. - You may add as many extra fields as you need to track your iterator’s state.
- Before you write any iterator code:
- Try designing an algorithm using pencil and paper, and run through a few examples by hand i.e. draw the chains array that has some varying number of
ArrayMap
objects scattered throughout, and simulate what your algorithm does. - Think about the invariants of your
ChainedHashMap
.
- Try designing an algorithm using pencil and paper, and run through a few examples by hand i.e. draw the chains array that has some varying number of
Good use of invariants can greatly reduce your code complexity by reducing the number of cases you need to consider. For example, as you (hopefully) found in the previous assignment, ensuring that a certain field is never null allows you to omit null checks.
Much of the complexity in your code execution will arise from handling edge cases—the empties and nulls and such. Think about what invariants you should uphold in both your main ChainedHashMap
code and in your iterator. Obviously, this might involve tweaking the way your ChainedHashMap
stores data, but it’s certainly worthwhile if you can reduce the overall complexity of your code.
For example, here are a couple invariants that you might include:
- Each index in the array of chains is null if and only if that chain has no entries.
- The
currentChain
field of the iterator always references the current chain being iterated through (the chain which contains the next entry thatnext
will return). - The
currentChain
field is null after the iterator has been exhausted of all entries.
Tip
Make sure to write down your invariants (perhaps in a comment somewhere in the class?) so that you don’t forget them, and make sure that you actually uphold your invariants before and after every method. Having them explicitly written out will also help in case you decide to change your invariants while implementing your code—a very real possibility, since it may not be entirely clear what invariants provide useful restrictions on your data structure’s state.
Submission¶
If you’re working in a group, the partner who submits must add the other partner as a group member on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.
Warning
Submitting the same code as another student without using Gradescope’s group feature is considered plagiarism, and may have consequences.