Description

General instructions (Read carefully!)
1
Technical considerations
• You are provided some starter code that you should fill in as requested. Add your code only where you are instructed to do so. You can add some helper methods. Do not modify the code in any other way and in particular, do not change the methods or constructors that are already given to you, do not import extra code and do not touch the method headers. The format that you see on the provided code is the only format accepted for programming questions. Any failure to comply with these rules will result in an automatic 0.
• Your code should be properly commented and indented.
• Do not change or alter the name of the files you must submit, or the method headers in these files. Files with the wrong name will not be graded. Make sure you are not changing file names by duplicating them. For example, main (2).java will not be graded. Make sure to double-check your zip file.
• Submit your files individually on codePost (no zips)
• You will automatically get 0 if the files you submitted on codePost do not compile, since you can ensure yourself that they do.
Homework 1: Building a Hash table
Exercise 1 (20 points). Building and inserting keys into two hash tables We want to compare the performance of hash tables implemented using chaining and open addressing. In this assignment, we will consider hash tables implemented using the multiplication and linear probing methods. We will (respectively) call the hash functions h and g and describe them below. Note that we are using the hash function h to define g.
Collisions solved by chaining (multiplication method): h(k) = ((A · k) mod 2w) >> (w − r) Open addressing (linear probing): g(k,i) = (h(k) + i) mod 2r
In the formula above, r and w are two integers such that w > r, and A is a random number such that 2w−1 < A < 2w. In addition, let n be the number of keys inserted, and m the number of slots in the hash tables. Here, we set m = 2r and r = dw/2e. The load factor α is equal to mn .
We want to estimate the number of collisions when inserting keys with respect to keys and the choice of values for A.
We provide you a set of three template files that you will complete. This file contains three classes; a main class and one for each hash function. Those contain several helper functions, namely generateRandom that enables you to generate a random number within a specified range. Details on which functions are included, how to use them, and where to add in your code can be found as comments in the java files. Please read them with attention. Note that verb?main.java? is only included for you to test out the other classes. You do not have to use it, and you must not submit it.
Your first task is to complete the two java methods Open_Addressing.probe and Chaining.chain. These methods must implement the hash functions for (respectively) the linear probing and multiplication methods. They take as input a key k, as well as an integer 0 ≤ i < m for the linear probing method, and return a hash value in [0,m[.
Next, you will implement the method insertKey in both classes, which inserts a key k into the hash table and returns the number of collisions encountered before insertion, or the number of collisions encountered before giving up on inserting, if the table is full.
Note that for this exercise as well as for the rest of the homework, we define the number of collisions in open addressing as the number of slots visited before inserting or removing a key, not counting the slot in which the insertion is successful. For chaining, we simply consider the number of other keys in the same bin at the time of insertion as the number of collisions. You can assume the key is not negative, and that all keys are unique.
Once this exercises is complete, we are done with the Chaining class. All further exercises will focus on the open addressing method.
Exercise 2 (15 points). Searching and removing keys Then you will add a method searchKey, this one only in Open_Addressing. This method should take as input a key k, and should return an array of two integers. The first one will be the index of k in the table if k is found, otherwise it returns -1. The second element of the array will be the number of collisions that happened before finding the key. The search phase should be optimized: you should visit as few slots as possible.
You will also implement a method removeKey, only in Open_Addressing. This method should take as input a key k, and remove it from the hash table while visiting the minimum number of slots possible. Like insertKey, it should output the number of collisions. If the key is not in the hash table, the method should simply not change the hash table, and output the number of slots visited. You can call searchKey in this method. You will notice from the code and comments that empty slots are given a value of −1. If applicable, you are allowed to use a different notation of your choice for slots containing a deleted element.
Exercise 3 (15 points). Automatic resize of the hash table
Exercise 4 (20 points). Optimization
Exercise 5 (10 points). Concerns about denial of service attack
The hash function we are using is pretty basic and does not offer a lot of protection against an attacker. If an attacker knows which hash function you are using, they could add to the table a large amount of keys that would collide every time. Put yourself in an attacker’s shoes and implement the function collidingKeys, which produces keys that all have the same hash value through function h. This function takes as parameters a key k, an integer n indicating the number of colliding keys to be returned, and w (which we assume is known by the attacker). It returns an int[] containing the n keys that collide with k (you can include k in the returned array). Hint: you will have to find a mathematical expression for a set of keys that all share the same hash through function h.
Exercise 6 (20 points). Universal hashing
The best way to avoid the type of attack described in the previous exercise is to randomize the choice of the hash function. Since we have a resizing function, we can randomize the hash function each time we resize the table because we need to rehash all the keys anyway. In universal hashing, the randomization of hashing function occurs by choosing a function in a set (a family) of hashing functions. This set has mathematical properties that guarantees as few collisions as possible. For our needs we will use the following hash function family :
h(x) = ((ax + b) mod p) mod m
Here p is a prime number higher than the required size of the table m. a and b are random integers chosen between [1,p − 1] and [0,p − 1] respectively.
Fill in the new Universal_Hashing class so that it uses universal hashing with the same linear probing formula from above:
g(k,i) = (h(k) + i) mod 2r
Note that not all functions need to be overwritten, and feel free to reuse your previous code to get it done.
Submit your three Java classes (not main.java) via codePost. Test your code thoroughly!