DESCRIPTION: In this lab you will implement a hash table with linear probing and perform simulations to observe its performance. The hash table will store integers. The hash function to be used is h(r-r%M (the remainder after dividing r by M), where M is the size of the hash table. The set of possible keys r is the set of positive integers representable by the int data type. You must write a Java class HashTableLin and a class TestHashTable for testing and for measuring its performance. SPECIFICATIONS: .Class HashTableLin must contain a field named table, of type Integer [, which is a reference to the array which stores the keys. There must be other fields to store the size of the table, the number of keys stored in the table and the maximum load factor allowed. All fields must be private. Pay attention to update these fields when performing hash table operations (when necessary) e Class HashTableLin must contain at least the following constructor public HashTableLin(int maxNum, double load) creates a HashTableLin object representing an empty hash table with maximum allowed load factor equal to load. The amount of memory allocated for the hash table should be large enough so that maxNum keys could be stored without its load factor exceeding the value of parameter load. The size of the table should be the smallest prime number such that the above requirement to be met. For stance, if maxNum 5 and load-04, then the size of the table should be at least 5/0.4 12.5. The smallest prime number satisfying the requirement is 13. .Class HashTableLin must contain at least the following public methods: 1) public void insert(int n): Inserts the key n in this hash table if the key is not already there. If the insertion will cause the load factor to exceed the maximum limit prescribed for this table, then rehashing should be performed by invoking the method rehash) 2) private void rehash): Allocates a bigger table of size equal to the smallest prime number at least twice larger than the old size. Then all keys from the old table are hashed into the bigger table with the appropriate hash function and with linear probing. 3) public boolean isIn(int n): Returns true if key n is in this hash table. 4) public void printKeysO: Prints all keys stored in this table, in no partic- 4) public void printKeysAndIndeesO: Prints all keys stored in this table It returns false otherwise ular order and the array index were each key is stored, in increasing order of array indexes. DESCRIPTION: In this lab you will implement a hash table with linear probing and perform simulations to observe its performance. The hash table will store integers. The hash function to be used is h(r-r%M (the remainder after dividing r by M), where M is the size of the hash table. The set of possible keys r is the set of positive integers representable by the int data type. You must write a Java class HashTableLin and a class TestHashTable for testing and for measuring its performance. SPECIFICATIONS: .Class HashTableLin must contain a field named table, of type Integer [, which is a reference to the array which stores the keys. There must be other fields to store the size of the table, the number of keys stored in the table and the maximum load factor allowed. All fields must be private. Pay attention to update these fields when performing hash table operations (when necessary) e Class HashTableLin must contain at least the following constructor public HashTableLin(int maxNum, double load) creates a HashTableLin object representing an empty hash table with maximum allowed load factor equal to load. The amount of memory allocated for the hash table should be large enough so that maxNum keys could be stored without its load factor exceeding the value of parameter load. The size of the table should be the smallest prime number such that the above requirement to be met. For stance, if maxNum 5 and load-04, then the size of the table should be at least 5/0.4 12.5. The smallest prime number satisfying the requirement is 13. .Class HashTableLin must contain at least the following public methods: 1) public void insert(int n): Inserts the key n in this hash table if the key is not already there. If the insertion will cause the load factor to exceed the maximum limit prescribed for this table, then rehashing should be performed by invoking the method rehash) 2) private void rehash): Allocates a bigger table of size equal to the smallest prime number at least twice larger than the old size. Then all keys from the old table are hashed into the bigger table with the appropriate hash function and with linear probing. 3) public boolean isIn(int n): Returns true if key n is in this hash table. 4) public void printKeysO: Prints all keys stored in this table, in no partic- 4) public void printKeysAndIndeesO: Prints all keys stored in this table It returns false otherwise ular order and the array index were each key is stored, in increasing order of array indexes
