Chaining Hash Map

You’ll be using hash maps to create the text generator. In implement
ChainingHashMap, which is a subclass of the AbstractHashMap class. This hash map should
use chaining, rather than re-hashing, to resolve collisions. In particular, rather than maintaining an array
of Entries, it should have an array of ArrayLists of entries. Each position of the array should
either contain null (if no keys have hashed to this position) or contain an ArrayList of Entries
whose keys map to this position.
Important note: Java will not allow you to have a variable ArrayList<Entry>[] entries; it’s
just a limitation of the language. You can, however, have a variable of type ArrayList[] entries.
Note that in this case entries[i].get(j) is of type Object. Doing this will cause the
“unchecked or unsafe operations” warning, but that’s okay; you know what you’re doing. You know
that the lists are filled with Entry objects. If you want to treat the result as an Entry, you need to
typecast like this: Entry e = (Entry)entries[i].get(j). If you forget to do this you will
get incompatible type errors.

Implement the following methods.
Constructor – Calls the superclass’ constructor, setting the maximum load to 5 and initializes the
array to the given capacity.
put(key, value) – If key is already in the map, replaces its associated value with the given
value. Otherwise it adds an entry with key and value to the table.
printEntries() – (Will not be graded, but would sure be useful for testing and debugging!)
Stop and test. You should now be able to thoroughly test put. Make sure it works before moving on!
You can write empty stubs for the other methods so it will compile.
resize() – Create a larger array (twice as big!) and rehash everything. (Also make put call
resize if the load reaches the maximum).
Stop and test. Make sure resizing works the way it should!
get(key) – If key is in the map, it should return the associated value. Otherwise, return null.
Stop and test. Test your ChainingHashMap thoroughly before moving on. Make sure you can store
and search for items that have the same hash value. Add items to your map and print it out, to make
sure it looks like what you would expect.
Now, in implement the ChainingHashMapIterator class, which
should be a subclass of AbstractHashMapIterator. In many ways it will be similar to your
ProbingHashMapIterator, but you must now take the chains into account as well.
Implement the iterator method in ChainingHashMap and test your iterator thoroughly.


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:dmxyzl003 工作时间:全年无休-早上8点到凌晨3点