The Map ADT – Answers to Selected Exercises
1. Many answers are possible, for example a. f(x) = x2 b. f(x) = 2x c. f(x) = 2x
4. a. MapInterface<String, Date> students;
b. MapInterface<String, Integercountries;
c. MapInterface<Integer, String> polygons;
5. Keys are allowed to map to null values so just because get returns a null its does not mean the key
is not in use. Instead, the code should use contains(k1).
6.true
0
null
false
5
true
false
dog
null
dog
dig
map dig top ant top
dig
null
map top ant top
8. Bob intends to use the ArrayList built in contains method. This is a nice idea but it will only
work correctly if the key class properly overrides the Object class's equals method, since the
ArrayList class uses .equals.
9.
a)The argument passed by the client class is ignored and 10 is used to initialize the ArrayList. An ArrayList will grow as needed so this is not catastrophic but it could affect performance.
b)If the client class passes a null key to put a map entry using a null key will be created. Since al the other methods will throw an exception when presented with a null key, this map entry can never be discovered or retrieved.
c)That makes no difference since equality is reflexive.
d)This alternate approach works also although it is a little less efficient since it will continue looking at map entries even after it finds a match.
e)Ditto
14. The only two that do not cause at least one collision are 17 and 10,000.
15.
a)5: 56: 205 7: 406 8: 5205 9: 8205 10: 307
b)5: 56: 205 7: 406 8: 307 9: 5205 14: 8250
c)2: 4063: 205 4: 307 5: 5 24: 8205 54: 5205
d)5: 5 205: 205 206: 5205 207: 8205 307: 307 406: 406
e)5: 5 – 205 – 5205 – 8205 6: 406 7: 307
16. 307: a: 4, b: 2, c: 1, d: 1 e: 1
406: a: 2, b: 2, c: 1, d: 1 e: 1
506: a: 6 (counting location 11), b: 5, c: 1, d: 1 e: 2
22.
a)Poor – anyone with the same age hashes to same location
b)Better but not great considering it's possible for many people to have the same last name such as Smith in USA or Nguyen in Vietnam. So if two people have same age and same last name they hash to same location.
c)Better – if same first and last names then hash to same location
d)Best
23 Answers can vary …
a)id % 100,000
b)(id / 1000) % 100,000 (the division "removes" the last three digits)
c)can be tricky .. and depends on length .. maybe use "middle" 24 characters and add multiply together ASCII code of 4th, 8th, 12th, 16th, 20th, and 24th, then % 100,000
d)Since the "prefix" to many file locations might be the same (if they are in the same folder) its best to emphasize the latter part of file location for hash
e)Can most likely just use String class's hashCode
f)Using the last 5 digits should be good enough. Do NOT use first five.
26. a: 0 b. 1 c. 3 d. 19 e. 199
27. Even though buckets remove the need for probing if a hash table becomes too "full" performance will degrade – the average number of elements in a bucket will increase as load increases – so it is still a good idea to monitor load.
28
a)As long as the clients switch the order of their arguments it makes no difference what order the parameters are listed.
b)As long as the hashCode method returns non-negative results everything should be ok, although there is no guarantee of this – we only know that hashCode returns an int. In fact, for example, the hashCode method of the String can and will return negative numbers.
c)Since currCap is never incremented the load factor will be overestimated and the size of the underlying array will grow too large.
d)If client calls put with a null key a null pointer exception will be thrown when k.hashCode is invoked a few lines later.
e)Ditto.
f)That code does successfully remove the element from the underlying array BUT since we use linear probing we may have lost our ability to find elements that were previously added to the map since we may stop looking prematurely when we reach the newly removed location and see the null.
g)There will be an array index out of bounds error when the while loop is executed