Provided are two Java classes, one of which (SetOfStrings) needs some work.
The underlying representation of the set is as a hash table (i.e., an array) that uses open addressing (meaning that all the (references to) strings are stored within the confines of the table) and employs the linear probing collision resolution strategy.
Each element of the array (which is named table[]) either stores the null value or contains (a reference to) a String object (that is a member of the represented set).
You are strongly encouraged to examine this class carefully. Especially take note of the findLoc() method and two of the methods that it utilizes, nextLocation() and homeAddressOf().
The two methods in SetOfStrings that are unfinished are insert() and remove(). The former should be relatively easy. The latter is much trickier, because when an element of table[] becomes null (due to the string formerly occupying it being removed from the set), it could possibly result in the class invariant becoming false. Which means that measures must be taken to re-establish the truth of that invariant. (The SetOfStrings class invariant is stated immediately after the declaration of its instance variables.)
Of great help in re-establishing the class invariant can be the belongsAt() method. Applied to a location k, it will tell you to which location in table[] the string in location k should be transferred. (If it returns k, that means that the string is in its proper place.)
Of course, to gain confidence that your solutions are correct, you should do extensive testing, which is the purpose of the SetOfStrApp application program.
Here is a sample interaction with the SetOfStrApp program. The version of SetOfStrings that was being tested is flawed, as can be seen by what happened when "kirk" was removed. The parenthesized number following each string is its home address.
Welcome to the Set Of Strings Application. Enter desired set capacity: 8 > h q (quit) h (print this help menu) p (print the whole set) t (print the table) n (report the # of members) i glorp (insert "glorp") r glorp (remove "glorp") m glorp (report whether "glorp" is a member) > i kirk 0: 1: 2: 3: 4: 5: "kirk" (5) 6: 7: > i spock 0: 1: 2: "spock" (2) 3: 4: 5: "kirk" (5) 6: 7: > i uhura 0: 1: "uhura" (1) 2: "spock" (2) 3: 4: 5: "kirk" (5) 6: 7:Continued in next column |
> i computer 0: 1: "uhura" (1) 2: "spock" (2) 3: 4: 5: "kirk" (5) 6: "computer" (5) 7: > r spock 0: 1: "uhura" (1) 2: 3: 4: 5: "kirk" (5) 6: "computer" (5) 7: > m kirk yes > m glorp no > r kirk 0: 1: "uhura" (1) 2: 3: 4: 5: 6: "computer" (5) 7: ** Hash Table is in error: String at location 6 belongs at 5 > q Goodbye. |