Topic: ALGORITHMS & DATA STRUCTURES TOPIC 4: HASHING

Use Java

Part A :In this lab submission, your task is implementing a hash table with linear probing. The hash function to implement is as follows:

h(k)=(a*k+c) mod m

where coefficients a, c and m are positive integer numbers and m is the number of buckets of the hash table. The client of the hash table will specify these parameters.

Because this lab submission will be automatically graded, you are provided with a skeleton code:

a single file (HashTable.java) for Java programmers

Your task is completing the code that makes the methods in that skeleton code operative. You must not change the prototypes of the methods. If you do that, your code will not pass the automatic tests and . You can add other methods if you want

Part B : JAVA PROGRAMMERS: Please, look at the content of the skeleton file you are provided for this lab submission (HashTable.java) in the picture. You can see there are 6 methods you must implement:

HashTable: This is a constructor that initialises the values of a, c and m (a takes the value of _a, c the value of _c and m the value of _m) and allocates memory space (to store m integer values) to the hash table buckets.

insert: This function is in charge of inserting strictly positive numbers into the hash table, using linear probing for collision resolution. The number to insert is stored in the variable key. If the load factor of the hash table is already 1 when a new number is going to be inserted, you have to apply extend & rehash. You choose the value of the extension factor.

extend: This method increases the size of the hash table. To do so, you must create a new (bigger) array temporarily storing the content of the hash table. Then, you increase the size of buckets (using new) and rehash the contents of the temporary array into buckets.

find: This function searches for the number key in the hash table. If the number is found, it returns true. Otherwise, it must return false.

remove: This function removes the number key from the hash table. Remember that, because of linear probing, a number present in the hash table might not be in its natural position.

loadFactor: This function returns, as a double, the fraction of total hash buckets that are occupied.

Notice: You must keep the buckets member variable public and use values of the hash function h as indexes into that array. In a real implementation buckets would be declared as private, but it needs to be exposed for testing purposes. (You may of course add other private member variables)

Hash Table - Notepad File Edit Format View Help ublic class HashTable { // public for testing purposes public int buckets[]; public HashTable(long _a, long _s, long _m) { } public void insert(int key) { } public void extend() { } public boolean find(int key) { return false; } public void remove(int key) { } public double loadFactor() { return 0.0; } }