Answer Happy

ArrayHashTable.java
LinearCollisiomHandler.java
QuadraticCollisionHandler.java
Hashtable.java
PublicArrayHashTableTest.java
Directions:
- Initialize count to θ, capacity to the argument, loadFactor to the respective DEFAULT values, * collisiontlandler to the collisionHdler argument, create the three arrays " for keys, values, and the isActive boolean array. public ArrayHashTable(int capacity, collisionHandler ⟨K⟩ collisionHdler) \{ | 11 ABimplement this method. Initialize count to θ, capacity and loadFactor to the respective argument values, collisiontandler to the collisiontdler argument, create the three arrays for keys, values, and the isactive boolean array. public ArrayHashTable(int capacity, double loadFactor, collisionHandler \&K collisionHdler) \{ I / Eoonglement this method. \} f∗∗ * Returns the number of elements in the hash table. public int getsize() \{ * For each key in the key array, if that cell is active (true) in * the activearray, get the index by calling the hash function, use the collisionHandler * probe method to get the new index (it nay be different from the original hash if * a collision occurred). Enter the key in the new keyArray, value in the new valueArray, * and set the new activeArray to true. Finally, assign the current keyArray, valueArray, - and activeArray to the new arrays. * 1
- Calculates and returns the load factor of the hash table. - This is the ratio of the number of elements stored in the hashtable - divided by the total capacity of the hashtable. −1 private double calcloadfactor () \{ /1 i.implesint tris cesthod - Insert the provided key value pair into the hashtable. If the key exists in - the table, the stored value is overwritten with the new value passed in. - Please use the provided gethash method to get the hash for the array index. * Steps: check is current load is > loadfactor. If true, call resizeArray. - Then see if key is in the table by calling getindex. If key exists, overwrite value - in the valueArray. If key does not exist, get the index by calling the hash function (gethash). - Then call resolveCollision to see if a collision occurs and if so, that methos will use the - collision handler to resolve it. Then enter the key in the keyarray using the index returned from - resolveCollision, enter the value in the valueArray, and set the isactiveArray to true. Finally, - increment the count. 1 public void put( K key, v value) \{ I 11 inplement this method. 3 jon - Returns the value associated with the key if it exists in the hashtable. - Get the index by calling the hash function, then check if key exists by calling getindex. - Return the value in the valuearray if key is in the table.
- Returns the value associated with the key if it exists in the hashtable. - Get the index by calling the hash function, then check if key exists by calling getindex. " Return the value in the valueArray if key is in the table. - Returns null if the key is not in the table. -/ public V getvalue( K target) \{ indeplement, this, method I return null; I Removes the key-value pair specified by the targetiky from the hashtable and returns the value. - The method gets the hash on the targetikey, then checks if the key is in the table by calling getindex. - Then, if targetkey is in the table, get the value associated with the targetkey from the valuedrray, - then set the activearray to false as this cell is now open, decrement the count, and return the value. - Cthrows ElementWotFoundException if the target does not exist in the table. public V remove( K targetKey)throws ElementwotFoundException \{ /f : Implement this method / Returns a KeyIterator for the keys in this HashTable. public IteratoreK > keyIterator() | return new KeyIteratorkK (keyArray, count); \} public int getcapacity() return capacity; \} public double getLoadFactor() .
public K[] getKeyArray public double getloadFactor( public K[] getkeyArray()\{ public V[] getvalueArray()\{ public boolean[] getisactiveArray()\{ |return isActiveArray; public Collisiontandler ⟨K⟩ getcollisiontandler()] |return collisionhandler; structures >0 ArrayHashTable,java > \& AfrayHashTable ⟨k,V>>$ getCollsionHandler0 ] - Coment out statements as needed. Use the debugger to see * what your code is doing by stepping in, out, and over methods * and statements, and checking the variables pane to see the state * of your table and its variables. -1 Run | Debug public static void main(String[] args) throws Exception \{ I // Init the type of collision handler: linear or quadratic. // CollisionHandler ⟨ String ⟩ collisionHdler = new LinearCollisionHandler \langle\rangle() ; CollisionHandler ⟨ string〉 collisionHdler = new QuadraticcollisionHandler ⟨(); AcrayHashTablesstring, String> table = new AcrayHashTablecstring, String (collisionHdler); table.put(key: "fatimeh", value: "efanB*k"); // test the get method after the put method was called:

package structures; public class LinearcollisionHandler ⟨K⟩ implements collisionHandler ⟨K⟩ \ private int probelength; Constructors to set probelength to 1 , or a different length. " public LinearcollisionHandler() | this.probelength =1; public LinearcollisionHandler(int probeLength) \{ I 1 this.probelength = probeLength; * Method starts at index and searches linearly until an-oper - is found in the array. This could inc ∗ public int probe(int index, boolean[] activeArray, int M ) \{ | 1 i. Inplement this method, ) Start at index and search the array linearly until the target - is found. Then return the array index of the target. * Return -1 if not found. * / |public int search(int startindex, K target, K[] keyArray, boolean [] activeArray, int M ) \{ 1/ : Implement this method.
B]
" Method starts at index and searches quadratically until an open spot - is found in the array. This could include index itself. - This is the formula to generate a new index to : | curIndex = startindex, i=1 while the space at curindex is occupied curIndex =( curIndex +cx∗i+c2∗(i∗i))× tablesize; increment i return the curIndex * Cparam startindex the index that generated a collision I "Gparan activeArray the boolean array where true cells are occupied, false are open. "Cparam M the size of the table. - 1 public int probe(int startindex, boolean[] activelrray, int m)f int curindex =−15 /1 : Implewe 3 Start at index and search the array quadratically until the target is found. Then return the array index of the target. Return −1 if not found. public int search(int startindex, K target, K[] keydrray, boolean [] activelrray, int w){ 1/1 Implement this method. return - 15

: ⟩ test ⟩ PublicArrayHashTableTest,java ⟩{} test
CTest: public void testconstructor1quadratic() throws Exception \{ CollisionHandler ⟩ quadcollisionHdler = new QuadraticcollisionHandlercinteger>(); ArrayHashTablecinteger, String> q= new ArrayHashrablesinteger, String (quadcollisionthler); assertEquals (θ, q.getsize()); assertTrue((ArrayHashTable.DEFAULT_CAPACITY - q.getCapacity ())<.001); assertTrue((ArrayHashTable.DEFAULT_LOAD_FACTOR - q-getLoadFactor()) <.601); object [ ] karr = q.getkeyArray (); assertTrue(karr. length = ArrayHashTable.DEFAULT_CAPACITY); object [ ] varr =9⋅ getvalueArray (); assertTrue(varr. length = = ArrayHashTable.DEFAULT_CAPACITY); boolean[] aa = q.getisActiveArray(); assertTrue(aa. length = = ArrayHashTable.DEFAULT_CAPACITY) assertTrue(q.getCollisionHandler() =-quadCollisionHdler) rest assertEquals (θ, q.getsize())); assertEquals (100, q.getcapacity())); assertTrue((ArrayHashTable.DEFAULT_LOAD_FACTOR - q.getLoadFactor( )) <.001); object [] karr = q.getkeyArray(); assertTrue(karr. length =100); object [] varr = q.getvalueArray(); assertTrue(varr. length =100); boolean[] aa = q.getIsActiveArray(); assertTrue(aa.length =100 ); assertTrue (q⋅getcol1 siontandler ()=−1 inCollisionHdler ); Crest public void testconstructor2quadratic() throws Exception \{

Grest public void testconstructor3Quadratic() throws Exception \& ArrayHashTablecinteger, String> q= new ArrayHashTablecinteger, Strings (capacity: 100, loadFactor: 0.9, quad assertequals (0, q.getsize()); assertEquals (100,9 getCapacity ()); assertirue ((0.9−q-getLoadfactor ())<.6e1); object [ ] karr =9⋅ getkeyArray (); assentirue(karr. length = 100 ); Object [] varr =q⋅ getvalueArray (); assertirue(varr. length =100 ); boolean[] aa = q-getrsActiveArray(); assertrue ( aa. length =100); assertirue (q⋅gcot CollisionHandler ()=q qadCollisionHdler ); Orest public void testPutandGetvalue() throws Exception } ArrayHashTablecinteger, String> q= new ArrayHashTablecinteger, String> (lincollisionkdler); assertEquals( θ, q.getsize()); q.put(key: 1, value: "apple"); q.put(key: 10, valuet "pencil"); assertirue(q-getvalue(target: 1), equals ("apple")); assertTrue(q.getvalue(target: 10). -equals ("pencil")); q.put(key: 3, value: "pineapple"); assertequals(3, q.getsize()); assertTrue(q.getvalue(target: 3).equals("pineapple")); Crest public void testResizeArray() throws Exception \{ CollisionHandler IincollisionHdler = new Linearcollisiontandler>(); ArrayHashTablecinteger, Strings q= new ArrayHashTablecinteger, String> (capacity: 3 , 1incollisionkder); assertequals (θ, q.getsize()); assertEquals (3, q.getCapacity( ) ) 3



General Information In this project, a hashtable is used by a website to store login credentials: a unique username and password. When a user creates an account, they enter a usemame, a string that will uniquely identify them in the database, and a password. The username serves as the key, and the password string is the value. Program Interaction Here is what the output would look like when all the ToDos are completed. Creating an account and viewing the database: Note that the V menu option has been included for development and debuging purposes. You can see that the password string submitted by the user has been encrypted. Deleting an account: Enter L to log in, C to create a new account, P to change passmord, a to delete account, Y to view all logins (for debug), X to quit : a Wseframe: gracehopperiob Enter passino Enter L to log in, C to create a new account, P to change passord, b to delete account, V to view all logins (for debug), X to quit: no entries.
Project Specification: Your Tasks: We suggest implementing the TODOs in the following methods in the ArrayHashTable class: constructors, size, put, and get. Also implement the TODOs in the LinearCollisionHandler class. The goal is to implement the simplest code that will allow you to be able to use the code in the main method in ArrayHashTable to test and debug creating the HashTable object, and then adding and getting some data. Once this is working, implement the remove method and test in the same way. Next, you can add the more complicated methods such as checking the load factor and resizing when necessary and then complete the TODOs in QuadraticCollisionHandler class.
Hashtable Implementation: There are many ways to implement a hashtable. This project uses three arrays to implement a hashtable: T[ ] keyArray: all keys are stored in this array. T [ ] valueArray: all values stored in this array boolean[ ] isActiveArray: true means the cell contains a data value, false means the cell's data has been deleted, but remains in the cell. This is needed for resolving collisions by open addressing (linear or quadratic probing). For example, when searching for a value, encountering a cell labeled false that contains data (is not null) means the search should continue. Encountering a cell labeled false that is empty (contains null) means the search has ended. A diagram of the three arrays: The tables show key/values at index 1 , open cells at index 0 and 3 , and a deleted keylvalue at index 2. Testing We suggest following the steps described in the "Project Specification: Your Tasks:" section above. Use the debugger to test that your code is working as you build more functionality. Once your code is working, then run the unit tests. Finally, upload to gradescope for autograder testing.