CS/COE 1501 Algorithm Implementation – Assignment#2

OVERVIEW



Purpose: To implement a hybrid Symbol Table that provides hash table access, indexed integer access, and sequential access (using an iterator).

Goal 1: To implement a linear probing hash table.

Goal 2: To implement an iterator.

BACKGROUND


The PHP language has an interesting array data type. Rather than a simple array like that of C or Java, the PHP array is a hybrid of a hash table and a linked list. This allows for a lot of functionality, including hash table access, indexed integer access, and sequential access (via the linked list). For more information on PHP arrays, see: http://php.net/manual/en/language.types.array.php.

DETAILS


In this assignment you will approximate a PHP array using Java. Your basic approach should be as follows:

    • You will create a new generic Java class with the following header: public class PHPArray<V> implements Iterable<V>

This will allow a user to instantiate a PHPArray of an arbitrary Java type and to iterate through its values using the predefined Java for loop.

– Your PHPArray class will be a symbol table and will thus store data as (key, value) pairs, where the keys will be Java Strings and the values will be the parameter type V.

– Your PHPArray will use a linear probing hash table as part of its underlying storage mechanism. This will enable the put(), get() and unset() [i.e. delete] methods to be done in O(1) time. Your hash table should handle delete and should automatically resize by doubling the


    1 Assignment adapted from Dr. John Ramirez’s CS 1501 class.
table size prior to a put() if the table is >= ½ full. For help on this part of your project, see the author's LinearProbingHashST.java class. Note, however, that there will be some differences in your class from this due to the requirement to also keep the data in insertion order via a linked list. For example, I do not recommend keeping the keys and values in separate parallel arrays, like the author does in LinearProbingHashST. Consider rather a linked type (i.e. a node) that contains both key and value fields. These objects could then be stored in your hash table and also accessed sequentially via a linked list.

– Your PHPArray will also use a linked list of data to keep track of the items in sequential order (based on the order that they were put() into the PHPArray). This ordering will be that produced and accessed by the Iterator() and some other methods as well. It is very important that this linked access does not alter the constant time access of the hash table. Thus, you should think carefully about how you will implement this. For example, keeping a completely separate hash table and linked list will not work, since to remove an item from the linked list requires linear time.

– There is a lot of other functionality required of your PHPArray class, based loosely on the functionality of the actual PHP array. This functionality is demonstrated in the main program Assig2.java. See the extensive comments in this file to determine the methods that you must implement and see the output produced in a2out.txt to see the required output. Your PHPArray class must run with this main program and produce the required output.

Important Notes:

    • If you are making an array of a parameterized type in Java, there are some issues with the array instantiation that may cause you grief. Below is a link that may help. You can also Google this to see other potential solutions. http://stackoverflow.com/questions/19478225/array-of-generic-nodes-java

    • You must utilize the Java Iterable and Iterator interfaces in this project. For help with these see the Java API and also your CS 445 Text.

EXTRA CREDIT


There are a LOT of additional methods / functions available for PHP Arrays. If you implement one or more of these that are non-trivial you can get some extra credit. See:

http://php.net/manual/en/ref.array.php

SUBMISSION REQUIREMENTS


You must submit to Gradescope at least the following files:

    1) Your PHPArray.java file

    2) Any other files that you have written

    3) Assignment Information Sheet.


2