Implementing a Hash Table in Java with Hashing

1. Study the Tableclass and write a JUnit test class TableTest.java to test the Table class as follows. Submit the test class and screen captures showing pass of all the tests. Either JUnit4 or JUnit 5 in any IDE may be used. (2 points)

1. Create a table and put 10 entries of your choice (e.g., testTable.put(1, “testA”)).

1. Test findIndex() for an non-existing entry.
2. Test findIndex() for an existing entry.
3. Test put() for an non-existing entry.
4. Test put() for an existing entry
5. Test put() for a new entry putting into the full table.

public class Table

{

private int manyItems;

private Object[] keys;

private Object[] data;

private boolean[] hasBeenUsed;

public Table(int capacity){

if (capacity <= 0)

throw new IllegalArgumentException("Capacity is negative"); keys=new Object[capacity];

data=new Object[capacity];

hasBeenUsed=new boolean[capacity];

}

public boolean containsKey(Object key){

return findIndex(key)!=-1;

}

public int findIndex(Object key){

int count=0;

int i=hash(key);

while (count <= data.length && hasBeenUsed[i]){

if (key.equals(keys[i]))

return i;

count++;

i=nextIndex(i);

}

return -1;

}

public Object get(Object key){

int index=findIndex(key);

if (index==-1)

return null;

else

return data[index];

}

private int hash(Object key){

return Math.abs(key.hashCode())%data.length;

}

private int nextIndex(int i){

if (i+1 == data.length)

return 0;

else

return i+1;

}

public Object put(Object key, Object element){

int index = findIndex(key);

Object answer;

if (index!=-1){ // The key is already in the table.

answer = data[index];

data[index] = element;

return answer;

}

else if (manyItems<data.length){ // The key is not yet in this Table.

index=hash(key);

while (keys[index]!=null)

index = nextIndex(index);

keys[index] = key;

data[index] = element;

hasBeenUsed[index] = true;

manyItems++;

return null;

}

else{ // The table is full.

throw new IllegalStateException("Table is full.");

}

}

public Object remove(Object key){

int index = findIndex(key);

Object answer = null;

if (index!=-1) // The key exists in the table.

{

answer=data[index];

keys[index]=null;

data[index]=null;

manyItems--;

}

return answer;

}

}

2. Consider the Accountclass in the below. In the class, the withdraw() method audits when money is withdrawn. In order to test the withdraw() method, a stub should be provided for the

audit object. Implement the stub structure shown in the class diagram and test withdraw() method using the StubAudit class. Reference the stubbing example on slide 13-16 in Testing Strategies. (1 point)

3. Study the following code and draw a control flow graph and measure the cyclomatic complexity based on the graph. The work must be shown. (2 point)

public static void main(String[] args)

{

final int NUMCHARS = 26;

Scanner scan = new Scanner(System.in);

int[] upper = new int[NUMCHARS];

int[] lower = new int[NUMCHARS];

char current; // the current character being processed

int other = 0; // counter for non-alphabetics

System.out.println("Enter a sentence:");

String line = scan.nextLine();

• Count the number of each letter occurence for (int ch = 0; ch < line.length(); ch++)

{

current = line.charAt(ch);

if (current >= 'A' && current <= 'Z') upper[current-'A']++;

else

if (current >= 'a' && current <= 'z') lower[current-'a']++;

else other++;

}

• Print the results

System.out.println();

for (int letter=0; letter < upper.length; letter++)

{

System.out.print( (char) (letter + 'A') );

System.out.print(": " + upper[letter]);

System.out.print("\t\t" + (char) (letter + 'a') );

System.out.println(": " + lower[letter]);

}

System.out.println();

System.out.println("Non-alphabetic characters: " + other);

}

4. Based on the cyclomatic complexity measured in Question 3, identify the basis set of independent paths. (1 point)

5. For each independent path in Question 4, write a test case in terms of input and output to exercise the path. (1.5 point)

6. The following diagrams show a model for a pretty printing application. Refactor the class diagram and sequence diagram using the Visitor design pattern. Justify pros and cons of the refactored model (1.5 point).