Skip to content

Latest commit

 

History

History
58 lines (41 loc) · 2.38 KB

ex06.md

File metadata and controls

58 lines (41 loc) · 2.38 KB

Exercise 06

Part A

Consider the classes in the package org.pg4200.ex06. Both Author and Book are mutable classes. You need to implement immutable versions. In particular, write a class ImmutableAuthorImp that implements ImmutableAuthor, and ImmutableBookImp that implements ImmutableBook.

Write a test class called ImmutableBookAndAuthorTest that extends
ImmutableBookAndAuthorTestTemplate. If your implementations of ImmutableAuthorImp and ImmutableBookImp are correct, then all tests should pass.

Note: you will likely need to use Collections.unmodifiableList() to create an immutable list.

Part B

Implement a class called HashMapLinearProbe that implements MyHashMap. Here, the data is stored in the following data structure, ie a single array:

private Entry[] data = (Entry[]) Array.newInstance(Entry.class, M);

When a new entry (ie a pair key/value) is added to the map, the position in the data array will be based on the hash value of the key (same way as in MyHashMapWithLists). However, the handling of conflicts (ie two different keys ending up in the same position) is done differently. If a position i is already occupied, look at i+1, and so on, until you find a free space. If you reach the end of the array, start back from the beginning (ie position i==0).

Note: put and get should be relatively easy. On the other hand, delete is quite tricky. Consider the case of [..., a, b, c, ...], where hash(a) and hash(b) are the same and you need to delete b. You cannot simply delete b from the array, because it might well be that hash(c)==hash(a), and create a hole in the array would make c not reachable any more. In those cases, the Entry object for b should still be kept, but just marked as "deleted" (eg, by setting the key to null), which would be treated differently from the entry just being null.

Write a test class called HashMapLinearProbeTest that extends MyHashMapTestTemplate. If your implementation is correct, all tests should pass.

Part C

Study the source code of MyHashMapWithLists. Once you think you fully understand it, write its implementation on paper (e.g., using a pen), without looking at the source code. Once done, compare what you wrote with the actual implementation.

Solutions

Solutions to this exercise can be found in the solutions module, under the org.pg4200.sol06 package.