How would this implementation work for this alternative deletion ?
2. In class we discussed deleting from a hash table that uses linear probing. The text approaches the problem by deleting the item and moving all the subsequent cluster of hash elements one position up. This is necessary in order to not disconnect a collision chain, but it may harm the performance, especially if there are large clusters. An alternative way to delete from a hash table is as follows: Every item in the table has an extra boolean flag, active or not active. When an item is "deleted" it is not physically removed from the table, but rather, its active flag is set to false. For this to work, several other things have to be modified from the original implementation: . When searching for an item in the table, you should return it only if its active flag is set to true. . When calculating the table size for rehash, you have to take into account "deleted" items as well, since they are in the table and take up space. . When rehashing, you obviously don't need the deleted objects anymore, and therefore you insert only active objects into the new table. Implement this alternative deletion. Do the following: (a) Start from S&W's implementation of hash with linear probing at: http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/LinearProbingHashST.java. (b) Copy it over to your src subdirectory and change the class name (and file name, of course), to LinearProbingHashST2 . java. (c) delete the package declaration from the top of the file. (d) Notice that since the source is not part of the library now, you may have to import some classes from the algs4 library. (e) Make the changes noted above. Notice that it's not only the delete function that you should change. (f) Test the delete function: In the main function, have the LinearProbingHashST2 read a file that contains strings. For example, you can use tinyST . txt which you can find at http://algs4. cs. princeton. edu/34hash/tinyST. txt. You can use the LinearProbingHashST's main function as a starting point: It reads a file string by string and puts the
pair in the table (in this case every string is just one character). However, don't read from the standard input but make the file a command line parameter (see below). It makes the auto-grading easier. g) Print out all the characters, then delete several characters and print again. The input file and characters for deletion should be the command line arguments (see below). You can delete any number of characters. (h) Your class should have the following two functions: int numberOfOverallkeys () that returns the number of all keys - including invalid ones, and int tableSize () which returns the size of the table (notice that size () returns the number of (valid) keys, not the size of the table itself. (i) For testing you can have the main function print out the size() of the table and the values of the n and m fields (as appear in the original source file) before and after deletion. Here is an example: Usage example: java -cp .:. ./lib/algs4. jar pal . LinearProbingHashST2 tinyST. txt S A Notice that the input file is the first command line parameter, followed by the character(s) to delete. Please don't hardcode anything. The output format for the autograder should look like that (this is the example above. I may use other files for testing): A 8 C E 12 H L 11 M
